A permutation arranges every member of a finite set exactly once. In the N queens search, valid inputs are permutations of the integers from 0 through N−1, encoding one distinct column position for each row. section 8.3.1
Reducing the N queens search space
Encoding each row by its queen’s column initially gives N^N possible inputs. Restricting inputs to permutations removes repeated columns, reducing the space to N!. For N = 4, the space falls from 256 to 24 and the optimal Grover iteration count from 9 to 3, although preparing the equal superposition becomes harder. section 8.3.1
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.
Use the board encoding to see how one integer per row represents a candidate permutation and avoids multiple queens in one row. section 8.3.1
