python八皇后问题

obeckham

from itertools import permutations　　for vec in permutations(range(8)):
　　if (8 == len(set(vec+i for i in range(8)))== len(set(vec-i for i in range(8)))):
　　print vec
　　global col                                  #定义一些全局变量
　　global row
　　global pos_diag
　　global nag_diag
　　global count
　　def output():
　　''' 输出一种有效结果
　　'''
　　global count
　　print row
　　count += 1
　　def do_queen(i):
　　''' 生成所有正确解
　　@param i: 皇后的数目
　　'''
　　for j in range(0, 8):                   #依次尝试0～7位置
　　if col[j] == 1 and pos_diag[i-j+7] == 1 and nag_diag[i+j] == 1:
　　#若该行，正对角线，负对角线上都没有皇后，则放入i皇后
　　row = j
　　col[j] = 0                      #调整各个列表状态
　　pos_diag[i-j+7] = 0
　　nag_diag[i+j] = 0
　　if i < 7:
　　do_queen(i+1)               #可递增或递减
　　else:
　　output()                    #产生一个结果，输出
　　col[j] = 1                      #恢复各个列表状态为之前的
　　pos_diag[i-j+7] = 1
　　nag_diag[i+j] = 1
　　if __name__ == '__main__':
　　col = []                                #矩阵列的列表，存储皇后所在列，若该列没有皇后，则相应置为1，反之则0
　　row = []                                #矩阵行的列表，存放每行皇后所在的列位置，随着程序的执行，在不断的变化中，之间输出结果
　　pos_diag = []                           #正对角线，i-j恒定，-7~0~7，并且b(i)+7统一到0～14
　　nag_diag = []                           #负对角线，i+j恒定，0～14
　　count = 0
　　for index in range(0, 8):               #一些初始化工作
　　col.append(1)
　　row.append(0)
　　for index in range(0, 15):
　　pos_diag.append(1)
　　nag_diag.append(1)
　　do_queen(0)
　　#开始递归，先放一个，依次递增，反过来，从7开始递减也可
　　print 'Totally have %d solutions!' % count
　　import random
　　#冲突检查，在定义state时，采用state来标志每个皇后的位置，其中索引用来表示横坐标，基对应的值表示纵坐标，例如： state[0]=3，表示该皇后位于第1行的第4列上
　　def conflict(state, nextX):
　　nextY = len(state)
　　for i in range(nextY):
　　#如果下一个皇后的位置与当前的皇后位置相邻（包括上下，左右）或在同一对角线上，则说明有冲突，需要重新摆放
　　if abs(state-nextX) in (0, nextY-i):
　　return True
　　return False
　　#采用生成器的方式来产生每一个皇后的位置，并用递归来实现下一个皇后的位置。
　　def queens(num, state=()):
　　for pos in range(num):
　　if not conflict(state, pos):
　　#产生当前皇后的位置信息
　　if len(state) == num-1:
　　yield (pos, )
　　#否则，把当前皇后的位置信息，添加到状态列表里，并传递给下一皇后。
　　else:
　　for result in queens(num, state+(pos,)):
　　yield (pos, ) + result
　　#为了直观表现棋盘，用X表示每个皇后的位置
　　def prettyprint(solution):
　　def line(pos, length=len(solution)):
　　return '. ' * (pos) + 'X ' + '. '*(length-pos-1)
　　for pos in solution:
　　print line(pos)
　　if __name__ == "__main__":
　　prettyprint(random.choice(list(queens(8))))
　　def queens(num=8, state=()):
　　for pos in range(num):
　　if not conflict((), pos):
　　queens(num, state+(pos,)) #递归调用，将此行展开
　　def conflict(state,nextx):
　　'定义冲突函数,state为元组，nextx为下一个皇后的水平位置，nexty为下一个皇后的垂直位置'
　　nexty = len(state)
　　for i in range(nexty):
　　if abs(state-nextx) in (0,nexty-i):#若下一个皇后和前面的皇后列相同或者在一条对角线上，则冲突
　　return True
　　return False
　　def queens(num=8,state=()):
　　'八皇后问题，这里num表示规模'
　　for pos in range(num):
　　if not conflict(state,pos):#位置不冲突
　　if len(state) == num - 1:#若是最后一个皇后，则返回该位置
　　yield (pos,)
　　else:#若不是最后一个皇后，则将该位置返回到state元组并传给后面的皇后
　　for result in queens(num,state + (pos,)):
　　yield (pos,) + result
　　def prettyp(solution):
　　'打印函数'
　　def line(pos,length = len(solution)):
　　'打印一行，皇后位置用X填充，其余用0填充'
　　return 'O'*(pos)+'X'+'O'*(length-pos-1)
　　for pos in solution:
　　print(line(pos))
　　import random
　　#随机打印一种
　　prettyp(random.choice(list(queens(8))))
　　# -*- coding: utf-8 -*-
　　#python默认为ascii编码，中文编码可以用utf-8
　　import random
　　#随机模块
　　def conflict(state,col):
　　#冲突函数，row为行，col为列
　　row=len(state)
　　for i in range(row):
　　if abs(state-col) in (0,row-i):#重要语句
　　return True
　　return False
　　def queens(num=8,state=()):
　　#生成器函数
　　for pos in range(num):
　　if not conflict(state, pos):
　　if len(state)==num-1:
　　yield(pos,)
　　else:
　　for result in queens(num, state+(pos,)):
　　yield (pos,)+result
　　def queenprint(solution):
　　#打印函数
　　def line(pos,length=len(solution)):
　　return '. '*(pos)+'X '+'. '*(length-pos-1)
　　for pos in solution:
　　print line(pos)
　　for solution in list(queens(8)):
　　print solution
　　print '  total number is '+str(len(list(queens())))
　　print '  one of the range is:\n'
　　queenprint(random.choice(list(queens())))