N-queens problem ($N$)

Place $N$ queens on an $N\times N$ chessboard so that none share a row, column or diagonal. One constraint satisfaction problem encoding uses a column variable $C_r\in \{1,\dots ,N\}$ for each row, with $C_r\ne C_s$ and $|C_r-C_s|\ne |r-s|$ whenever $r\ne s$. The pigeonhole principle explains why one queen per row loses no solutions. Prescribed occupied cells give the queens completion problem.

Complete a prescribed subset of occupied cells to a solution of the N-queens problem while retaining every prescribed queen. In a row-variable constraint satisfaction problem, a clue $(r,c)$ gives the singleton constraint domain $D_r=\{c\}$. Conflicting clues prove impossibility immediately, but nonattacking clues need not extend to a full solution. Backtracking decides the finite problem; hill climbing can search large candidate boards without an exhaustive guarantee.