0%

【LeetCode with Python】 52. N-Queens II

题目

原题页面:https://oj.leetcode.com/problems/n-queens-ii/
本文地址:</n-queens-ii/>
题目类型:Backtracking
难度评价:Hard
类似题目:(H) N-Queens

Follow up for N-Queens problem.

Now, instead outputting board configurations, return the total number of distinct solutions.

8-queens


分析


代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution:

def __init__(self):
self.paths_count = 0

def dpTotalNQueens(self, n, prefix, level):
for i in range(0, n):
point = (i, level)
is_valid = True
for m in range(0, len(prefix)):
if i == prefix[m]:
is_valid = False
break
if level - m == i - prefix[m] or level - m == prefix[m] - i:
is_valid = False
break
if is_valid:
new_prefix = prefix[:]
new_prefix.append(i)
if n - 1 != level:
self.dpTotalNQueens(n, new_prefix, level + 1)
else:
self.paths_count += 1

# @return an integer
def totalNQueens(self, n):
self.dpTotalNQueens(n, [ ], 0)
return self.paths_count