N Queens

                                            
class Solution {
public:
    vector<vector<string>> solveNQueens(int n) {
        vector<vector<string>> res;
        vector<string> board(n, string(n, '.'));
        solve(res, board, 0);
        return res;
    }
    
    void solve(vector<vector<string>>& res, vector<string>& board, int row) {
        int n = board.size();
        if (row == n) {
            res.push_back(board);
            return;
        }
        
        for (int col = 0; col < n; col++) {
            if (isValid(board, row, col)) {
                board[row][col] = 'Q';
                solve(res, board, row + 1);
                board[row][col] = '.';
            }
        }
    }
    
    bool isValid(vector<string>& board, int row, int col) {
        int n = board.size();
        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;
    }
};

                                            
class Solution {
    public List<List<String>> solveNQueens(int n) {
        List<List<String>> res = new ArrayList<>();
        char[][] board = new char[n][n];
        for (int i = 0; i < n; i++) {
            Arrays.fill(board[i], '.');
        }
        backtrack(n, 0, board, res);
        return res;
    }
    
    private void backtrack(int n, int row, char[][] board, List<List<String>> res) {
        if (row == n) {
            List<String> tempList = new ArrayList<>();
            for (char[] rowArray : board) {
                tempList.add(String.valueOf(rowArray));
            }
            res.add(new ArrayList<>(tempList));
            return;
        }
        
        for (int col = 0; col < n; col++) {
            if (isValid(board, row, col, n)) {
                board[row][col] = 'Q';
                backtrack(n, row + 1, board, res);
                board[row][col] = '.';
            }
        }
    }
    
    private boolean isValid(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;
    }
}

                                            
class Solution:
    def solveNQueens(self, n):
        def solve(row, cols, diag1, diag2):
            if row == n:
                result.append([''.join(board[i]) for i in range(n)])
                return
            for col in range(n):
                if col in cols or row + col in diag1 or row - col in diag2:
                    continue
                board[row][col] = "Q"
                cols.add(col)
                diag1.add(row + col)
                diag2.add(row - col)
                solve(row + 1, cols, diag1, diag2)
                board[row][col] = "."
                cols.remove(col)
                diag1.remove(row + col)
                diag2.remove(row - col)
        
        result = []
        board = [['.' for _ in range(n)] for _ in range(n)]
        solve(0, set(), set(), set())
        return result

                                            
public class Solution {
    public IList<IList<string>> SolveNQueens(int n) {
        IList<IList<string>> result = new List<IList<string>>();
        char[][] board = new char[n][];
        for (int i = 0; i < n; i++) {
            board[i] = new char[n];
            for (int j = 0; j < n; j++) {
                board[i][j] = '.';
            }
        }
        SolveNQueensHelper(result, board, 0);
        return result;
    }

    private void SolveNQueensHelper(IList<IList<string>> result, char[][] board, int row) {
        if (row == board.Length) {
            IList<string> solution = new List<string>();
            foreach (var r in board) {
                solution.Add(new string(r));
            }
            result.Add(solution);
            return;
        }

        for (int col = 0; col < board.Length; col++) {
            if (IsSafe(board, row, col)) {
                board[row][col] = 'Q';
                SolveNQueensHelper(result, board, row + 1);
                board[row][col] = '.';
            }
        }
    }

    private bool IsSafe(char[][] board, int row, int col) {
        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 < board.Length; i--, j++) {
            if (board[i][j] == 'Q') {
                return false;
            }
        }
        return true;
    }
}

                                            
/**
 * @param {number} n
 * @return {string[][]}
 */
