
[full paper] 
Michel Vasquez, Djamal Habet
The queen graph coloring problem consists in covering a nxn chessboard with nxn queens, so that two queens of the same color cannot attack each other. When the size, n, of the chessboard 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 chessboard. 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.226230.