N-Queens problem and Sudoku: constraint search

The N-Queens problem asks for every way to place n queens on an n × n chessboard so that no two attack each other. Two queens attack when they share a row, a column or a diagonal. Sudoku asks for the digits 1 to 9 in every row, column and 3 × 3 box of a 9 × 9 grid. Both yield to constraint search, a form of backtracking that places one piece at a time, checks only the rules that piece touches, and backs out the moment one breaks.

The problem: n queens, and a 9 × 9 grid

For n = 4 there are two placements, columns [1, 3, 0, 2] and [2, 0, 3, 1]. Boards of size 2 and 3 have no placement at all, and size 1 has one. For n = 8 the N-Queens problem has 92 placements, the count the OEIS lists.

The example puzzle has 25 given digits and exactly one solution. A 2 written into its empty cell at row 7, column 8 breaks no rule yet, but leaves a grid that no Sudoku solver can complete.

The brute force, and why it fails at these sizes

Every ordering of the columns puts one queen in each row and each column, so the brute force tries them all and checks the diagonals of each finished board. For the grid, it tries every digit in every empty cell.

"""The brute force for both puzzles: build complete answers first, check the rules last."""
import time
from itertools import permutations
from math import factorial


def queens_brute_force(n):
    """Every ordering of the columns puts one queen in each row and each column; keep those with no shared diagonal."""
    found = 0
    for cols in permutations(range(n)):
        if len({r - c for r, c in enumerate(cols)}) == n and len({r + c for r, c in enumerate(cols)}) == n:
            found += 1
    return found


print(" n  placements  orderings tried   time")
for n in range(4, 10):
    start = time.perf_counter()
    found = queens_brute_force(n)
    seconds = time.perf_counter() - start
    print(f"{n:2} {found:11,} {factorial(n):16,} {seconds:6.2f} s")
rate = factorial(9) / seconds
print(f"n = 12: {factorial(12):,} orderings, about {factorial(12) / rate / 60:.0f} minutes at the speed of the last row")

PUZZLE = "004008030000010005000000809007300010090001050510006903300000007000050000060042080"
empty = PUZZLE.count("0")
print(f"the 9 x 9 puzzle has {empty} empty cells: 9 ** {empty} = {9 ** empty:.2e} ways to fill them")

 n  placements  orderings tried   time
 4           2               24   0.00 s
 5          10              120   0.00 s
 6           4              720   0.00 s
 7          40            5,040   0.00 s
 8          92           40,320   0.03 s
 9         352          362,880   0.24 s
n = 12: 479,001,600 orderings, about 5 minutes at the speed of the last row
the 9 x 9 puzzle has 56 empty cells: 9 ** 56 = 2.74e+53 ways to fill them

The counts are right, but the cost is n!: 479,001,600 boards for n = 12, minutes of Python for one answer. Any n of the n² squares would be worse still, 4,426,165,368 boards for n = 8, and the grid’s 56 empty cells allow about 2.7 × 10⁵³ fillings.

What to notice

• A conflict always involves exactly two pieces, so it shows the moment the second of them lands.
• No row can hold two queens, and there are as many rows as queens: fill the rows one at a time.
• A cell’s row, column and box decide which digits it can still take.
• A cell with one possible digit is forced, and one with none is lost, so handle such cells first.

Six techniques follow:

• Sets of used columns and diagonals make the test of a square three lookups.
• Bitmasks give all safe squares of a row from one expression.
• Mirror symmetry lets a counter explore only half of the first row.
• Most constrained first fills the cell with the fewest possible digits next.
• Forced digits are written in before any guess.
• A modular rule places n queens with no search when n shares no factor with 6.

Queens row by row, with constant-time conflict checks Pro: opens with a Pro, Premium or Ultimate pass