51. N-Queens

Time: O(n!)

Space: O(n)

Intuition

Place one queen per row. For each row, try each column; a column is valid if no previously placed queen shares that column, positive diagonal (row-col = constant), or negative diagonal (row+col = constant). Three HashSets track conflicts in O(1).

Algorithm

1Backtrack row by row, starting at row 0.
2For each column col in [0, n-1]: skip if col, row-col, or row+col is already in the conflict sets.
3Place queen: add col to cols, row-col to posDiag, row+col to negDiag.
4Recurse on row+1. If row+1==n, record the current board.
5Remove the queen (backtrack).

Example Walkthrough

Input: n = 4

1.Row 0: try col 1 (valid). Row 1: col 3 (valid). Row 2: col 0 (valid). Row 3: col 2 (valid). Record [[".Q..","...Q","Q...","..Q."]].
2.Backtrack to find second solution: [["..Q.","Q...","...Q",".Q.."] ].

Output: 2 solutions

Common Pitfalls

•Track diagonals as row-col and row+col constants, not as slope comparisons.
•Build the board string only when a complete valid placement (row == n) is found.

51.cs

// Approach: Backtracking column by column. Use sets to track occupied rows
// and diagonals; record valid configurations as board strings.
// Time: O(n!) Space: O(n)

public class Solution
{
    public IList<IList<string>> SolveNQueens(int n)
    {
        IList<IList<string>> ans = new List<IList<string>>();
        char[][] board = new char[n][];

        for (int i = 0; i < n; i++)
        {
            char[] s = new char[n];
            Array.Fill(s, '.');
            board[i] = s;
        }

        Solve(0, board, ans, n);

        return ans;
    }

    private void Solve(int col, char[][] board, IList<IList<string>> ans, int n)
    {
        if (col == n)
        {
            ans.Add(construct(board));
            return;
        }

        for (int row = 0; row < n; row++)
        {
            if (isSafe(row, col, board, n))
            {
                board[row][col] = 'Q';
                Solve(col + 1, board, ans, n);
                board[row][col] = '.';
            }
        }
    }

    private IList<string> construct(char[][] board)
    {
        IList<string> res = new List<string>();
        for (int i = 0; i < board.Length; i++)
            res.Add(new String(board[i]));
        return res;
    }

    private bool isSafe(int row, int col, char[][] board, int n)
    {
        int r = row, c = col;
        // upper diagonal
        while (r >= 0 && c >= 0)
        {
            if (board[r][c] == 'Q')
                return false;
            r--;
            c--;
        }

        r = row;
        c = col;
        //left
        while (c >= 0)
        {
            if (board[r][c] == 'Q')
                return false;
            c--;
        }

        r = row;
        c = col;
        // lower diagonal
        while (r < n && c >= 0)
        {
            if (board[r][c] == 'Q')
                return false;
            r++;
            c--;
        }

        return true;
    }
}

Was this solution helpful?