具体如下:

八皇后问题是一个以国际象棋为背景的问题:如何能够在 8×8 的国际象棋棋盘上放置八个皇后,使得任何一个皇后都无法直接吃掉其他的皇后?为了达到此目的,任两个皇后都不能处于同一条横行、纵行或斜线上。八皇后问题可以推广为更一般的n皇后摆放问题:这时棋盘的大小变为n1×n1,而皇后个数也变成n2。而且仅当 n2 = 1 或 n1 ≥ 3 时问题有解。

这是一个典型的回溯算法,我们可以将问题进行分解:

首先,我们要想到某种方法来解决冲突检测问题,即不能令棋子处于能相互吃掉的位置——相邻、左右对角线。

其次,运用回溯的方法,求得问题的解。此处具体为函数的递归调用,当调用到棋盘的最后一行,便跳出,求得解。

最后,将我们的解打印出来。难点在于对递归调用函数的理解。

这仅仅是思路,是我们必须要解决的问题,但并不代表程序的运行流程。

具体代码如下:

#-*-coding:utf-8-*-importrandom#冲突检查,在定义state时,采用state来标志每个皇后的位置,其中索引用来表示横坐标,基对应的值表示纵坐标,例如:state[0]=3,表示该皇后位于第1行的第4列上defconflict(state,nextX):nextY=len(state)#print(nextY),foriinrange(nextY):#如果下一个皇后的位置与当前的皇后位置相邻(包括上下,左右)或在同一对角线上,则说明有冲突,需要重新摆放ifabs(state[i]-nextX)in(0,nextY-i):#纵坐标减去下一个皇后的横坐标的绝对值处于0到下一皇后纵坐标减i则冲突returnTruereturnFalse#采用生成器的方式来产生每一个皇后的位置,并用递归来实现下一个皇后的位置。defqueens(num,state=()):#num=8#print("%d"%len(state)),forposinrange(num):ifnotconflict(state,pos):#如果没有冲突#产生当前皇后的位置信息iflen(state)==num-1:yield(pos,)#生成元组#否则,把当前皇后的位置信息,添加到状态列表里,并传递给下一皇后。else:forresultinqueens(num,state+(pos,)):yield(pos,)+result#result这个变量代表的是quees返回的元组#若是最后一行对于posinrange(num)调用conflict(state,num),#如果没有冲突,生成元组#若不是最后一行对于posinrange(num)调用conflict(state,pos),#如果没有冲突,state更新,递归调用queens(num,state)state将更新#为了直观表现棋盘,用X表示每个皇后的位置defprettyprint(solution):defline(pos,length=len(solution)):return'.'*(pos)+'X'+'.'*(length-pos-1)forposinsolution:printline(pos)if__name__=="__main__":#来判断是否是在直接运行该.py文件prettyprint(random.choice(list(queens(8))))

运行结果: