N-Queens Problem

Problem Statement

Place n queens on an n×n chessboard such that no two queens threaten each other (no shared row, column, or diagonal). Return all distinct solutions as board configurations. This hard-level problem uses backtracking to try every placement—picture a royal puzzle where queens must coexist peacefully!

Example

Input: n = 4

Output: [[".Q..","...Q","Q...","..Q."], ["..Q.","Q...","...Q",".Q.."]] (two valid 4×4 layouts)

Input: n = 1

Output: [["Q"]] (one queen on a 1×1 board)

Code

public class Solution {
    public List> solveNQueens(int n) {
        List> result = new ArrayList<>();
        char[][] board = new char[n][n];
        for (char[] row : board) Arrays.fill(row, '.');
        backtrack(result, board, 0, n);
        return result;
    }
    
    private void backtrack(List> result, char[][] board, int row, int n) {
        if (row == n) {
            result.add(buildBoard(board));
            return;
        }
        for (int col = 0; col < n; col++) {
            if (isSafe(board, row, col, n)) {
                board[row][col] = 'Q';
                backtrack(result, board, row + 1, n);
                board[row][col] = '.'; // Backtrack
            }
        }
    }
    
    private boolean isSafe(char[][] board, int row, int col, int n) {
        for (int i = 0; i < row; i++) if (board[i][col] == 'Q') return false;
        for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) if (board[i][j] == 'Q') return false;
        for (int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) if (board[i][j] == 'Q') return false;
        return true;
    }
    
    private List buildBoard(char[][] board) {
        List layout = new ArrayList<>();
        for (char[] row : board) layout.add(new String(row));
        return layout;
    }
}
            

def solve_n_queens(n):
    def backtrack(row):
        if row == n:
            result.append(["".join(r) for r in board])
            return
        for col in range(n):
            if is_safe(row, col):
                board[row][col] = "Q"
                backtrack(row + 1)
                board[row][col] = "."  # Backtrack
    
    def is_safe(row, col):
        for i in range(row):
            if board[i][col] == "Q":
                return False
        for i, j in zip(range(row-1, -1, -1), range(col-1, -1, -1)):
            if board[i][j] == "Q":
                return False
        for i, j in zip(range(row-1, -1, -1), range(col+1, n)):
            if board[i][j] == "Q":
                return False
        return True
    
    board = [["."] * n for _ in range(n)]
    result = []
    backtrack(0)
    return result

# Example usage
print(solve_n_queens(4))  # [[".Q..","...Q","Q...","..Q."], ["..Q.","Q...","...Q",".Q.."]]
print(solve_n_queens(1))  # [["Q"]]
            

function solveNQueens(n) {
    function backtrack(row) {
        if (row === n) {
            result.push(board.map(row => row.join("")));
            return;
        }
        for (let col = 0; col < n; col++) {
            if (isSafe(row, col)) {
                board[row][col] = "Q";
                backtrack(row + 1);
                board[row][col] = "."; // Backtrack
            }
        }
    }
    
    function isSafe(row, col) {
        for (let i = 0; i < row; i++) if (board[i][col] === "Q") return false;
        for (let i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) if (board[i][j] === "Q") return false;
        for (let i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) if (board[i][j] === "Q") return false;
        return true;
    }
    
    let board = Array(n).fill().map(() => Array(n).fill("."));
    let result = [];
    backtrack(0);
    return result;
}

// Example usage
console.log(solveNQueens(4)); // [[".Q..","...Q","Q...","..Q."], ["..Q.","Q...","...Q",".Q.."]]
console.log(solveNQueens(1)); // [["Q"]]
            

Explanation

• Base Case: When row equals n, a solution is complete—add the board layout.
• Backtracking: Place a queen in each column of the current row if safe, then recurse.
• Safety Check: Verify no conflicts in column, left diagonal, or right diagonal above.
• Flow Example (n=2): No solution (2×2 can’t fit 2 queens); n=4 yields complex patterns.
• Construction: Build strings from the board for each valid configuration.

Note