LeetCode 52: N-Queens II

Explanation:

To solve the N-Queens II problem, we can utilize backtracking. The goal is to place N queens on an N x N chessboard such that no two queens attack each other. We can use recursion to explore all possible placements of queens on each row and backtrack when a solution is not valid.

Algorithm:

1. Create a board of size N x N to represent the chessboard.
2. Define a helper method that takes the current row as a parameter.
3. In the helper method, iterate through each column in the current row and try to place a queen.
4. Check if the placement is valid by ensuring no queens are attacking each other horizontally, vertically, or diagonally.
5. If the placement is valid, mark the cell as a queen and recursively move to the next row.
6. If all rows are filled without conflicts, increment the count of valid solutions.
7. Backtrack by removing the queen and continue exploring other placements.
8. Return the count of valid solutions.

Time Complexity:

The time complexity of this approach is O(N!) where N is the number of queens or the size of the chessboard.

Space Complexity:

The space complexity is O(N) for storing the board and the recursive call stack.

: :

class Solution {
    int count = 0;
    
    public int totalNQueens(int n) {
        char[][] board = new char[n][n];
        for (char[] row : board) {
            Arrays.fill(row, '.');
        }
        solveNQueens(board, 0);
        return count;
    }
    
    private void solveNQueens(char[][] board, int row) {
        if (row == board.length) {
            count++;
            return;
        }
        
        for (int col = 0; col < board.length; col++) {
            if (isValid(board, row, col)) {
                board[row][col] = 'Q';
                solveNQueens(board, row + 1);
                board[row][col] = '.';
            }
        }
    }
    
    private boolean isValid(char[][] board, int row, int col) {
        for (int i = 0; i < row; i++) {
            if (board[i][col] == 'Q') return false;
            int diff = row - i;
            if (col - diff >= 0 && board[i][col - diff] == 'Q') return false;
            if (col + diff < board.length && board[i][col + diff] == 'Q') return false;
        }
        return true;
    }
}