经典算法之八皇后问题
点击上方“算法与数据之美”，选择“置顶公众号”
更多精彩等你来！
八皇后问题是一个古老而又著名的问题，是学习回溯算法的一个经典案例。今天我们就一起来探究一下吧！
时间退回到1848年，国际西洋棋棋手马克斯·贝瑟尔提出了这样的一个问题，
在8×8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问一共有多少种摆法。
后面陆续有不同的学者提出自己的见解。大数学家高斯认为一共有76种摆法，1854年在柏林的象棋杂志上不同的作者发表了共计40种不同的见解，后来还有人利用图论的方法得出共有92种摆法。
而如今，通过我们的计算机以及编程语言我们可以轻松的解决这个问题。
最直接的也是最容易想到的一种解法便是暴力法，我们可以在8×8的格子中任选8个皇后，选定后看是否满足任意两个皇后都不处于同行同列同斜线的条件，若满足则累计满足条件的方案。学习过排列组合的我们发现64取8这个数字达到了40亿，显然是令人难以接受的。
但我们根据这个条件，我们可以人为地做出一些选择，比如根据条件我们可知每行每列最多都只能有一个皇后，这样可以在一定程度上缩减问题的规模。在第一行的某一列选择放置一个皇后，共有8种不同的选择，而第二行只能选择剩下的7列，也就是7种选择，剩下每一行的选择都会递减1，那么总共可供选择的方案有8的阶乘种，已经是一种远优于暴力解法的解法，但是这个阶乘的时间复杂度恐怕也难以令人接受，还有更优的解法吗？
那是自然的，这便是递归回溯的方法。
当我们选择了第一个皇后的位置之后，与其处于同行同列同斜线的位置便都无法被选择，第二个皇后只能放在未被第一个皇后所辐射到的位置上，接着放置第三个皇后，同样不能放在被前两个皇后辐射到的位置上，若此时已经没有未被辐射的位置能够被选择，也就意味着这种摆法是不可行的，我们需要回退到上一步，给第二个皇后重新选择一个未被第一个皇后辐射的位置，再来看是否有第三个皇后可以摆放的位置，如还是没有则再次回退至选择第二个皇后的位置，若第二个皇后也没有更多的选择则回退到第一个皇后，重新进行位置的选择。
整体的方法便如上所述，下面用直观的代码来实现这个算法，
def find_Queen(row):
if row>7:
global count
count+=1
print_queen()
return
for column in range(8):
if check(row,column):
Queen[row][column]=1
find_Queen(row+1)
Queen[row][column]=0
定义一个二维数组Queen,数组中相应位置为1则表示该位置放置皇后，按行来摆放皇后的位置，如果当前选择没法继续往下找到皇后的放置位置，则将之前置为1的重新置为0，也就是回退。而check函数的主要目的是为了筛选皇后的合适位置以满足条件。具体可以分为三块，行列检查，主对角线以及负对角线检查。
def check(row,column):
# 检查行列
for k in range(8):
if Queen[k][column]==1:
return False
# 检查主对角线
for i,j in zip(range(row-1,-1,-1),range(column-1,-1,-1)):
if Queen[i][j]==1:
return False
# 检查副对角线
for i,j in zip(range(row-1,-1,-1),range(column+1,8)):
if Queen[i][j]==1:
return False
return True
当已经放置了八个皇后时，进入 if 语句，累计数值并且打印出相应的皇后摆放示意图。
实体的星星表示当前位置摆放了皇后，而具体的打印代码如下所示，
def print_queen():
print(Queen)
for i in range(8):
for j in range(8):
if Queen[i][j]==1:
print('☆ '*j+'★ '+'☆ '*(7-j))
print("\n\n")
这样，通过递归回溯的办法，我们找到了八皇后的92种解，并且以形式化的方法打印了出来。通过对八皇后问题的学习，我们可以深刻体会到回溯的思想~