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
- •For constraint solver developers: Optimize solver performance for graph coloring problems by choosing effective symmetry-breaking constraints and encoding hints.
- •For software engineers in optimization: Improve encoding strategies in constraint-based systems to solve scheduling or resource allocation tasks more efficiently.
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.