N-Queens
Place n queens on an n × n chessboard so that no two queens attack each other (share a row, column or diagonal). Return every distinct arrangement as a list of board rows.
- 1 ≤ n ≤ 9
- Enumerate all valid configurations — search with pruning
- One queen per row, so decisions are per row
- Attacks are detected via column and diagonal sets
Enumerating every arrangement is exponential, so tiny bounds plus "all" or "any valid" wording mean search the decision tree: choose, recurse, un-choose. Pruning invalid partial states early (a queen already attacked, a sum already exceeded) is what makes it practical.
Place queens row by row. For the current row, try each column that is not in the used-columns set and whose diagonals r - c and r + c are unused. Mark the sets, recurse to the next row, then unmark to try the next column. When all n rows are filled, record the board. Pruning at the first conflict keeps the search far below n^n.
- Bitmask versions represent the three constraint sets as integers for speed. For counting only, symmetry reduces the work by roughly half.