An evolutionary approach to search for NCR-boards

An NCR (non-chromatic rectangle) board is a chessboard in which the squares can be colored in such a way that no rectangle has four corners that are of the same color. The search space for finding a 10×10 NCR-board with three colors, is so large, 3¹⁰⁰, that traditional search techniques may be inefficient or even impractical. While genetic algorithms (GAs) usually have problems zeroing in on the global optimal solution, the NCR-board problem demands a perfect solution; a near-optimal solution is simply not good enough. A wrong-step in this case is frequently a big one. In addition, local hill-climbing, which usually helps a GA to reach the absolute global optimum, has been shown to be ineffective in the experiments. This paper investigates the application of GA techniques to search for a three-colored 10×10 NCR-board. Special strategies to avoid premature convergence to near-optimal solutions are analyzed and discussed