Comparing thousands of chessboard colorings reveals key solver tricks

Coloring Queens with Thousands of Encodings

Logic in Computer Science

Summary

The problem is to color a chessboard so no two squares in the same row, column, or diagonal have the same color, using the fewest colors possible. The authors studied over a thousand ways to set up this problem for computer solvers, examining how different rules and hints affect solving speed. They found that the choices for breaking symmetrical solutions, adding special clues called clique hints, and strict rules assigning colors to squares have the biggest impact. They also showed some hints work well beyond the specific method Knuth originally suggested.

What this means in practice

Authors

Bernardo Subercaseaux, Benjamin Przybocki, Marijn J. H. Heule

Abstract

In The Art of Computer Programming, Knuth benchmarked 10 encoding techniques for computing the chromatic number of the queen's graph: the minimum number of colors needed to color the squares of an $n \times n$ chessboard so that no two squares sharing a row, column, or diagonal receive the same color. In this paper, we extend his analysis much further by comparing thousands of encodings for the same problem, which allows us to identify additional factors that are important for solver performance. We obtain 1584 encodings for this problem by varying (a) the constraints that encode which color is assigned to each cell, (b) the constraints that forbid the same color appearing in a row, column, or diagonal line, and (c) the symmetry-breaking constraints. We find that the three most impactful encoding factors are (i) the choice of symmetry-breaking constraints, (ii) enabling so-called clique hints, and (iii) enforcing that each cell is assigned exactly one color through blocked clauses. Furthermore, while Knuth proposed clique hints as an advantage of the order encoding, we show in fact that they can be effectively employed for the one-hot encoding as well.