-
Notifications
You must be signed in to change notification settings - Fork 0
/
Leetcode0052.py
35 lines (33 loc) · 1.14 KB
/
Leetcode0052.py
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
29
30
31
32
33
34
35
class Solution(object):
def check(self, k, j, board):
# check if k-th queen can be put in column j
for i in range(len(board)):
pos_i = board[i]
# if they are at the same column
if j == pos_i:
return False
# if they are at the same diagonal
if abs(i-k) == abs(j-pos_i):
return False
return True
def dfs(self, n, board, res):
# the path stores the positions of the current queens
# termination condition
if len(board) == n:
result = ["."*n for i in range(n)]
for i in range(n):
j = board[i]
result[i] = result[i][:j]+"Q"+result[i][j+1:]
res[0]+=1
for j in range(n):
# if the current position is valid, we find the position of the next queen
if self.check(len(board), j, board):
self.dfs(n, board+[j], res)
def totalNQueens(self, n):
"""
:type n: int
:rtype: int
"""
res = [0]
self.dfs(n, [], res)
return res[0]