var solveNQueens = function(n) {
    const result = [];
    const board = Array.from({ length: n }, () => Array(n).fill('.'));
    
    const isValid = (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 < n; i--, j++) {
            if (board[i][j] === 'Q') return false;
        }
        
        for (let i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
            if (board[i][j] === 'Q') return false;
        }
        
        return true;
    };
    
    const backtrack = (row) => {
        if (row === n) {
            result.push(board.map(row => row.join('')));
        } else {
            for (let col = 0; col < n; col++) {
                if (isValid(row, col)) {
                    board[row][col] = 'Q';
                    backtrack(row + 1);
                    board[row][col] = '.';
                }
            }
        }
    };
    
    backtrack(0);
    
    return result;
};

                                            
function solveNQueens(n: number): string[][] {
    const result: string[][] = [];
    const board: string[][] = Array.from({ length: n }, () => Array(n).fill('.'));

    const isValid = (row: number, col: number): boolean => {
        for (let i = 0; i < row; i++) {
            if (board[i][col] === 'Q') return false;
            const diagonal1 = col - (row - i);
            if (diagonal1 >= 0 && board[i][diagonal1] === 'Q') return false;
            const diagonal2 = col + (row - i);
            if (diagonal2 < n && board[i][diagonal2] === 'Q') return false;
        }
        return true;
    };

    const backtrack = (row: number): void => {
        if (row === n) {
            result.push(board.map(row => row.join('')));
            return;
        }

        for (let col = 0; col < n; col++) {
            if (isValid(row, col)) {
                board[row][col] = 'Q';
                backtrack(row + 1);
                board[row][col] = '.';
            }
        }
    };

    backtrack(0);

    return result;
};

                                            
class Solution {
    /**
     * @param Integer $n
     * @return String[][]
     */
    function solveNQueens($n) {
        $result = [];
        $board = array_fill(0, $n, str_repeat('.', $n));

        $this->backtrack($result, $board, 0, $n);

        return $result;
    }

    function backtrack(&$result, &$board, $row, $n) {
        if ($row == $n) {
            $temp = [];
            foreach ($board as $r) {
                $temp[] = $r;
            }
            $result[] = $temp;
            return;
        }

        for ($i = 0; $i < $n; $i++) {
            if ($this->isValid($board, $row, $i, $n)) {
                $board[$row][$i] = 'Q';
                $this->backtrack($result, $board, $row + 1, $n);
                $board[$row][$i] = '.';
            }
        }
    }

    function isValid(&$board, $row, $col, $n) {
        for ($i = 0; $i < $row; $i++) {
            if ($board[$i][$col] == 'Q') return false;
        }

        for ($i = $row - 1, $j = $col - 1; $i >= 0 && $j >= 0; $i--, $j--) {
            if ($board[$i][$j] == 'Q') return false;
        }

        for ($i = $row - 1, $j = $col + 1; $i >= 0 && $j < $n; $i--, $j++) {
            if ($board[$i][$j] == 'Q') return false;
        }

        return true;
    }
}

                                            
class Solution {
    fun solveNQueens(n: Int): List<List<String>> {
        val result = mutableListOf<List<String>>()
        val col = BooleanArray(n)
        val diag1 = BooleanArray(2 * n - 1)
        val diag2 = BooleanArray(2 * n - 1)
        val board = Array(n) { CharArray(n) { '.' } }
        
        fun placeQueens(row: Int) {
            if (row == n) {
                result.add(board.map { it.joinToString("") })
                return
            }
            for (i in 0 until n) {
                if (col[i] || diag1[row + i] || diag2[row - i + n - 1]) continue
                col[i] = true
                diag1[row + i] = true
                diag2[row - i + n - 1] = true
                board[row][i] = 'Q'
                placeQueens(row + 1)
                col[i] = false
                diag1[row + i] = false
                diag2[row - i + n - 1] = false
                board[row][i] = '.'
            }
        }
        
        placeQueens(0)
        return result
    }
}

                                            
func solveNQueens(n int) [][]string {
    solutions := [][]string{}
    cols := make([]bool, n)
    diagonal1 := make([]bool, 2*n-1)
    diagonal2 := make([]bool, 2*n-1)
    board := make([]string, n)
    for i := range board {
        board[i] = strings.Repeat(".", n)
    }

    var backtrack func(row int)
    backtrack = func(row int) {
        if row == n {
            tmp := make([]string, n)
            copy(tmp, board)
            solutions = append(solutions, tmp)
            return
        }

        for col := 0; col < n; col++ {
            id1 := row - col + n - 1
            id2 := row + col
            if cols[col] || diagonal1[id1] || diagonal2[id2] {
                continue
            }

            cols[col], diagonal1[id1], diagonal2[id2] = true, true, true
            board[row] = board[row][:col] + "Q" + board[row][col+1:]
            backtrack(row + 1)
            board[row] = board[row][:col] + "." + board[row][col+1:]
            cols[col], diagonal1[id1], diagonal2[id2] = false, false, false
        }
    }

    backtrack(0)
    return solutions
}

                                            
# @param {Integer} n
# @return {String[][]}
def solve_n_queens(n)
    result = []
    cols = Array.new(n, false)
    diag1 = Array.new(2 * n - 1, false)
    diag2 = Array.new(2 * n - 1, false)
    board = Array.new(n) { Array.new(n, '.') }

    backtrack(0, n, board, cols, diag1, diag2, result)
    result
