关于N王后问题
模块代码:
#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保存在“你的路径”下。
查看全文 »
为之漫笔(李松峰),本博客专注于Web前后端技术、移动平台开发技术、交互设计和技术翻译。 