<i>"The hard part becomes writing those constraints, not writing the actual solution."</i><p>Yes, writing constraints can be difficult, as can figuring out which constraints you need, and coming up with fitness functions for figuring out how good a given solution is.<p>Other difficulties include tweaking the various parameters of the GP to perform well enough to get reasonable solutions in a reasonable amount of time, and making sure you're not overoptimizing, etc...<p>The other thing I'd mention is that one should always take the results of AI research with a big grain of salt.  Often the problems they work on are unrealistic toy problems that have little relevance to anything you'd actually do in the real world, and their statistical methods leave a lot to be desired.<p>There's huge pressure to get funding, so many papers tend to be unrealistically optimistic and misleading (but get published anyway).