Skip to content

52. N Queens II

Backtracking

Problem - N Queens II

Hard

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

Solutions

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    def totalNQueens(self, n: int) -> int:
        result = 0
        cols = [False] * n
        diag = [False] * (n << 1)
        anti_diag = [False] * (n << 1)

        def dfs(i: int):
            if i == n:
                nonlocal result
                result += 1
                return
            for j in range(n):
                if cols[j] or diag[j + i] or anti_diag[n - j + i]:
                    continue
                cols[j] = diag[j + i] = anti_diag[n - j + i] = True
                dfs(i + 1)
                cols[j] = diag[j + i] = anti_diag[n - j + i] = False

        dfs(0)
        return result

Submission Stats:

  • Runtime: 3 ms (96.12%)
  • Memory: 18 MB (24.64%)