The N-queens problem asks for placements of N queens on an N × N chessboard such that no two attack each other. A valid placement therefore has no shared row, column, or diagonal. For four queens, there are two solutions, related by reflection; larger boards have more solutions and a harder search task. section 8.0
As a constraint-satisfaction search problem, it is defined by properties of acceptable placements rather than by a precomputed list of answers. A Grover-search solution must choose an input representation, prepare an equal superposition over its candidate inputs, and implement a marking oracle that recognizes valid placements. section 8.0
Three representations expose different tradeoffs:
- A naive board encoding uses one bit per cell, requiring N² bits. Its oracle must reject every attacking pair of cells in a common row, column, or diagonal; reversible checking can require extra workspace for intermediate constraints. section 8.1
- A restricted board encoding still uses one bit per cell, but prepares only states with exactly one queen in each row. The search space becomes a tensor product of row-wise W states, removing row-conflict checks from the oracle. section 8.2.1
- A compact row encoding stores each queen’s column index using ⌈log₂ N⌉ bits per row. It retains Nᴺ candidates with one queen per row while reducing the input register from N² to N⌈log₂ N⌉ bits; column and diagonal conflicts are checked between row pairs. section 8.3.1
Four queens
On a 4 × 4 board, a placement is valid only when every row and column contains one queen and no diagonal contains two. A cell-bit picture makes invalid cases visible: one can fail through a repeated column, another through a repeated diagonal. section 8.0
Figure 8.7 The new input encoding relies on the fact that only inputs in which each row has exactly one queen can be solutions to the puzzle. We represent each row of the board as just one integer, the column index of the queen in that row.
The row-index representation makes the key reduction concrete: each row is stored as one column number rather than as N separate cell bits. section 8.3.1
Encoding choices affect practical quantum cost. For N = 10, resource estimates compare the cell-bit and column-index approaches over the same Nᴺ search space; the compact encoding uses fewer estimated physical qubits and has a shorter estimated runtime. The comparison also cautions that these quantum approaches fare unfavorably against the classical solutions considered. section 9.5
