LeetCode Hard — N-Queens II

The n-queens puzzle is the problem of placing n queens on an n x n chessboard such that no two queens attack each other.

Given an integer n, return the number of distinct solutions to the n-queens puzzle.

Example 1:

Input: n = 4 Output: 2 Explanation: There are two distinct solutions to the 4-queens puzzle as shown.

Example 2:Input: n = 1 Output: 1

Constraints:

• 1 <= n <= 9

Java Solution

You can solve the N-Queens problem to count the number of distinct solutions using a similar backtracking approach. Instead of storing the solutions, you can maintain a count. Here’s a Java solution for this problem:

public class NQueensCount {
    public static int totalNQueens(int n) {
        int[] count = new int[1];
        char[][] board = new char[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                board[i][j] = '.';
            }
        }
        totalNQueensHelper(board, 0, count);
        return count[0];
    }

    private static void totalNQueensHelper(char[][] board, int row, int[] count) {
        int n = board.length;
        if (row == n) {
            count[0]++;
            return;
        }

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

    private static boolean isValid(char[][] board, int row, int col) {
        int n = board.length;

        // Check if there is a queen in the same column
        for (int i = 0; i < row; i++) {
            if (board[i][col] == 'Q') {
                return false;
            }
        }

        // Check if there is a queen in the left diagonal
        for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
            if (board[i][j] == 'Q') {
                return false;
            }
        }

        // Check if there is a queen in the right diagonal
        for (int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {
            if (board[i][j] == 'Q') {
                return false;
            }
        }

        return true;
    }

    public static void main(String[] args) {
        int n1 = 4;
        System.out.println("N = " + n1 + ": " + totalNQueens(n1));

        int n2 = 1;
        System.out.println("N = " + n2 + ": " + totalNQueens(n2));
    }
}

This Java code uses a similar backtracking approach to count the number of distinct solutions for the N-Queens puzzle. The totalNQueens method returns the count of distinct solutions, and the totalNQueensHelper method recursively explores the possible configurations. The isValid method checks whether placing a queen at a specific position is valid or not.

Python Solution

def totalNQueens(n):
    def is_valid(board, row, col):
        # Check if there is a queen in the same column
        for i in range(row):
            if board[i][col] == 'Q':
                return False

        # Check if there is a queen in the left diagonal
        for i, j in zip(range(row - 1, -1, -1), range(col - 1, -1, -1)):
            if board[i][j] == 'Q':
                return False

        # Check if there is a queen in the right diagonal
        for i, j in zip(range(row - 1, -1, -1), range(col + 1, len(board))):
            if board[i][j] == 'Q':
                return False

        return True

    def total_nqueens_helper(board, row, count):
        n = len(board)
        if row == n:
            count[0] += 1
            return

        for col in range(n):
            if is_valid(board, row, col):
                board[row][col] = 'Q'
                total_nqueens_helper(board, row + 1, count)
                board[row][col] = '.'

    count = [0]
    board = [['.' for _ in range(n)] for _ in range(n)]
    total_nqueens_helper(board, 0, count)
    return count[0]

# Test cases
n1 = 4
print(f"N = {n1}: {totalNQueens(n1)}")

n2 = 1
print(f"N = {n2}: {totalNQueens(n2)}")

This Python code uses a similar backtracking approach to count the number of distinct solutions for the N-Queens puzzle. The totalNQueens function returns the count of distinct solutions, and the total_nqueens_helper function recursively explores the possible configurations. The is_valid function checks whether placing a queen at a specific position is valid or not.