关于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前后端技术和技术翻译。目前正在翻译《JavaScript高级程序设计(第2版)》。新浪微博(t.sina.com.cn/lisf),Twitter(@cncuckoo,仅仅用于跟踪国外牛人;我翻不了墙,无法接受各位朋友的follow,抱歉!)