Two classic puzzles show how much good pruning matters. Both follow the same template from the previous lesson: choose, explore, undo.

N-Queens

Place n queens on an n x n board so that no two share a row, a column or a diagonal. Every row holds exactly one queen, so we fill rows one by one and choose a column. Conflicts are checked in O(1) with three sets:

  • cols: used columns;
  • diag1: values of row - col (one diagonal direction);
  • diag2: values of row + col (the other direction).
4x4 board with one solution of 4-Queens and the column and diagonal sets
4x4 board with one solution of 4-Queens and the column and diagonal sets

All cells of one diagonal share the same row - col (or row + col), which is why a set lookup is enough.

python
def solve_queens(n):
    cols, diag1, diag2 = set(), set(), set()
    placement, solutions = [], []