N-Queens

Backtracking O(N!) O(N)

Places N queens on an N×N board so none attack each other, undoing placements the moment a conflict appears.

Board size

1/229

Start solving the 6×6 board from row 0.

InvariantEvery queen already on the board is safe from every other. A partial board is never illegal, only incomplete.

tryingplacedconflictbacktrack

n-queens.c

int safe(int board[], int row, int col) {
    for (int r = 0; r < row; r++) {
        if (board[r] == col) return 0;
        if (r - board[r] == row - col) return 0;
        if (r + board[r] == row + col) return 0;
    }
    return 1;
}
 
int solve(int board[], int row, int n) {
    if (row == n) return 1;   /* all queens placed */
    for (int col = 0; col < n; col++) {
        if (safe(board, row, col)) {
            board[row] = col;
            if (solve(board, row + 1, n)) return 1;
            board[row] = -1;   /* backtrack */
        }
    }
    return 0;
}

How N-Queens works

Place queens row by row. If a column/diagonal conflict appears, undo the latest placement and try the next column — pruning a whole subtree of doomed positions each time.

When to use it

The canonical constraint-satisfaction demo: placement problems with pairwise conflicts.