52. N-Queens II - LeetcodeSolve

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:

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

: :

View Leetcode Problem

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;
    }
}

Code Editor (Testing phase)

Improve Your Solution

Use the editor below to refine the provided solution. Select a programming language and try the following:

Add import statement if required.
Optimize the code for better time or space complexity.
Add test cases to validate edge cases and common scenarios.
Handle error conditions or invalid inputs gracefully.
Experiment with alternative approaches to deepen your understanding.

Click "Run Code" to execute your solution and view the output. If errors occur, check the line numbers and debug accordingly. Resize the editor by dragging its bottom edge.