Recursion Backtracking Combinatorics
Guru Level

Implement the nQueensSolutionCount method that counts valid ways to place n queens on the board.

The input is an integer n, representing an n × n chessboard.

Your task is to return how many different ways n queens can be placed on the board so that no two queens attack each other.

Queens attack along the same row, same column, and both diagonals. For example, for n = 4, there are 2 valid arrangements.

Example 1
Input:
n (int) = 4
Return:
(int) 2
Example 2
Input:
n (int) = 1
Return:
(int) 1
Example 3
Input:
n (int) = 2
Return:
(int) 0

Place queens row by row using backtracking.

For each row, try every column. A position is valid only when no previous queen is in the same column or diagonal. If the position is safe, place the queen and continue to the next row.

When queens have been placed in all rows, one valid solution has been found, so increase the count.

Pseudocode:

function nQueensSolutionCount(n):
    count = 0
    usedColumns = empty set
    usedDiag1 = empty set
    usedDiag2 = empty set
    backtrack(row):
        if row == n:
            count++
            return
        for col from 0 to n - 1:
            if col is used or row - col is used or row + col is used:
                continue
            mark col, row - col, and row + col as used
            backtrack(row + 1)
            unmark col, row - col, and row + col
    backtrack(0)
    return count
Run your code to see the result.