N 皇后问题是回溯算法的典型案例,本文通过 N 皇后问题复习递归 / 回溯算法并运用一些 python 函数库简化程序。

最容易理解的递归解法

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
class Solution(object):
def __init__(self):
# board 存储一种解法(作为缓存)
self.board = []
# boards 存储所有解法(作为结果)
self.boards = []
def solve_n_queens(self, n):
"""
:param n: int:
:return: self.boards: list[list[int]]
"""
self.board = [0 for i in range(n)]
self.solve_line(0, n)
return self.boards
# 解决前 row 列
def solve_line(self, row, n):
if row == n:
self.boards.append([i for i in self.board])
return
else:
for col in range(n):
if self.is_valid(row, col):
self.board[row] = col
self.solve_line(row + 1, n)
self.board[row] = 0
# 监测 (row,col) 是否与 0~row-1 行发生冲突
def is_valid(self, row, col):
for i in range(row):
if self.board[i] == col:
return False
if i+self.board[i] == row+col:
return False
if i-self.board[i] == row-col:
return False
return True
if __name__ == '__main__':
s = Solution()
r = s.solve_n_queens(8)
for i in r:
print(i)

Raymond Hettingers 的解法(使用 permutations)

1
2
3
4
5
6
7
8
from itertools import permutations
n = 8
cols = range(n)
for vec in permutations(cols):
if n == len(set(vec[i]+i for i in cols)) \
== len(set(vec[i]-i for i in cols)):
print ( vec )

这个解法由 Raymond Hettingers 编写,展示了 itertools 模块的魅力。

Raymond Hettingers 对这个解法的解释:

  • 由于解(由 vector 表示)中每一个元素代表棋盘的一行,所以不用检测棋子是否在同一行。同时,由于使用了生成器(generator)permutation,vector 中的每个元素都是不同的,所以不用检测棋子是否在同一列。因此,我们只需要检测是否存在斜线冲突。

  • 检测斜线冲突的办法是将每一个元素加上 / 减去它的索引(即每一个棋子的列序号加上 / 减去它的行序号)。这样,在斜线上冲突的棋子将会呈现出相同的值。然后将所有棋子相加 / 相减后的索引放入一个 set 中,再比较 set 的大小与 n 的值,即可得知是否发生了斜线冲突。

  • 所有不发生斜线冲突的全排列都是一个解,将它们输出。

这个解法的缺陷在于不能跳过已经被证实为不可行的前缀,如(1,2,…)。这些前缀会在多种全排列中被反复测试并浪费一些时间。

Steve Howell 的解法

这个解法来自于 Steve Howell

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# From: http://wiki.python.org/moin/SimplePrograms, with permission from the author, Steve Howell
BOARD_SIZE = 8
def under_attack(col, queens):
return col in queens or \
any(abs(col - x) == len(queens)-i for i,x in enumerate(queens))
def solve(n):
solutions = [[]]
for row in range(n):
solutions = [solution+[i+1]
for solution in solutions
for i in range(BOARD_SIZE)
if not under_attack(i+1, solution)]
return solutions
for answer in solve(BOARD_SIZE): print(list(enumerate(answer, start=1)))

由 Steve Howell 的解法改进而来的回溯解法

把上面的 Steve Howell 的解法中的 list 表达式替换为 generator 表达式,便形成了一种回溯解法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
BOARD_SIZE = 8
def under_attack(col, queens):
return col in queens or \
any(abs(col - x) == len(queens)-i for i,x in enumerate(queens))
def solve(n):
solutions = [[]]
for row in range(n):
solutions = (solution+[i+1]
for solution in solutions # first for clause is evaluated immediately,
# so "solutions" is correctly captured
for i in range(BOARD_SIZE)
if not under_attack(i+1, solution))
return solutions
answers = solve(BOARD_SIZE)
first_answer = next(answers)
print(list(enumerate(first_answer, start=1)))

基于 permutations 的回溯解法

参考链接

(未完待续)

本文地址: http://www.cuixiaochen.com/2016/08/18/N皇后问题解法汇总及分析-python/