N Queens Ii

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

                                            
class Solution {
    public int totalNQueens(int n) {
        List<List<String>> res = new ArrayList<>();
        char[][] board = new char[n][n];
        for (char[] row : board) {
            Arrays.fill(row, '.');
        }
        solveNQueens(board, 0, res);
        return res.size();
    }
    
    private void solveNQueens(char[][] board, int col, List<List<String>> res) {
        if (col == board.length) {
            res.add(construct(board));
            return;
        }
        for (int i = 0; i < board.length; i++) {
            if (isValid(board, i, col)) {
                board[i][col] = 'Q';
                solveNQueens(board, col + 1, res);
                board[i][col] = '.';
            }
        }
    }
    
    private boolean isValid(char[][] board, int row, int col) {
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < col; j++) {
                if (board[i][j] == 'Q' && (row == i || Math.abs(row - i) == Math.abs(col - j))) {
                    return false;
                }
            }
        }
        return true;
    }
    
    private List<String> construct(char[][] board) {
        List<String> list = new ArrayList<>();
        for (char[] row : board) {
            list.add(new String(row));
        }
        return list;
    }
}

                                            
class Solution(object):
    def totalNQueens(self, n):
        def backtrack(queens, xy_dif, xy_sum):
            p = len(queens)
            if p == n:
                output.append(queens)
                return None
            for q in range(n):
                if q not in queens and p-q not in xy_dif and p+q not in xy_sum:
                    backtrack(queens + [q], xy_dif + [p-q], xy_sum + [p+q])
        
        output = []
        backtrack([], [], [])
        return len(output)

                                            
int totalNQueens(int n) {
    int count = 0;
    
    backtrack(&count, n, 0, 0, 0, 0);
    
    return count;
}

void backtrack(int* count, int n, int row, int cols, int diags1, int diags2) {
    if (row == n) {
        (*count)++;
        return;
    }
    
    for (int i = 0; i < n; i++) {
        int col = 1 << i;
        int diag1 = 1 << (row + i);
        int diag2 = 1 << (row - i + n - 1);
        
        if ((cols & col) || (diags1 & diag1) || (diags2 & diag2)) {
            continue;
        }
        
        backtrack(count, n, row + 1, cols | col, diags1 | diag1, diags2 | diag2);
    }
}

                                            
public class Solution {
    public int TotalNQueens(int n) {
        if (n <= 0) return 0;

        int count = 0;
        int[] columns = new int[n];
        SolveNQueens(n, 0, columns, ref count);

        return count;
    }

    private void SolveNQueens(int n, int row, int[] columns, ref int count)
    {
        if (row == n)
        {
            count++;
            return;
        }

        for (int col = 0; col < n; col++)
        {
            columns[row] = col;
            if (IsValid(columns, row))
            {
                SolveNQueens(n, row + 1, columns, ref count);
            }
        }
    }

    private bool IsValid(int[] columns, int row)
    {
        for (int i = 0; i < row; i++)
        {
            if (columns[i] == columns[row] || Math.Abs(columns[i] - columns[row]) == row - i)
            {
                return false;
            }
        }
        return true;
    }
}

                                            
/**
 * @param {number} n
 * @return {number}
 */
var totalNQueens = function(n) {
    let count = 0;

    const isSafe = (board, row, col) => {
        for (let i = 0; i < row; i++) {
            if (board[i] === col || board[i] - col === i - row || board[i] - col === row - i) {
                return false;
            }
        }
        return true;
    };

    const solve = (board, row) => {
        if (row === n) {
            count++;
            return;
        }

        for (let col = 0; col < n; col++) {
            if (isSafe(board, row, col)) {
                board[row] = col;
                solve(board, row + 1);
                board[row] = undefined;
            }
        }
    };

    solve([], 0);

    return count;
};

                                            
function totalNQueens(n: number): number {
    let count = 0;
  
    const backtracking = (row: number, cols: number[], diag1: number[], diag2: number[]) => {
        if (row === n) {
            count++;
            return;
        }
        
        for (let col = 0; col < n; col++) {
            const d1 = row + col;
            const d2 = row - col + n - 1;
            
            if (!cols[col] && !diag1[d1] && !diag2[d2]) {
                cols[col] = 1;
                diag1[d1] = 1;
                diag2[d2] = 1;
                
                backtracking(row + 1, cols, diag1, diag2);
                
                cols[col] = 0;
                diag1[d1] = 0;
                diag2[d2] = 0;
            }
        }
    };
  
    backtracking(0, Array(n).fill(0), Array(2 * n - 1).fill(0), Array(2 * n - 1).fill(0));
    
    return count;
};

