51. N-Queens - Leetcode Solution

Code Implementation

class Solution:
    def solveNQueens(self, n: int):
        def backtrack(row, cols, diagonals1, diagonals2, board, res):
            if row == n:
                res.append([''.join(r) for r in board])
                return
            for col in range(n):
                if col in cols or (row - col) in diagonals1 or (row + col) in diagonals2:
                    continue
                cols.add(col)
                diagonals1.add(row - col)
                diagonals2.add(row + col)
                board[row][col] = 'Q'
                backtrack(row + 1, cols, diagonals1, diagonals2, board, res)
                board[row][col] = '.'
                cols.remove(col)
                diagonals1.remove(row - col)
                diagonals2.remove(row + col)
        res = []
        board = [['.' for _ in range(n)] for _ in range(n)]
        backtrack(0, set(), set(), set(), board, res)
        return res

class Solution {
public:
    vector<vector<string>> solveNQueens(int n) {
        vector<vector<string>> res;
        vector<string> board(n, string(n, '.'));
        unordered_set<int> cols, diag1, diag2;
        backtrack(0, n, cols, diag1, diag2, board, res);
        return res;
    }
    void backtrack(int row, int n, unordered_set<int>& cols, unordered_set<int>& diag1, unordered_set<int>& diag2,
                   vector<string>& board, vector<vector<string>>& res) {
        if (row == n) {
            res.push_back(board);
            return;
        }
        for (int col = 0; col < n; ++col) {
            if (cols.count(col) || diag1.count(row - col) || diag2.count(row + col)) continue;
            cols.insert(col);
            diag1.insert(row - col);
            diag2.insert(row + col);
            board[row][col] = 'Q';
            backtrack(row + 1, n, cols, diag1, diag2, board, res);
            board[row][col] = '.';
            cols.erase(col);
            diag1.erase(row - col);
            diag2.erase(row + col);
        }
    }
};

class Solution {
    public List<List<String>> solveNQueens(int n) {
        List<List<String>> res = new ArrayList<>();
        char[][] board = new char[n][n];
        for (char[] row : board) Arrays.fill(row, '.');
        backtrack(0, n, new HashSet<>(), new HashSet<>(), new HashSet<>(), board, res);
        return res;
    }
    private void backtrack(int row, int n, Set<Integer> cols, Set<Integer> diag1, Set<Integer> diag2,
                           char[][] board, List<List<String>> res) {
        if (row == n) {
            List<String> solution = new ArrayList<>();
            for (char[] r : board) solution.add(new String(r));
            res.add(solution);
            return;
        }
        for (int col = 0; col < n; ++col) {
            if (cols.contains(col) || diag1.contains(row - col) || diag2.contains(row + col)) continue;
            cols.add(col);
            diag1.add(row - col);
            diag2.add(row + col);
            board[row][col] = 'Q';
            backtrack(row + 1, n, cols, diag1, diag2, board, res);
            board[row][col] = '.';
            cols.remove(col);
            diag1.remove(row - col);
            diag2.remove(row + col);
        }
    }
}

var solveNQueens = function(n) {
    const res = [];
    const board = Array.from({length: n}, () => Array(n).fill('.'));
    function backtrack(row, cols, diag1, diag2) {
        if (row === n) {
            res.push(board.map(r => r.join('')));
            return;
        }
        for (let col = 0; col < n; ++col) {
            if (cols.has(col) || diag1.has(row - col) || diag2.has(row + col)) continue;
            cols.add(col);
            diag1.add(row - col);
            diag2.add(row + col);
            board[row][col] = 'Q';
            backtrack(row + 1, cols, diag1, diag2);
            board[row][col] = '.';
            cols.delete(col);
            diag1.delete(row - col);
            diag2.delete(row + col);
        }
    }
    backtrack(0, new Set(), new Set(), new Set());
    return res;
};

Problem Description

The N-Queens problem requires you to place n queens on an n x n chessboard so that no two queens threaten each other. In chess, a queen can attack any other piece in the same row, column, or diagonal. Your task is to return all distinct solutions to the n-queens puzzle, where each solution is represented as a list of strings. Each string represents a row, with 'Q' indicating a queen and '.' indicating an empty space. The goal is to find all valid configurations, not just one. Each queen must occupy a unique row and column, and no two queens can share a diagonal.

Thought Process

At first glance, you might think of trying every possible way to place queens on the board. However, with n rows and n columns, the number of possible arrangements grows very quickly (exponentially). Placing queens randomly and checking for conflicts is inefficient and impractical. To make the problem manageable, we can use backtracking. This means we build the solution row by row, placing a queen in each row only if it doesn't conflict with any previously placed queens. If we get stuck (no valid columns in a row), we back up and try a different position for the last queen. By keeping track of which columns and diagonals are already occupied, we avoid unnecessary checks and speed up our search.

Solution Approach

The solution uses backtracking with efficient conflict detection:

Step 1: Start with an empty board and attempt to place a queen in the first row.
Step 2: For each column in the current row, check if placing a queen there would conflict with any queens already placed in previous rows. We check three things:
- Is the column already occupied?
- Is the main diagonal (row - col) already occupied?
- Is the anti-diagonal (row + col) already occupied?
Step 3: If the spot is safe, place the queen, mark the column and diagonals as occupied, and move to the next row.
Step 4: If we reach the end (all rows filled), save the current board as a solution.
Step 5: If we can't place a queen in a row, backtrack: remove the last queen, unmark the column and diagonals, and try the next possible spot.

We use sets (or arrays) to track which columns and diagonals are already used. This allows us to check for conflicts in constant time, making the algorithm much faster than brute-force.

Example Walkthrough

Let's walk through the case where n = 4:

Row 0: Try placing a queen in each column.
- Place queen at (0, 1). Mark column 1, diagonal -1, and anti-diagonal 1 as used.
Row 1: Try each column.
- Column 1 is taken. Try column 3: it's safe. Place queen at (1, 3).
Row 2: Try each column.
- Columns 1 and 3 are taken. Only column 0 is safe. Place queen at (2, 0).
Row 3: Only column 2 is safe. Place queen at (3, 2).
All rows are filled: we've found a solution! The board looks like:
```
. Q . .
. . . Q
Q . . .
. . Q .
      
```
Backtrack and try other possibilities to find all solutions.

This process continues until all configurations are tried.

Time and Space Complexity

Brute-force approach: There are n^n possible ways to place queens, since each of the n rows could have a queen in any of n columns. This is extremely inefficient.
Optimized (backtracking) approach: We only try valid placements, pruning branches early. The number of valid solutions is much smaller than n^n. The time complexity is O(n!), since for each row, we have fewer and fewer valid columns to choose from as we go deeper.
Space complexity: O(n^2) for storing the board, plus O(n) for tracking columns and diagonals, and O(n) recursion stack depth.

Summary

The N-Queens problem is a classic example of using backtracking to explore all valid configurations efficiently. By placing one queen per row and using sets to track columns and diagonals, we avoid unnecessary work and ensure no two queens threaten each other. This method is both elegant and efficient, transforming an exponential brute-force search into a manageable recursive solution.

AlgoMap.io

Want Help Cracking FAANG?