N-Queens hard

Problem Statement

The N-Queens problem is to place N chess queens on an N×N chessboard such that no two queens threaten each other. This means that no two queens can share the same row, column, or diagonal.

Example 1

Input: n = 4

Output: [["Q",".",".","."],[".",".","Q","."],["..","Q",".","."],[".",".",".","Q"]]

Explanation: There exist two distinct solutions to the 4-queens puzzle as shown below,

[
 [".Q..",  // Solution 1
  "...Q",
  "Q...",
  "..Q."],

 ["..Q.",  // Solution 2
  "Q...",
  "...Q",
  ".Q.."]
]

Example 2

Input: n = 1 Output: [["Q"]]

Steps

1. Backtracking: We use a backtracking algorithm to explore all possible placements of queens.
2. Board Representation: We represent the chessboard using a single array cols where cols[i] stores the column index of the queen placed in row i. If no queen is placed in row i, cols[i] will be -1.
3. Is Safe Function: We create a helper function isSafe to check if placing a queen at (row, col) is safe (doesn't conflict with existing queens). This involves checking rows, columns, and diagonals.
4. Recursive Solve: The main function solveNQueens recursively places queens row by row. For each row, it iterates through columns, checking if placing a queen at that column is safe. If safe, it places the queen, recursively calls itself for the next row, and then backtracks (removes the queen) if the recursive call fails.
5. Result Formatting: Once a solution is found, it is formatted into a 2D array of strings ("Q" for queen, "." for empty) and added to the result list.

Explanation

The backtracking algorithm systematically explores all possible placements of queens. The isSafe function ensures that no two queens threaten each other. The recursive nature allows us to efficiently explore the solution space without explicitly generating all possible board configurations. Backtracking is crucial because when a placement is unsafe, we immediately undo it and try a different placement, avoiding unnecessary computation.

Code

function solveNQueens(n: number): string[][] {
    const result: string[][][] = [];
    const cols: number[] = new Array(n).fill(-1); // Initialize board

    function isSafe(row: number, col: number): boolean {
        for (let i = 0; i < row; i++) {
            // Check column and diagonals
            if (cols[i] === col || Math.abs(cols[i] - col) === row - i) {
                return false;
            }
        }
        return true;
    }

    function solve(row: number): void {
        if (row === n) {
            // Found a solution
            const board: string[][] = [];
            for (let i = 0; i < n; i++) {
                const rowStr: string[] = [];
                for (let j = 0; j < n; j++) {
                    rowStr.push(j === cols[i] ? "Q" : ".");
                }
                board.push(rowStr);
            }
            result.push(board);
            return;
        }

        for (let col = 0; col < n; col++) {
            if (isSafe(row, col)) {
                cols[row] = col; // Place queen
                solve(row + 1); // Recurse to next row
                cols[row] = -1; // Backtrack: remove queen
            }
        }
    }

    solve(0);
    return result.map(board=>board.map(row=>row.join(''))) //Convert 2d arrays into strings
};

Complexity

• Time Complexity: O(N!), where N is the size of the board. In the worst case, we explore all possible permutations of queen placements.
• Space Complexity: O(N) for the cols array and the recursion stack. The space used to store the results can also contribute to the space complexity, which is O(N^2 * k), where k is the number of solutions. For a typical N, the recursion stack space is relatively small in comparison to the result storage.