The puzzle
The n queens problem asks you to place n chess queens on an n by n board so that none attacks another. Queens attack along rows, columns, and both diagonals, so no two may share any of those lines.
Row-by-row placement
Since each row holds exactly one queen, you decide one row at a time and only choose a column for it. That alone removes all row conflicts. For each candidate column you check three constraints before placing:
- The column is not already occupied.
- The anti-diagonal, identified by row plus column, is free.
- The main diagonal, identified by row minus column, is free.
Track these with three boolean sets so each check is constant time rather than a board scan.
Recursion and counting
Place a queen, mark its column and two diagonals, recurse to the next row, then unmark when backtracking. Reaching past the last row means a full valid placement, which you record or count. Symmetry tricks, like fixing the first queen to the left half, can roughly halve the work.
Key idea
Fixing one queen per row turns the puzzle into a column choice per row, and constant-time column and diagonal sets let you prune conflicts instantly instead of scanning the board.