-
Notifications
You must be signed in to change notification settings - Fork 4
Expand file tree
/
Copy path2018-12-14-51-N-Queens.py
More file actions
78 lines (67 loc) · 2.62 KB
/
2018-12-14-51-N-Queens.py
File metadata and controls
78 lines (67 loc) · 2.62 KB
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
74
75
76
77
78
# -*- coding: utf-8 -*-
# @Author: 何睿
# @Create Date: 2018-12-14 12:02:03
# @Last Modified by: 何睿
# @Last Modified time: 2018-12-14 18:38:30
import copy
class Solution:
def __init__(self):
# 初始变量，减少函数传递次数
# 记录列的情况，表示是否被占用,Ture表示被占用，False表示空
self.coloccupied = []
# 记录左对角线的情况，表示左对角线是否被占用
self.Left_diag = []
# 记录又对角线的情况，表示右边的对角线是否被占用
self.right_diag = []
# 皇后的面板，所有的位置都初始化为'.'
self.board = []
# 矩阵维度
self.rank = 0
# 结果数组
self.res = []
def solveNQueens(self, n):
"""
:type n: int
:rtype: List[List[str]]
"""
self.rank = n
self.coloccupied = [False]*self.rank
self.Left_diag = [False]*(2*self.rank-1)
self.right_diag = [False]*(2*self.rank-1)
for _ in range(self.rank):
self.board.append(['.']*self.rank)
self.nQueen(0)
for i in range(len(self.res)):
self.res[i] = [''.join(subitem) for subitem in self.res[i]]
return self.res
# 检查当前位置是否被占用，被占用返回Ture，没有被占用返回False
def isOccupied(self, row, col):
# 当前位置所在的列，左对角线，右对角线只要有一个被占用，则该位置就被占用
return self.coloccupied[col] or self.Left_diag[row+col] or self.right_diag[row+self.rank-col-1]
def put(self, row, col, isput):
# 该列是否被占用
self.coloccupied[col] = isput
# 该位置左对角线是否被占用
self.Left_diag[row+col] = isput
# 该位置右对角线是否被占用
self.right_diag[row+self.rank-col-1] = isput
# 如果是放置，则放入"Q"，清空，放置"."
self.board[row][col] = "Q" if isput else "."
def nQueen(self, row):
if row == self.rank:
# 注意，这里需要用深拷贝
self.res.append(copy.deepcopy(self.board))
return
for col in range(self.rank):
if self.isOccupied(row, col):
continue
# 在当前位置放置皇后
self.put(row, col, True)
# 进入下一层寻找
self.nQueen(row+1)
# 返回的时候，逐层清除原来放置的皇后
self.put(row, col, False)
if __name__ == "__main__":
so = Solution()
res = so.solveNQueens(4)
print(res)