ECAI 2004 Conference Paper

Using Symmetries for Coloring Queen Graphs

Michel Vasquez, Djamal Habet

The queen graph coloring problem consists in covering a nxn chess-board with nxn queens, so that two queens of the same color cannot attack each other. When the size, n, of the chess-board is not a multiple of 2 or 3 it is hard to color the queen graph with only n colors. We have developed an exact algorithm which is able to solve exhaustively this problem for dimensions up to n=12 and find one solution for n=14 in 168 hours of computing time. The 454 solutions of 12x12 Queen show horizontal and vertical symmetries in the color repartition on the chess-board. From this observation, we design a new exact, but incomplete, algorithm which leads us to color nxn Queen problems with n colors for n=15, 16, 18, 20, 21, 22, 24 and 28 in less than 24 hours of computing time by the exploitation of symmetries and other geometric properties.

Keywords: Queen Graph Coloring, Exact Incomplete Algorithm, Symmetry, Rotation

Citation: Michel Vasquez, Djamal Habet: Using Symmetries for Coloring Queen Graphs. In R.López de Mántaras and L.Saitta (eds.): ECAI2004, Proceedings of the 16th European Conference on Artificial Intelligence, IOS Press, Amsterdam, 2004, pp.226-230.

ECAI-2004 is organised by the European Coordinating Committee for Artificial Intelligence (ECCAI) and hosted by the Universitat Politècnica de València on behalf of Asociación Española de Inteligencia Artificial (AEPIA) and Associació Catalana d'Intel-ligència Artificial (ACIA).