52. N-Queens II

package Leetcode.Backtracking;

/**
 * @author zhengxingxing
 * @date 2024/12/02
 */
public class NQueensII {
    // This method is the entry point. It calls the recursive solve method to find the number of solutions.
    public static int totalNQueens(int n) {
        return solve(n, 0, 0, 0, 0);  // Initial call with row = 0 and all bitmasks set to 0.
    }

    // Recursive backtracking method to solve N-Queens problem
    private static int solve(int n, int row, int columns, int diagonals, int antiDiagonals) {

        // If we've placed queens in all rows, return 1 as we've found a valid solution.
        if (row == n) {
            return 1;
        }

        int solutions = 0;  // Variable to count the number of valid solutions

        // Try placing a queen in every column of the current row
        for (int i = 0; i < n; i++) {
            // Calculate the bitmask for the current column (only i-th column in the row).
            int currColumn = 1 << i;

            // Calculate the bitmask for the current main diagonal.
            // The main diagonal can be uniquely identified by (row - col), and we add (n-1) to ensure it stays positive.
            int currDiagonal = 1 << (row - i + n - 1);

            // Calculate the bitmask for the current anti-diagonal (row + col).
            int currAntiDiagonal = 1 << (row + i);

            // Check if placing the queen at (row, i) conflicts with any previously placed queens.
            // We check each of the three potential conflicts (column, diagonal, anti-diagonal) using bitwise AND.
            // If the result is not 0, it means that a queen already exists in that column, diagonal, or anti-diagonal.
            if ((columns & currColumn) != 0 ||
                    (diagonals & currDiagonal) != 0 ||
                    (antiDiagonals & currAntiDiagonal) != 0) {
                continue;  // If there's a conflict, skip this column.
            }

            // If no conflicts, place the queen at (row, i) and move to the next row (row + 1).
            // We update the bitmasks (columns, diagonals, and antiDiagonals) by setting the corresponding bits to 1.
            solutions += solve(
                    n,
                    row + 1,  // Move to the next row
                    columns | currColumn,  // Mark the current column as occupied
                    diagonals | currDiagonal,  // Mark the current main diagonal as occupied
                    antiDiagonals | currAntiDiagonal  // Mark the current anti-diagonal as occupied
            );
        }

        // Return the total number of solutions found for this configuration
        return solutions;
    }

    // Main method to test the N-Queens solution
    public static void main(String[] args) {
        // You can modify n to test different board sizes
        int n = 4;
        System.out.println("Total solutions for N=" + n + " Queens: " + totalNQueens(n));
    }
}