51. N-Queens

Hard

Problem Description

The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other.

Given an integer n, return all distinct solutions to the n-queens puzzle. Each solution contains a distinct board configuration of the n-queens' placement, where 'Q' and '.' both indicate a queen and an empty space, respectively.

Examples

Example 1:
Input: n = 4
Output: [[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
Explanation: There exist two distinct solutions to the 4-queens puzzle

Example 2:
Input: n = 1
Output: [["Q"]]
Jump to Solution: Python Java C++ JavaScript C#

Python Solution


def solveNQueens(n: int) -> List[List[str]]:
    def createBoard():
        board = []
        for i in range(n):
            row = ['.' for _ in range(n)]
            board.append(''.join(row))
        return board
    
    def backtrack(row, diagonals, anti_diagonals, cols, board):
        if row == n:
            result.append(board[:])
            return
        
        for col in range(n):
            curr_diagonal = row - col
            curr_anti_diagonal = row + col
            
            if (col in cols or 
                curr_diagonal in diagonals or 
                curr_anti_diagonal in anti_diagonals):
                continue
            
            cols.add(col)
            diagonals.add(curr_diagonal)
            anti_diagonals.add(curr_anti_diagonal)
            
            new_row = list(board[row])
            new_row[col] = 'Q'
            board[row] = ''.join(new_row)
            
            backtrack(row + 1, diagonals, anti_diagonals, cols, board)
            
            cols.remove(col)
            diagonals.remove(curr_diagonal)
            anti_diagonals.remove(curr_anti_diagonal)
            board[row] = '.' * n
    
    result = []
    board = createBoard()
    backtrack(0, set(), set(), set(), board)
    return result

Java Solution


class Solution {
    private List> result = new ArrayList<>();
    private int n;
    
    public List> solveNQueens(int n) {
        this.n = n;
        char[][] board = new char[n][n];
        for (int i = 0; i < n; i++) {
            Arrays.fill(board[i], '.');
        }
        
        backtrack(0, new HashSet<>(), new HashSet<>(), new HashSet<>(), board);
        return result;
    }
    
    private void backtrack(int row, Set diagonals, 
                         Set antiDiagonals, Set cols, 
                         char[][] board) {
        if (row == n) {
            List solution = new ArrayList<>();
            for (char[] rowArray : board) {
                solution.add(new String(rowArray));
            }
            result.add(solution);
            return;
        }
        
        for (int col = 0; col < n; col++) {
            int currDiagonal = row - col;
            int currAntiDiagonal = row + col;
            
            if (cols.contains(col) || 
                diagonals.contains(currDiagonal) || 
                antiDiagonals.contains(currAntiDiagonal)) {
                continue;
            }
            
            cols.add(col);
            diagonals.add(currDiagonal);
            antiDiagonals.add(currAntiDiagonal);
            board[row][col] = 'Q';
            
            backtrack(row + 1, diagonals, antiDiagonals, cols, board);
            
            cols.remove(col);
            diagonals.remove(currDiagonal);
            antiDiagonals.remove(currAntiDiagonal);
            board[row][col] = '.';
        }
    }
}

C++ Solution


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

JavaScript Solution


/**
 * @param {number} n
 * @return {string[][]}
 */
var solveNQueens = function(n) {
    const result = [];
    const board = Array(n).fill().map(() => Array(n).fill('.'));
    
    const backtrack = (row, diagonals, antiDiagonals, cols) => {
        if (row === n) {
            result.push(board.map(row => row.join('')));
            return;
        }
        
        for (let col = 0; col < n; col++) {
            const currDiagonal = row - col;
            const currAntiDiagonal = row + col;
            
            if (cols.has(col) || 
                diagonals.has(currDiagonal) || 
                antiDiagonals.has(currAntiDiagonal)) {
                continue;
            }
            
            cols.add(col);
            diagonals.add(currDiagonal);
            antiDiagonals.add(currAntiDiagonal);
            board[row][col] = 'Q';
            
            backtrack(row + 1, diagonals, antiDiagonals, cols);
            
            cols.delete(col);
            diagonals.delete(currDiagonal);
            antiDiagonals.delete(currAntiDiagonal);
            board[row][col] = '.';
        }
    };
    
    backtrack(0, new Set(), new Set(), new Set());
    return result;
};

C# Solution


public class Solution {
    private IList> result = new List>();
    private int n;
    
    public IList> SolveNQueens(int n) {
        this.n = n;
        char[][] board = new char[n][];
        for (int i = 0; i < n; i++) {
            board[i] = new char[n];
            Array.Fill(board[i], '.');
        }
        
        Backtrack(0, new HashSet(), new HashSet(), 
                 new HashSet(), board);
        return result;
    }
    
    private void Backtrack(int row, HashSet diagonals, 
                         HashSet antiDiagonals, HashSet cols, 
                         char[][] board) {
        if (row == n) {
            IList solution = new List();
            for (int i = 0; i < n; i++) {
                solution.Add(new string(board[i]));
            }
            result.Add(solution);
            return;
        }
        
        for (int col = 0; col < n; col++) {
            int currDiagonal = row - col;
            int currAntiDiagonal = row + col;
            
            if (cols.Contains(col) || 
                diagonals.Contains(currDiagonal) || 
                antiDiagonals.Contains(currAntiDiagonal)) {
                continue;
            }
            
            cols.Add(col);
            diagonals.Add(currDiagonal);
            antiDiagonals.Add(currAntiDiagonal);
            board[row][col] = 'Q';
            
            Backtrack(row + 1, diagonals, antiDiagonals, cols, board);
            
            cols.Remove(col);
            diagonals.Remove(currDiagonal);
            antiDiagonals.Remove(currAntiDiagonal);
            board[row][col] = '.';
        }
    }
}

Complexity Analysis

Solution Explanation

This solution uses backtracking to find all valid N-Queens configurations. Here's how it works:

Key points: