N-Queens Problem with Backtracking Algorithm

Place N queens on an N×N chessboard so that no two queens threaten each other. No shared rows, columns, or diagonals.

This is the classic backtracking problem. It teaches you how to explore possibilities systematically and abandon dead ends early.

The intuition

Place queens one row at a time. For each row, try every column. Before placing, check if that position is safe — no queen already occupies the same column or diagonal. If safe, place the queen and move to the next row. If no column works, backtrack to the previous row and try the next option.

The code

function isSafe(board, row, col) {
    for (let i = 0; i < row; i++) {
        if (board[i] === col) return false;
        if (Math.abs(board[i] - col) === Math.abs(i - row)) return false;
    }
    return true;
}

function solveNQueens(n) {
    const results = [];
    const board = new Array(n).fill(-1);

    function backtrack(row) {
        if (row === n) {
            results.push([...board]);
            return;
        }

        for (let col = 0; col < n; col++) {
            if (isSafe(board, row, col)) {
                board[row] = col;
                backtrack(row + 1);
                board[row] = -1;
            }
        }
    }

    backtrack(0);
    return results;
}

How it works

The board array stores one value per row: the column where the queen is placed. board[2] = 4 means the queen in row 2 is in column 4.

The isSafe function checks all previously placed queens. Same column? Same diagonal? If either, the position is invalid.

When row === n, all queens are placed successfully. Record the solution and continue exploring for more.

Complexity

• Time: O(N!) — the branching factor decreases as queens are placed. Still exponential.
• Space: O(N) — the board array plus recursion stack depth.

Trade-offs

Backtracking is elegant but slow for large N. You can speed it up with constraint propagation — using sets to track occupied columns and diagonals, reducing the isSafe check to O(1). For N > 20 or so, even optimized backtracking gets slow. At that scale, you'd look at randomized or iterative repair algorithms.