forked from algorhythms/LeetCode
-
Notifications
You must be signed in to change notification settings - Fork 0
/
051 N-Queens II.py
73 lines (60 loc) · 2.24 KB
/
051 N-Queens II.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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
"""
Follow up for N-Queens problem.
Now, instead outputting board configurations, return the total number of distinct solutions.
"""
__author__ = 'Danyang'
INVALID = -1
QUEEN = 1
DEFAULT = 0
class Solution:
def totalNQueens(self, n):
"""
backtracking
:param n: integer
:return: a list of lists of string
"""
result = []
current = [[0 for _ in xrange(n)] for _ in xrange(n)]
self.backtrack(0, current, result)
return len(result)
def backtrack(self, queen_index, current, result):
"""
:param queen_index:
:param current: 2D matrix
:param result: list of 2D matrix
:return: Nothing
"""
n = len(current)
if queen_index==n:
result.append(current)
return
for i in xrange(n):
if current[queen_index][i]==INVALID:
continue
# place the queen
new_config = [list(element) for element in current] # new copy
new_config[queen_index][i] = QUEEN
# config
for m in xrange(n):
# col
if new_config[m][i]==DEFAULT:
new_config[m][i] = INVALID
# row
if new_config[queen_index][m]==DEFAULT:
new_config[queen_index][m] = INVALID
# diagonal
row = queen_index+m
col = i+m
if 0<=row<n and 0<=col<n and new_config[row][col]==DEFAULT: new_config[row][col] = INVALID
row = queen_index-m
col = i-m
if 0<=row<n and 0<=col<n and new_config[row][col]==DEFAULT: new_config[row][col] = INVALID
row = queen_index-m
col = i+m
if 0<=row<n and 0<=col<n and new_config[row][col]==DEFAULT: new_config[row][col] = INVALID
row = queen_index+m
col = i-m
if 0<=row<n and 0<=col<n and new_config[row][col]==DEFAULT: new_config[row][col] = INVALID
self.backtrack(queen_index+1, new_config, result)
if __name__=="__main__":
print Solution().totalNQueens(4)