N王后问题

2009年01月16日原创

#nqueens.py
#coding=UTF-8
# n王后问题解决方案
# 检查当前王后位置（可能是多个）与下一个王后位置是否冲突
def conflict(state,posX):
posY = len(state)
for i in range(posY):
if abs(state[i]-posX) in (0,posY-i):
return True
return False
# 采用回溯递归算法，结合生成器特性，计算可能的解决方案
def find(num=4,state=()):
for pos in range(num):
if not conflict(state,pos):
if len(state)==num-1:
yield (pos,)
else:
for result in find(num,state+(pos,)):
yield (pos,)+result
# 形象地表示每个解决方案
def show(solutions):
def printSolution(index,solution):
print "\n方案"+str(index)+" "+str(solution)+"\n"
for pos in solution:
length=len(solution)
print ". "*(pos)+"Q "+". "*(length-pos-1)+"("+str(pos)+")"
list_solutions = list(solutions)
if not len(list_solutions)==0:
enum_solutions = enumerate(list_solutions)
n_solutions = len(list_solutions)
n_queens = len(list_solutions[0])
print str(n_queens)+"王后问题有"+str(n_solutions)+"种方案："
for index,solution in enum_solutions:
printSolution(index+1,solution)
# 调用方法：
# nqueens.show(nqueens.find())
# 或
# nqueens.show(nqueens.find(5))

将以上代码复制到nqueens.py中，把nqueens.py保存在“你的路径”下。

以4王后问题（默认）为例。首先设置系统路径，以便Python解析器能在该路径中找到相应模块：

>>> import sys
>>> sys.path.append("你的路径")

然后，导入模块，并采用默认值调用show方法：

>>> import nqueens
>>> nqueens.show(nqueens.find())
4王后问题有2种方案：

方案1 (1, 3, 0, 2)

. Q . . (1)
. . . Q (3)
Q . . . (0)
. . Q . (2)

方案2 (2, 0, 3, 1)

. . Q . (2)
Q . . . (0)
. . . Q (3)
. Q . . (1)

另外，如果不需要看图，可以直接调用find方法：

>>> list(nqueens.find())
[(1, 3, 0, 2), (2, 0, 3, 1)]
>>> list(nqueens.find(6))
[(1, 3, 5, 0, 2, 4), (2, 5, 1, 4, 0, 3), (3, 0, 4, 1, 5, 2), (4, 2, 0, 5, 3, 1)]

或者，为查看方便，可以使用pprint模块的pprint（pretty-print）方法：

>>> import pprint
>>> pprint.pprint(list(nqueens.find(5)))
[(0, 2, 4, 1, 3),
(0, 3, 1, 4, 2),
(1, 3, 0, 2, 4),
(1, 4, 2, 0, 3),
(2, 0, 3, 1, 4),
(2, 4, 1, 3, 0),
(3, 0, 2, 4, 1),
(3, 1, 4, 2, 0),
(4, 1, 3, 0, 2),
(4, 2, 0, 3, 1)]

如果王后多于6个（7王后问题有40种解决方案，8王后问题有92种解决方案），则可以只查看方案数量：

>>> len(list(nqueens.find(7)))
40
>>> len(list(nqueens.find(8)))
92
>>> len(list(nqueens.find(9)))
352
>>> len(list(nqueens.find(10)))
724
>>> len(list(nqueens.find(11)))
2680

注意：求解12个以上的王后时要小心。在俺的P4 2.4G电脑中，求解11王后问题，上面算法费时10秒。而12王后的解决方案是14200……，小心啊！
参见“目前最快的算法”。

有话要说？评论RSS

朋友们的留言

为之漫笔 » N王后问题（续） | 一月 24th, 2009 at 11:47
[...] N王后问题，是一个科学谜题，指的是在把N个王后放到N*N的棋盘上，结果是任何王后之间都不会彼此威胁。换句话说，每个后继的王后既不能与前面的王后在同一行、同一列，也不能位于同一对角线上。N王后问题给出了Python代码。下面是JavaScript代码，但结果有些误差，不知何故。 function conflict(state,posX) { [...]