--- title: 'The N-Queens Problem' source: 'https://academia.sh/en/courses/advanced-algorithms/n-queens-problem' course: 'Advanced Algorithms and Problem Solving' language: en updated: '2026-08-17T18:07:24+00:00' license: 'CC BY-SA 4.0' --- # The N-Queens Problem Taking the shared definition's backtracking counts as input and measuring symmetry breaking on top of them: restricting the first queen to half the board brings the node count at eight queens from 2057 down to 1029, a ratio of 2.00; 1.69 at five queens, 1.78 at nine. The mirrored solutions restore the oracle's solution set exactly, on all five board sizes. The fundamental-solution count at eight queens is 12 instead of 92, but the smallest equivalence class is 4, not 8. Pruning's gain grows with n; symmetry breaking's gain stays fixed at 2 and buys nothing when finding the first solution. In the previous lesson, the pattern gave a wrong answer and the oracle gave the correct one. This lesson looks at the oracle itself. In the n-queens problem, the oracle is brute force trying every placement of queens on the board; backtracking does the same search by cutting conflicting branches. The shared definition already gave the numbers for both, and **this lesson does not remeasure them — it takes them as input**. The problem is this: n queens are to be placed on an n-by-n board so that no two share a row, a column, or a diagonal. The new question is: can the board's own symmetries be used to shrink the search space, and if so, is that gain **the same kind** as what pruning contributes. - **CP30.** The shared definition's backtracking counts are **input**: at n=5, 54 pruned nodes and 3906 unpruned; at n=6, 153 and 55,987; at n=7, 552 and 960,800; at n=8, 2057 pruned nodes and 16,777,216 unpruned placements. These numbers are not remeasured. - **CP31.** The pruned traversal is exactly the shared definition's procedure: a queen is placed on every row, and a branch is cut on the spot if there is a conflict. Symmetry breaking is added **on top of** this. - **CP32.** Symmetry breaking is built with a single constraint: the queen in the **first row can only be placed in the first half of the board**. With an odd number of columns, the middle column belongs to that half. - **CP33.** The oracle is the **solution set** produced by the unrestricted pruned traversal. Solutions coming from the half board are mirrored and compared against this set; set equality is tested exactly. - **CP34.** The board's symmetry group has eight elements: four quarter-turns and the mirror of each. A solution's equivalence class consists of the distinct solutions these eight transformations produce. - **CP35.** The measure is **steps**, and a step is a node visited in the search tree. - **CP36.** Board size is kept between 5 and 9; large n is conveyed **by counting**, not by running it. **This lesson's input does not come from the generator:** the only input is board size, and every number is exhaustive enumeration. In this lesson, the second-pool rule is replaced by a **board-size sweep**; every row is an independent run, and no value depends on a seed. - **CP37.** Finding all solutions and finding **one** solution are measured separately. They are two different questions about the same problem, and their costs are not comparable. - **CP38.** Verifying a candidate is counted separately: every pair of queens is compared. - **CP39.** The second constraint, forward checking, is independent of symmetry breaking. What the two contribute together is compared against the product of what they contribute separately; equality is not assumed, it is measured. ## Measuring Symmetry Breaking Once a solution is found, its mirror image is also a solution. The same holds for quarter-turns. This means part of the search is **redundant**: every solution found by placing the first queen in the right half is the mirror of a solution found by placing it in the left half. The block below adds the constraint, places the two traversals' node counts side by side, compares the set restored by mirroring against the oracle's set, and counts the equivalence classes. ```python class Counter: def __init__(self): self.steps = 0 def count(self): self.steps += 1 def queens(n, half_first=False): """The shared definition's pruned backtracking; half_first adds symmetry breaking.""" s = Counter() solutions = [] def walk(row, placed): s.count() if row == n: solutions.append(tuple(placed)) return top = (n + 1) // 2 if (half_first and row == 0) else n for col in range(top): if any(col == y or abs(col - y) == row - i for i, y in enumerate(placed)): continue placed.append(col) walk(row + 1, placed) placed.pop() walk(0, []) return s.steps, solutions def mirror(c, n): return tuple(n - 1 - x for x in c) def rotate(c, n): new = [0] * n for i, x in enumerate(c): new[x] = n - 1 - i return tuple(new) def orbit(c, n): """All images of a solution under the eight transformations.""" group, d = set(), c for _ in range(4): group.add(d) group.add(mirror(d, n)) d = rotate(d, n) return group print(" n | full nodes | full solutions | half nodes | half solutions | node ratio" " | mirrored | fundamental solutions | smallest class") for n in (5, 6, 7, 8, 9): d1, c1 = queens(n) d2, c2 = queens(n, half_first=True) restored = set(c2) | {mirror(c, n) for c in c2} full = set(c1) fundamental, seen, smallest = 0, set(), 99 for c in sorted(full): if c in seen: continue k = orbit(c, n) seen |= k fundamental += 1 smallest = min(smallest, len(k)) print(f"{n:2d} | {d1:9d} | {len(c1):9d} | {d2:11d} | {len(c2):11d} |" f" {round(d1 / d2, 2):11} | {'same' if restored == full else 'DIFFERENT':12s}" f" | {fundamental:11d} | {smallest:14d}") ``` ``` n | full nodes | full solutions | half nodes | half solutions | node ratio | mirrored | fundamental solutions | smallest class 5 | 54 | 10 | 32 | 6 | 1.69 | same | 2 | 2 6 | 153 | 4 | 77 | 2 | 1.99 | same | 1 | 4 7 | 552 | 40 | 316 | 23 | 1.75 | same | 6 | 4 8 | 2057 | 92 | 1029 | 46 | 2.0 | same | 12 | 4 9 | 8394 | 352 | 4704 | 203 | 1.78 | same | 46 | 4 ``` ## The Size and Kind of the Gain The first column confirms the shared definition's numbers: 54, 153, 552, 2057. Once the symmetry constraint is added, the node count at eight queens drops from 2057 to **1029**, a ratio of **2.00**. At five queens, 1.69; at six, 1.99; at seven, 1.75; at nine, 1.78. In none of the five rows does the ratio exceed 2. The mirroring column is the oracle comparison. Adding the mirror images to the solutions coming from the half board gives a set that is **the same on all five board sizes** as the unrestricted search's solution set. Symmetry breaking is not an approximate solution: no solution is lost, only the way it is found changes. This is a rare case in this course's measurements — the pattern splits from the oracle on no input at all. This gain should now be placed alongside the shared definition's pruning gain. | n | unpruned (shared definition) | pruned | pruning ratio | half board | symmetry ratio | |---|---|---|---|---|---| | 5 | 3,906 | 54 | 72.3 | 32 | 1.69 | | 6 | 55,987 | 153 | 365.9 | 77 | 1.99 | | 7 | 960,800 | 552 | 1740.6 | 316 | 1.75 | | 8 | 16,777,216 placements | 2057 | 8156.2 | 1029 | 2.00 | The two columns are in the same unit but are **not the same kind**. The pruning ratio rises from 72.3 to 8156.2, meaning pruning's contribution grows as n grows. The symmetry ratio stays between 1.69 and 2.00 and does not grow; it cannot grow, because what is eliminated is **a fixed number of symmetries of the board**, and that number does not change with n. This distinction is part of the course's reading of measurement. A single number for an improvement is not enough; **what that number does as n grows** must be asked. A constraint that saves a thousand nodes at eight queens still saves only half at sixteen, and that half is still exponential. The shared definition's fourth reading said this about pruning: pruning's gain grows with scale, but **the result is still exponential**. In symmetry breaking, the gain does not even grow with scale. The fundamental-solution column gives a third number. At eight queens there are 92 solutions, but the number of equivalence classes is **12**. This is not 92 divided by 8: 92 divided by 8 is 11.5. The difference shows up in the smallest-class column. Some solutions map to **themselves** under a transformation, so their classes have four or two elements instead of eight. At five queens, the smallest class has 2 elements. Saying "divide by eight" when eliminating by symmetry is therefore wrong. ## Do Two Improvements Multiply Symmetry breaking restricts the **start** of the search. A second, independent constraint can be added on top: once a queen is placed, if one of the remaining rows has no open column left at all, that branch is cut immediately. This is called forward checking, and it does **not wait for the conflict to appear** — it looks ahead and cuts. The two improvements are independent of each other; what is to be asked is whether their gains multiply when used together. ```python class Counter: def __init__(self): self.steps = 0 def count(self): self.steps += 1 def conflicts(col, row, placed): return any(col == y or abs(col - y) == row - i for i, y in enumerate(placed)) def queens(n, half_first=False, look_ahead=False): """Two independent improvements: symmetry breaking and forward checking.""" s = Counter() count = 0 def walk(row, placed): nonlocal count s.count() if row == n: count += 1 return top = (n + 1) // 2 if (half_first and row == 0) else n for col in range(top): if conflicts(col, row, placed): continue placed.append(col) if not look_ahead or all(any(not conflicts(c, r, placed) for c in range(n)) for r in range(row + 1, n)): walk(row + 1, placed) placed.pop() walk(0, []) return s.steps, count print(" n | plain | symmetry | forward checking | both" " | product of separate | measured ratio") for n in (6, 7, 8, 9, 10): d0, _ = queens(n) d1, _ = queens(n, half_first=True) d2, _ = queens(n, look_ahead=True) d3, _ = queens(n, half_first=True, look_ahead=True) product = (d0 / d1) * (d0 / d2) print(f"{n:2d} | {d0:5d} | {d1:7d} | {d2:11d} | {d3:12d} |" f" {round(product, 2):16} | {round(d0 / d3, 2)}") ``` ``` n | plain | symmetry | forward checking | both | product of separate | measured ratio 6 | 153 | 77 | 87 | 44 | 3.49 | 3.48 7 | 552 | 316 | 334 | 187 | 2.89 | 2.95 8 | 2057 | 1029 | 1165 | 583 | 3.53 | 3.53 9 | 8394 | 4704 | 4720 | 2658 | 3.17 | 3.16 10 | 35539 | 17770 | 17489 | 8745 | 4.06 | 4.06 ``` The last two columns agree on all five rows: 3.49 against 3.48, 2.89 against 2.95, 3.53 against 3.53, 3.17 against 3.16, 4.06 against 4.06. The product of the separately measured gains comes out equal to the gain measured jointly. Because the two constraints touch **different parts** of the search, they do not repeat each other's work. This agreement is not a rule, it is a measured result; if the two constraints cut the same branches, the product would come out larger than the measured ratio, and the gap would be a **double-counted gain**. The measurement exists precisely to test this. Still, the combined ratio stays at 4.06. Three improvements were stacked, and the search space still grows exponentially with n; 8745 nodes at ten queens, and this number will multiply many times over again at twelve. **Even when constant factors are combined, the kind of growth does not change.** ## The Question Where Symmetry Buys Nothing The question asked so far was "all solutions." The same problem can also be asked with a different question: finding **one** solution. The two questions look at the same board, but their costs cannot be compared. ```python class Counter: def __init__(self): self.steps = 0 def count(self): self.steps += 1 def search(n, half_first=False, stop=False): """Pruned backtracking. stop=True halts at the first solution.""" s = Counter() found = [] def walk(row, placed): s.count() if stop and found: return if row == n: found.append(tuple(placed)) return top = (n + 1) // 2 if (half_first and row == 0) else n for col in range(top): if stop and found: return if any(col == y or abs(col - y) == row - i for i, y in enumerate(placed)): continue placed.append(col) walk(row + 1, placed) placed.pop() walk(0, []) return s.steps, found def verify(c, n): """A candidate solution is checked by comparing every pair of queens.""" steps = 0 for i in range(n): for j in range(i + 1, n): steps += 1 if c[i] == c[j] or abs(c[i] - c[j]) == j - i: return False, steps return True, steps print(" n | first solution | first solution half | all solutions | ratio | verification") for n in (5, 6, 7, 8, 9, 10): d1, b1 = search(n, stop=True) d2, _ = search(n, half_first=True, stop=True) d3, everything = search(n) ok, steps = verify(b1[0], n) print(f"{n:2d} | {d1:9d} | {d2:15d} | {d3:14d} | {d3 // d1:4d} |" f" {steps:3d} steps, correct {ok}") ``` ``` n | first solution | first solution half | all solutions | ratio | verification 5 | 6 | 6 | 54 | 9 | 10 steps, correct True 6 | 32 | 32 | 153 | 4 | 15 steps, correct True 7 | 10 | 10 | 552 | 55 | 21 steps, correct True 8 | 114 | 114 | 2057 | 18 | 28 steps, correct True 9 | 42 | 42 | 8394 | 199 | 36 steps, correct True 10 | 103 | 103 | 35539 | 345 | 45 steps, correct True ``` The second and third columns are **the same on all six of the six rows**. Symmetry breaking buys nothing when finding the first solution, because in the first solution the search finds, the first queen already sits in column zero, and that column is inside the constraint. The constraint closes off a region that was never going to be entered. This is the measured demonstration that improvements are **question-dependent**. The same constraint halves the node count exactly when all solutions are asked for, and buys zero when one solution is asked for. An improvement's value comes not from the procedure but from **the question asked**. The last two columns show a sharper difference. At ten queens, finding all solutions is 35,539 nodes, finding one solution is **103 nodes**, a ratio of 345. **Verifying** that a found candidate is correct, however, is only 45 steps: comparing every pair of queens. Searching, finding, and verifying are three separate costs, and the gap between them widens with board size. ## Summary - Symmetry breaking brings the node count at eight queens from 2057 down to 1029; the ratio stays between 1.69 and 2.00 across five board sizes. - The solution set restored by mirroring matches the oracle's set on all five sizes; no solution is lost. - Pruning's ratio rises from 72.3 to 8156.2, symmetry's ratio stays at 2: one is a gain that grows with n, the other a **constant-factor** gain. - The fundamental-solution count at eight queens is 12; dividing 92 by eight is wrong, because some solutions map to their own images and the smallest equivalence class has 4 elements. - Symmetry breaking buys nothing when a single solution is sought; the same constraint buys half in one question and zero in the other. ## Next Step In n-queens, the search space could be read directly off the board: one queen per row, n choices per queen. The next lesson moves to problems where the search space is **not given**. The knight's tour and the maze are defined on the same grid, but how many objects are scanned changes by a factor of thousands depending on how they are modeled. The question to ask will be: is the search space a property of the problem, or of the model.