八皇后问题是一个老生常谈的问题，是学习回溯算法的经典案例。今天就一起来探索吧！早在1848年，国际象棋棋手MaxBethel就提出了这样一个问题，将八个皇后放在一个8×8的方格棋子上，使它们不能互相攻击，即任意两个皇后都不能在同一行、同一列或斜线。一共有多少种方式？后来，不同的学者提出了自己的看法。伟大的数学家高斯认为总共有76个摆。1854年，不同的作者在柏林的国际象棋杂志上发表了总共40种不同的观点。后来有人用图论的方法得到了总共92个摆。今天，我们可以用我们的计算机和编程语言轻松解决这个问题。最直接、最简单的解决办法就是暴力法。我们可以在8×8的方格中选出8个皇后，选出后检查任意两个皇后是否不在同一列和同一斜线。如果满足条件，则累积满足条件的方案。经过研究排列组合，我们发现64个中8个的数量已经达到了40亿个，这显然是不能接受的。但是根据这个条件，我们可以做一些人为的选择。比如根据条件我们知道每一行每一列最多只能有一个皇后，这样可以在一定程度上降低问题的规模。选择在第一行的某一列放置一个皇后，有8种不同的选择，第二行只能选择剩下的7列，即7种选择，剩下的每一行的选择都会减1，所以总共有8个阶乘可供选择，这已经是一个远优于暴力解法的解法了，但是这个阶乘的时间复杂度恐怕是无法接受的。有更好的解决方案吗？这很自然，这就是递归回溯的方式。当我们选择第一个皇后的位置时，不能选择同一行和同一斜线的位置。第二个皇后只能放在第一个皇后没有辐射的位置，然后再放第三个皇后也不能放在前两个皇后辐射的位置。如果此时没有可以选择的未辐射位置，则说明这种安排是不可行的。我们需要回到上一步重新为第二个皇后选择一个没有被第一个皇后辐射的位置，然后检查是否有第三个皇后可以放置的位置。如果仍然没有位置，则返回选择第二个皇后如果第二个皇后没有更多选择，则退回到第一个皇后并重新选择位置。整体方法如上，下面用直观的代码来实现这个算法，deffind_Queen(row):ifrow>7:globalcountcount+=1print_queen()returnforcolumninrange(8):ifcheck(row,column):Queen[row][column]=1find_Queen(row+1)Queen[row][column]=0定义一个二维数组Queen，数组中对应的位置为1，表示皇后被放置在这个位置，行是放置皇后的位置，如果当前选择不能继续找到皇后的位置，则将之前设置的1重置为0，即回滚。check函数的主要目的是筛选出符合条件的皇后合适的位置。具体可以分为三部分，行列检查，主对角线和负对角线检查。defcheck(row,column):#Checktherowandcolumnforkinrange(8):ifQueen[k][column]==1:returnFalse#Checkthemaindiagonalfori,jinzip(range(row-1,-1,-1),range(column-1,-1,-1)):ifQueen[i][j]==1:returnFalse#检查i,j的下对角线zip(range(row-1,-1,-1),range(column+1,8)):ifQueen[i][j]==1:returnFalsereturnTrue当八个皇后都已放置时，输入ifstatement，累加值，打印出相应的皇后放置示意图。实体的星号表示皇后放在当前位置，具体打印代码如下，defprint_queen():print(Queen)foriinrange(8):forjinrange(8):ifQueen[i][j]==1:print('☆'*j+'★'+'☆'*(7-j))print("\n\n")这样，通过递归回溯，我们找到了的八皇后92解，并正式打印出来。通过八皇后问题的学习，我们可以深刻理解回溯的思想~