end

def backtrack(row, n, board, cols, diag1, diag2, result)
    if row == n
        result << board.map { |row| row.join('') }
        return
    end

    (0...n).each do |col|
        id1 = n - 1 + row - col
        id2 = row + col
        next if cols[col] || diag1[id1] || diag2[id2]

        cols[col] = true
        diag1[id1] = true
        diag2[id2] = true
        board[row][col] = 'Q'

        backtrack(row + 1, n, board, cols, diag1, diag2, result)

        cols[col] = false
        diag1[id1] = false
        diag2[id2] = false
        board[row][col] = '.'
    end
end

To solve this coding challenge of the N-Queens problem, we need to place n queens on an n x n chessboard such that no two queens can attack each other. This means no two queens can share the same row, column, or diagonal. We aim to find all possible and distinct solutions and represent them in the specified format. The problem requires both a deep understanding of the constraints imposed by queens' movements and an efficient algorithm to explore all possible configurations.

Explanation:

Step-by-Step Explanation

Initialization : We start by initializing an empty
result

list to store all valid board configurations. We also prepare an empty
board

, which is an n x n matrix filled with '.' representing empty spaces.
Recursive Function : We define a recursive function
solve(row, cols, diag1, diag2)

to place queens row by row.

Base Case : If
row

equals
n

, it means we've successfully placed n queens. Convert the current board configuration into a list of strings and append it to
result

.
Iterate Through Columns : For the current row, we iterate through each column to determine safe positions:

Conflict Checks : Use
cols

,
diag1

, and
diag2

sets to check if the current column or diagonal positions are already attacked by other queens.

cols

keeps track of columns already occupied by queens.
diag1

keeps track of the difference between row and column (r - c), representing the '\' diagonal.
diag2

keeps track of the sum of row and column (r + c), representing the '/' diagonal.

Place Queen : If it’s a safe position, place a queen (‘Q’) on the board, add the column and diagonals to respective sets, and recursively call
solve

for the next row.
Backtrack : If placing the queen leads to no solution in subsequent steps, backtrack by removing the queen ('Q') and removing the column and diagonals from respective sets to restore the state.

Starting the Process : Begin the process by calling
solve(0, set(), set(), set())

from the first row.
Return Result : After exploring all possibilities, return the
result

list containing all the valid board configurations.

Detailed Steps in Pseudocode

Step 1: Initialization

                                            
# Create an empty result list to store all valid configurations
result = []

# Create an empty n x n board filled with '.'
board = [[ '.' for _ in range(n) ] for _ in range(n)]

Step 2: Define the Recursive Function

                                            
# Define the recursive function to solve the N-Queens problem
def solve(row, cols, diag1, diag2):
    # Check if we have placed queens in all rows
    if row == n:
        # Convert the board to the required format and add to the result list
        result.append([''.join(board[i]) for i in range(n)])
        return
    
    # Iterate through all columns of the current row
    for col in range(n):
        # Check if placing a queen at (row, col) is safe
        if col in cols or (row + col) in diag1 or (row - col) in diag2:
            continue
        
        # Place the queen at (row, col)
        board[row][col] = 'Q'
        
        # Add the column and diagonals to the sets
        cols.add(col)
        diag1.add(row + col)
        diag2.add(row - col)
        
        # Recurse to place the next queen in the next row
        solve(row + 1, cols, diag1, diag2)
        
        # Backtrack by removing the queen
        board[row][col] = '.'
        cols.remove(col)
        diag1.remove(row + col)
        diag2.remove(row - col)

Step 3: Start the Recursive Process

                                            
# Start the solving process from the first row
solve(0, set(), set(), set())

Step 4: Return the Result

                                            
# Return all the configurations
return result

Through this detailed explanation and pseudocode, we attend to the objective of solving the N-Queens problem methodically and ensure we capture each step required, from initialization through recursive backtracking to final solution collection.