算法初识——回溯法八皇后

八皇后问题是一个古老而著名的问题，是回溯算法的典型例题。该问题由国际西洋棋棋手马克斯·贝瑟尔于1848年提出：在8x8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意的两个皇后不能在同一行，同一列或者同一斜线上，问有多少种摆法。

首先学习下如何对两个皇后不在同一行，同一列以及同一斜线上的判定。

不在同一行或者同一列只需要对一个数值进行判定就可以得出，比较好判断，不在同一斜线上应该怎样判定呢？

图中的五边形代表一个皇后，观察下它的两斜边可以得出规律：

1、在皇后所在的右上到左下的这条斜线上方格的横坐标和纵坐标之差是一个固定值，并且每一条斜线方格横纵坐标的差值都不一样。

例如（8,8）——（1,1）这条斜线上的方格横纵坐标的差值为0；

2、在皇后所在的左上到右下的这条斜线上方格的横坐标和纵坐标之和为一个固定值，并且轻易证实每一条斜线上的方格的横纵坐标之和都不相同。

因此对皇后的摆放条件有了清晰判断依据。先假设一个bool返回值类型的函数  is_ok(int row)  来根据已知的判定条件判定是否可以摆放一个皇后的位置，同时使用一个数组来保存皇后所在的行列，数组的下标为皇后所摆放的行，数组的值为存储的皇后所在的列，在下面代码体现的就是row 代表皇后所在的行，col代表皇后所在的列。total代表以供有多少种解决方案。

接下来查看摆放皇后的代码：

void queen(int row)

{

if(row==9)

total++;//如果第八个皇后摆放好了，那么解决方案加一

else
for（int col=1;col<=8;col++）
{

c[row]=col;

if(is_ok(row)）

queen(row+1);

}

}

对代码的详细解释：

首先对是否进展到第九行进行判定，为什么是第九行？因为当第一行（row=1）摆放了一个皇后后，会递归调用自己本身，并且行数加一(row=2)，由此递推可知当第八个皇后被摆放好后，同样会递归调用自己本身，并且行数加一，此时row会变为9（row的初值为1）。如果row等于9，那就说明第八个皇后已经被摆放好了，那么解决方案就加一。

同时呢，因为queen()本身是在一个for循环中被调用的，所以当解决方案加一后，会回溯到没有摆放第八个皇后的状况。例如当c(8)=7的时候摆放了第八个皇后，在递归调用queen时，row=9，解决方案加一，同时回溯到摆放第八个皇后的for循环中，c(8)=8，再判断是否可以摆放第8个皇后。如果不能摆放，当前摆放的第八皇后位置的for循环结束，回溯到摆放第七个皇后位置的for循环，重新摆放好第七个皇后的位置，再去递归调用摆放第8个皇后的位置。类似于这样回溯再执行递归的方式，当第七个皇后的各个列被遍历完了，就回溯到摆放第六个皇后的for循环，该换了第六个皇后的位置，在递归调用确定第七个皇后的位置，确定了第七个皇后的位置，再确定第八个皇后的位置。

当回溯到c(1)=8,并且各行的位置都被遍历判断过后，算法结束，所有的解决方案就都得出了。

再从row=1开始，了解下代码的运行。如果row=1,那么执行for循环。c(1)=1,因为是第一个位置，所以不会有冲突，第一个皇后就被安排在了坐标为（1，1）的格子。递归调用自身queen(2)来安排第二个皇后的位置，第二个皇后的位置不能在坐标为（2,1）,（2,2）的位置，因为这两个位置与皇后一冲突。第二个皇后位置安排在（2，3），再安排第三个皇后的位置，以此类推，当第八个皇后的位置安排好后，就回溯到安排第八个皇后的for循环进行遍历判断，再回溯到安排第七个皇后的for循环。

代码逻辑已经理解得比较清晰了，还有is_ok这个判断函数没有理解。

bool is_ok(int row){
     for(int j=1;j<row;j++){
         if(c[row]==c[j] || row-c[row]==j-c[j] || row+c[row]==j+c[j])
             return false;
     }
     return true;
 }

is_ok这个函数会传入当前的行数作为参数，也可以理解为第几个皇后，毕竟8行8个皇后，每一行都会有一个皇后。因为在放置放置前会判断当前已经放了几个皇后，所以 j 代表放置当前皇后时，之前已经放好的皇后中的一个遍历。例如，我当前放置的是第一个皇后（row=1），那么前面不存在任何皇后，我可以放在第一行的任何一列，所以直接 return true表示可以放置。当我放置的是第二个皇后的时候（row=2），就需要判定第二个皇后是否和第一个皇后同列，同斜线，一旦同列或者同斜线，就需要重新对第二个皇后的位置做更改。当第二个皇后的位置安排好后，对第三个皇后安排位置时就需要先对和第一个皇后先比较是否同行同斜线，再和第二个皇后比较是否同行同斜线。以此类推，代码中的被遍历的 j 就代表了被用来和当前要放置的皇后进行比较的之前摆放好的皇后。因为不可能同行，所以只判断同列，同斜线。

c[row]==c(j)判断是否同列；

例如:

c[1]=1;

c[2]=1；就表示两皇后同列，需要更改第二皇后的位置。

row-c[row] ==j-c[row];判断两皇后是否在右上到左下这条斜线上。

例如:

c[1]=1;

c[2]=2;

 1-c[1]==2-c[2]；就表示两皇后是否在右上到左下这条斜线上。

完整的代码如下：

#include<iostream>
#include<math.h>
using namespace std;

int total=0;
int c[9];
bool is_ok(int row){
     for(int j=1;j<row;j++){
         if(c[row]==c[j] || row-c[row]==j-c[j] || row+c[row]==j+c[j])
             return false;
     }
     return true;
 }
void queen(int row){
if(row==9)
total++;//如果第八个皇后摆放好了，那么解决方案加一,回溯到for循环。
else
for（int col=1;col<=8;col++）
{
c[row]=col;
if(is_ok(row)）
queen(row+1);
}
}

int main(){
    queen(1);
    cout<<total;
    return 1;
}

主要学习的博客地址：【基础算法】回溯法与八皇后问题

以上，祝好！