Represent an N×N chessboard with N² binary bits: 1 marks a queen, and 0 marks an empty cell. The encoding imposes no placement constraints, so a validity function must check them separately. section 8.1
Check candidate placements by testing pairs of cells that share:
- A row or column: together, these produce N²(N−1) same-line pairs. section 8.1
- A diagonal: both diagonal directions produce N(N−1)(2N−1)/3 same-line pairs. section 8.1
- Reversible implementations may require additional bits for intermediate constraint checks, roughly one bit per checked constraint. section 8.1
Figure 8.3 The naive input encoding uses one bit per board cell. This bit is 1 if there is a queen in this cell and 0 if the cell is empty.
Visualizes the one-bit-per-cell layout and the meaning of the two binary values. section 8.1
