-
Notifications
You must be signed in to change notification settings - Fork 1
/
n_queens.py
204 lines (168 loc) · 8.33 KB
/
n_queens.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
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
import unittest
from typing import List, Tuple
# 既然每行只能有一个皇后，皇后的位置用的是一个一位数组: 数组下标表示皇后的行号，值表示皇后的纵坐标
class Solution(unittest.TestCase):
TEST_CASES: List[Tuple[int, List[List[str]]]] = [
(4, [[".Q..",
"...Q",
"Q...",
"..Q."],
["..Q.",
"Q...",
"...Q",
".Q.."]]),
]
def test_print_all_solutions(self):
for n, output in self.TEST_CASES:
self.assertEqual(output, self.print_all_solutions(n))
# 52 ms, faster than 95.44% of Python3 online submissions for N-Queens.
# 36 ms, faster than 99.12% of Python3 online submissions for N-Queens II.
@staticmethod
def print_all_solutions(n: int) -> List[List[str]]:
"""
入口函数: N皇后问题1的入口函数
"""
results = []
# TODO 优化思路: 初始化时设定Set的容量固定容量提高性能，例如Rust的: HashSet::with_capacity()
# 斜率为左上到右下的直线方程的常系数b(x+y=b)
# x+y的范围是0..2n，Java可以用一个长度为2*n-1的Boolean数组
row_col_sum_memo = [False] * (2*n+1)
# 斜率为右上到左下的直线方程的常系数b(x-y=b)
# x-y的范围是-n..n，Java可以用一个长度为2*n-1的Boolean数组，不过坐标需要变换一下让-n..n => 0..2n
row_col_diff_set = set()
# 已使用的列号(推荐用List[bool])
used_cols = [False] * n
# 参数row表示下一个皇后的行号
def search(queen_cols: List[int], row: int):
if row == n:
results.append(Solution.render_board(queen_cols, n))
return
for col in range(n):
if used_cols[col]:
continue
row_col_sum = row + col
if row_col_sum_memo[row_col_sum]:
continue
row_col_diff = row - col
if row_col_diff in row_col_diff_set:
continue
queen_cols.append(col)
used_cols[col] = True
row_col_sum_memo[row_col_sum] = True
row_col_diff_set.add(row_col_diff)
search(queen_cols, row+1)
queen_cols.pop()
used_cols[col] = False
row_col_sum_memo[row_col_sum] = False
row_col_diff_set.remove(row_col_diff)
search([], 0)
return results
# @staticmethod
# def search(queens_col):
# pass
@staticmethod
def count_solutions():
"""
入口函数: N皇后问题2的入口函数
这题没什么变化，只不过将N皇后找到答案后render_board的函数改为自增count
"""
pass
@staticmethod
def render_board(queen_cols, n: int) -> List[str]:
board = []
for col in queen_cols:
row = ['.'] * n
row[col] = 'Q'
board.append(''.join(row))
return board
@staticmethod
def itertools_permutations_n_queen_solution(n: int):
"""
https://zhihu.com/question/37046157/answer/70747261
http://wordaligned.org/articles/8-queens-puzzle
https://leetcode.com/problems/n-queens/discuss/437421/Simple-python-3-solution-with-itertools.permutations
首先`itertools.permutations`保证了每个皇后的列号都不一样
因此只需要判断斜的方向有没有重合
皇后斜的方向就只有两种，左上-右下 和 右上-左下
而棋盘的左上-右下的直线方程的斜率为1、右上-左下的斜率为-1
左上-右下的直线方程为: y= x+b => x-y=-b
右上-左下的直线方程为: y=-x+b => x+y=b
所以表达式`queen_cols[i] + i`能得到右上-左下直线方程的「常系数b」
所以只要N皇后位置算出的斜率为1和斜率为-1的8条直线的常系数都不一样，则N皇后问题是正确的，否则必有两个皇后在同一条直线上
"""
import itertools
# for queen_cols in itertools.permutations(range(n)):
# # 一种通过斜率辨别法, 斜率为正的直线方程左上到右下，判断直线方程的常系数是否有相同的，相同说明两个皇后在一条斜线上
# if n == len({queen_cols[i] + i for i in range(n)}) \
# == len({queen_cols[i] - i for i in range(n)}):
# print({queen_cols[i] + i for i in range(n)})
# print({queen_cols[i] - i for i in range(n)})
# for col in queen_cols:
# s = ['.'] * n
# s[col] = 'Q'
# print(''.join(s))
# print()
solutions = []
# TODO itertools.permutations不用迭代器铁超时，只是这题时间限制放的很松
for queen_cols in itertools.permutations(range(n)):
if Solution.check_queen_cols_permutations(queen_cols):
solutions.append(Solution.render_board(queen_cols, n))
return solutions
@staticmethod
def check_queen_cols_permutations(queen_cols) -> bool:
"""
仅用于检测itertools.permutations的皇后们斜方向是否有两个皇后在同一条直线上
DFS解法中除了需要检测斜方向，还要检测列坐标有没有重复
而且这里检测斜方向的过程跟DFS回溯里不太一样
这里用的是HashSet方法，DFS里更多的是遍历一遍新坐标与老皇后逐个比较
"""
# 左上-右下方向的直线方程的常系数
constant_of_minus_slope_of_liner = set()
# 左上-右下方向的直线方程的常系数
constant_of_positive_slope_of_liner = set()
for x, y in enumerate(queen_cols):
s = x + y
if s in constant_of_minus_slope_of_liner:
return False
constant_of_minus_slope_of_liner.add(s)
d = x - y
if d in constant_of_positive_slope_of_liner:
return False
constant_of_positive_slope_of_liner.add(d)
return True
def test_itertools_permutations_n_queen_solution(self):
self.itertools_permutations_n_queen_solution(4)
"""
N皇后的问题在LeetCode上DFS回溯的算法题里不算特别难，相比word_ladder_2代码量也很少
只要代码结果拆分合理，这道题就很难写错，我认为这题可以拆为4个部分:
- 入口函数
- DFS搜索回溯函数(search)
- 判断当前放置皇后的位置是否合法(is_invalid)
- 将正确的皇后位置渲染成棋盘字符串(render_board)，然后在DFS搜索回溯函数里加到答案集内
我认为主要难点就两个 通过什么数据结构存储皇后的位置 和 如何判断某个位置是否合法
既然每行只能有一个皇后，皇后的位置用的是一个一位数组: 数组下标表示皇后的行号，值表示皇后的纵坐标
所以`for x, y in enumerate(queen_cols)`就能得到皇后们的行号和列号
先看一段打印8皇后的简单版代码:
```python
import itertools
for queen_cols in itertools.permutations(range(n)):
if n == len({queen_cols[i] + i for i in range(n)}) \
== len({queen_cols[i] - i for i in range(n)}):
for col in queen_cols:
s = ['.'] * n
s[col] = 'Q'
print(''.join(s))
print()
```
解释下`len({queen_cols[i] + i for i in range(n)})`这行为什么能验证N皇后
首先`itertools.permutations`保证了每个皇后的列号都不一样
因此只需要判断斜的方向有没有重合
可以将棋盘看做一个初中数学的xoy坐标系，只不过顺时针转动了90度，y轴是横着的
皇后斜的方向就只有两种，左上-右下 和 右上-左下
而xoy坐标系下棋盘的左上-右下的直线方程的斜率为1、右上-左下的斜率为-1
左上-右下的直线方程为: y= x+b => x-y=-b
右上-左下的直线方程为: y=-x+b => x+y=b
所以表达式`queen_cols[i] + i`能得到右上-左下直线方程的「常系数b」
初中数学学过点-斜式方程，通过一点和斜率可以的得到直线方程
所以只要N皇后位置算出的斜率为1和斜率为-1的8条直线的常系数都不一样，则N皇后问题是正确的，否则必有两个皇后在同一条直线上
"""