52.n_queens_2.md

52. N-Queens II

困难

https://leetcode.cn/problems/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

相关企业

• 字节跳动|2

相关标签

• Backtracking

相似题目

• N-Queens 困难

solution

it's same as 51.n queens but asking for count

class Solution:
    def totalNQueens(self, n: int) -> int:
        return self.dfs(n, [])

    def dfs(self, n, col):
        if len(col) == n:
            return 1

        total_counter = 0
        for next_coli in range(n):
            if not self.isValid(col, next_coli):
                continue
            col.append(next_coli)
            total_counter += self.dfs(n, col)
            col.pop()
        return total_counter
    
    def isValid(self, col, next_coli):
        next_rowi = len(col)
        for rowi, coli in enumerate(col):
            if coli == next_coli:
                return False
            if abs(rowi - next_rowi) == abs(coli - next_coli):
                return False
        return True