Step 4 of 6

N-Queens

The classic backtracking puzzle: place n queens on an n × n chessboard so that no two attack each other. A queen attacks along its row, its column and both diagonals. For the ordinary 8 × 8 board there are 92 solutions.

Trying every placement of 8 queens on 64 squares means over 4 billion possibilities. Backtracking does far better by building a solution one row at a time: each row gets exactly one queen, so the only choice per row is the column. Before placing, check whether that square is attacked by a queen in an earlier row. If every column in the current row is attacked, this branch is dead: return and move the previous queen.

Checking attacks in O(1)

Instead of scanning the board, keep three sets of flags:

• col[c]: some queen is in column c.
• diag[r + c]: some queen is on this "/" diagonal. Along a / diagonal, row + column stays the same.
• anti[r - c + n - 1]: some queen is on this "" diagonal. Along it, row - column stays the same; adding n - 1 keeps the index from going negative.

#include <iostream>
#include <string>
#include <vector>

struct Board {
    int n;
    std::vector<int> queen_col;              // queen_col[r] = column of row r's queen
    std::vector<bool> col, diag, anti;
    int solutions = 0;

    explicit Board(int size)
        : n(size), queen_col(size), col(size), diag(2 * size - 1), anti(2 * size - 1) {}

    void place(int r) {
        if (r == n) {                        // a queen in every row
            solutions++;
            for (int row = 0; row < n; row++) {
                std::string line(n, '.');
                line[queen_col[row]] = 'Q';
                std::cout << line << "\n";
            }
            std::cout << "\n";
            return;
        }
        for (int c = 0; c < n; c++) {
            if (col[c] || diag[r + c] || anti[r - c + n - 1]) continue;   // attacked
            queen_col[r] = c;
            col[c] = diag[r + c] = anti[r - c + n - 1] = true;           // choose
            place(r + 1);                                                // explore
            col[c] = diag[r + c] = anti[r - c + n - 1] = false;          // un-choose
        }
    }
};

int main() {
    Board b(4);
    b.place(0);
    std::cout << b.solutions << " solutions\n";
}

.Q..
...Q
Q...
..Q.

..Q.
Q...
...Q
.Q..

2 solutions

How it works

• place(r) puts a queen somewhere in row r, given that rows 0 to r - 1 already hold safe queens. Reaching r == n means all rows are filled.
• A queen in the first row at column 0 fails for n = 4: every way of continuing gets stuck by row 3, so the search backs up and tries column 1. That backing up is where the name comes from.
• The three flag arrays are the only state, and un-choosing clears exactly the three flags that choosing set.

For n = 8 this explores about 2,000 partial boards instead of billions of full ones. The count grows quickly with n (724 solutions for n = 10, over 14,000 for n = 12), but the pruning keeps small boards instant.

Your turn: write count_queens(n), returning the number of solutions for an n × n board (1 ≤ n ≤ 10). Just count them; there's no need to print boards.

Previous: Pruning Next: Paths through a grid