To solve this coding challenge, we need to determine the number of distinct solutions to the N-Queens puzzle, where n queens must be placed on an n x n chessboard such that no two queens threaten each other. Below is a comprehensive explanation of how to approach this problem using backtracking.

Explanation

The backtracking method is an ideal way to solve the N-Queens puzzle because it allows us to explore all possible arrangements of queens on the board while pruning invalid configurations early, ensuring efficiency.

Board Representation :

The board is implicitly represented as a list.
Each index represents a row on the board, and the value at each index represents the column where the queen is placed in that row.

Constraints :

A queen can attack another queen if it is in the same row, column, or diagonals.

Backtracking :

The method involves placing a queen in each row and checking if it’s safe to do so.
We keep track of which columns and diagonals are threatened by other queens. There are two diagonals to check: main diagonals (left-top to right-bottom) and anti-diagonals (left-bottom to right-top).

Check Validity :

For each position explored, we check if placing a queen there will violate any constraints:

Column constraint.
Main diagonal constraint.
Anti-diagonal constraint.

Detailed Steps in Pseudocode

Here's a step-by-step pseudocode with comments for clarity:

                                            
# Function to solve N-Queens problem
function solveNQueens(n):
# Initialize result to store the count of solutions
result = 0

# Function to perform backtracking
function backtrack(row, cols, diagonals1, diagonals2):
# If row equals n, it means we've placed queens in all rows successfully
if row == n:
# Increment the count of solutions
result += 1
return

# Iterate through each column
for col in range(0, n):
# Calculate the diagonal indices for current position
diag1 = row - col
diag2 = row + col

# Check if placing a queen in current column and diagonals is valid
if col not in cols and diag1 not in diagonals1 and diag2 not in diagonals2:
# Place the queen in the current position
cols.add(col)
diagonals1.add(diag1)
diagonals2.add(diag2)

# Proceed to place queen in the next row
backtrack(row + 1, cols, diagonals1, diagonals2)

# Remove the queen from the current position (backtrack)
cols.remove(col)
diagonals1.remove(diag1)
diagonals2.remove(diag2)

# Initialize backtracking from the first row with empty sets for columns and diagonals
backtrack(0, set(), set(), set())

# Return the number of solutions found
return result

Step-by-Step Explanation

Initialization :

We initialize the
result

variable to store the count of valid solutions.

Backtracking Function :

backtrack(row, cols, diagonals1, diagonals2)

:

row

: Current row index.
cols

: Set of column indices where queens are already placed.
diagonals1

: Set of indices for main diagonals where queens are already placed.
diagonals2

: Set of indices for anti-diagonals where queens are already placed.

Base Case :

If
row == n

, all queens are successfully placed, so we increment the result.

Iterate Through Columns :

For each column, we check if it is valid to place a queen based on the existing queens in
cols

,
diagonals1

, and
diagonals2

.

Recursive Placement :

If placement is valid, we:

Add the column and diagonals to the respective sets.
Call
backtrack

for the next row.
Remove the queen position afterward (backtrack).

Return Result :

The main function,
solveNQueens

, returns the number of distinct solutions.

By maintaining detailed checks and leveraging set operations for constraints, we efficiently explore and backtrack in the solution space to count all valid N-Queen arrangements.