01144nas a2200157 4500008004100000020001800041245009000059210006900149260001500218300001500233520063400248653002800882653002100910100001600931856003900947 2003 eng d a0-7803-7804-000aEvolving binary constraint satisfaction problem instances that are difficult to solve0 aEvolving binary constraint satisfaction problem instances that a bIEEE Press a1267--12733 aWe present a study on the difficulty of solving binary constraint satisfaction problems where an evolutionary algorithm is used to explore the space of problem instances. By directly altering the structure of problem instances and by evaluating the effort it takes to solve them using a complete algorithm we show that the evolutionary algorithm is able to detect problem instances that are harder to solve than those produced with conventional methods. Results from the search of the evolutionary algorithm confirm conjectures about where the most difficult to solve problem instances can be found with respect to the tightness.10aconstraint satisfaction10aproblem evolving1 aHemert, J I uhttp://research.nesc.ac.uk/node/23