N-queens

The puzzle of placing N chess queens on an N-by-N board so that no two share a row, column or diagonal.

In more detail

Backtracking places one queen per row and prunes any column or diagonal already attacked. The standard 8-by-8 board has 92 solutions, and the count grows quickly with N. It is the classic demonstration of how much pruning saves over exhaustive search.

Related terms

Taught in

References