Write a backtracking algorithm for the N-Queens problem.

Concept

Backtracking builds a solution one decision at a time. Whenever a partial choice violates a constraint or cannot lead to a complete solution, the algorithm undoes that choice and tries the next alternative.

For N-Queens, place one queen in each row. A placement is safe only when no earlier queen shares its column, main diagonal, or anti-diagonal.

Application and algorithm

1. Maintain three sets: usedColumns for occupied columns, usedMainDiagonals for values row minus column, and usedAntiDiagonals for values row plus column.

2. Start with row 0. For every column from 0 to N minus 1, test whether the column and both diagonal identifiers are absent from their sets.

3. If the position is safe, record the column for that row and add the three identifiers to the sets.

4. Recursively process the next row. When row equals N, all queens have been placed, so output or return the recorded arrangement.

5. If the recursive call does not complete a solution, remove the queen and the three identifiers. This undo operation is the backtracking step; then try the next column.

Pseudocode

procedure solve(row):
    if row = N:
        output position[0 ... N - 1]
        return true

    for col = 0 to N - 1:
        mainDiag = row - col
        antiDiag = row + col
        if col not in usedColumns
           and mainDiag not in usedMainDiagonals
           and antiDiag not in usedAntiDiagonals:
            position[row] = col
            add col, mainDiag, antiDiag to their sets
            if solve(row + 1):
                return true
            remove col, mainDiag, antiDiag from their sets

    return false

initialize empty sets and position[0 ... N - 1]
solve(0)

Concrete trace for N = 4

1. Trying row 0, column 0 leads first to row 1, column 2; row 2 then has no safe column, so the placement at row 1 is undone.

2. Continuing the search eventually tries row 0, column 1. The recursive choices row 1, column 3; row 2, column 0; and row 3, column 2 are all safe.

3. The recorded column array is [1, 3, 0, 2], which represents one queen in each row at those columns.

Cross-check and complexity

• In [1, 3, 0, 2], all column values are distinct. For every pair of rows, the absolute column difference is different from the row difference, so no two queens share a diagonal.

• The worst-case search explores permutations of columns and takes O(N!) time. The recursion, position array, and three sets use O(N) auxiliary space, excluding any stored output boards.

Thus, row-wise recursion with a safety test and an explicit undo step is a valid backtracking algorithm for the N-Queens problem.