N王后问题

2009年01月16日 原创

关于N王后问题
模块代码：

  1. #nqueens.py
  2. #coding=UTF-8
  3.  
  4. # n王后问题解决方案
  5. # 检查当前王后位置（可能是多个）与下一个王后位置是否冲突
  6. def conflict(state,posX):
  7.     posY = len(state)
  8.     for i in range(posY):
  9.         if abs(state[i]-posX) in (0,posY-i):
  10.             return True
  11.     return False
  12.  
  13. # 采用回溯递归算法，结合生成器特性，计算可能的解决方案
  14. def find(num=4,state=()):
  15.     for pos in range(num):
  16.         if not conflict(state,pos):
  17.             if len(state)==num-1:
  18.                 yield (pos,)
  19.             else:
  20.                 for result in find(num,state+(pos,)):
  21.                     yield (pos,)+result
  22.  
  23. # 形象地表示每个解决方案
  24. def show(solutions):
  25.     def printSolution(index,solution):
  26.         print "\n方案"+str(index)+" "+str(solution)+"\n"
  27.         for pos in solution:
  28.             length=len(solution)
  29.             print ". "*(pos)+"Q "+". "*(length-pos-1)+"("+str(pos)+")"
  30.     list_solutions = list(solutions)
  31.     if not len(list_solutions)==0:
  32.         enum_solutions = enumerate(list_solutions)
  33.         n_solutions = len(list_solutions)
  34.         n_queens = len(list_solutions[0])
  35.  
  36.         print str(n_queens)+"王后问题有"+str(n_solutions)+"种方案："
  37.         for index,solution in enum_solutions:
  38.             printSolution(index+1,solution)
  39.  
  40. # 调用方法：
  41. # nqueens.show(nqueens.find())
  42. # 或
  43. # nqueens.show(nqueens.find(5))

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

有 1 条评论