A constraint is a condition a candidate queen placement must satisfy. In the N-queens puzzle, no two queens may occupy the same row, column, or diagonal. With one bit per board cell, a reversible checking function must test every conflicting pair of cells and reject placements containing queens in both cells. section 8.1
Constraint checks can be organized as follows:
- Enumerate cell pairs sharing a row, column, or diagonal. section 8.1
- Require that no conflicting pair contains two queens. section 8.1
- Estimate additional reversible-workspace bits at roughly one per checked constraint, while recognizing implementation-dependent variation. section 8.1
Figure 8.4 To improve on our naive solution, we can count the number of queens in each row and each column and check that there is exactly one. We can do the same for the diagonals, checking that the number of queens in each diagonal is zero or one.
An alternative encoding counts queens in each row, column, and diagonal, requiring one per row and column and at most one per diagonal. section 8.1
