本文共 873 字，大约阅读时间需要 2 分钟。

所谓八皇后问题就是有一个8*8的棋盘，然后在这个棋盘中摆放八个皇后，并且要求这八个皇后不能同时出现在同一行同一列或者同意线上。

八皇后问题是最经典的搜索回溯问题，非常的基础，下面介绍两种解法，第一种是递归调用的解法，如果我用一位数组存储八皇后的位置的话，定义一个数组c[i]=j,表示在第i行的第j列摆放一个皇后，因为每个皇后都存储在不同的行上，这样我们就可以忽略行的问题，只考虑列元素的位置，这个问题的关键在于怎么递归调用上，每次我们从第i行的第j列开始寻找，如果满足条件则递归寻找第i+1行，如果不满足寻找第j+1列的元素，直到i==8查找到一个存储模式，递归终止。

#include 
   
    using namespace std;int n=8;int c[10];int cnt;void print(){    for(int i=0;i
   

另一种方法就是搜索回溯，其实也就是递归，只不过换了一种写法，更像是一颗抽象的树形结构，如果子结点不满足条件，回溯到上一个结点，并”清零“也就是回溯到上一步，重新赋值重新计算。

搜索回溯和核心就是在递归调用后回溯一步，回到上一个结点，也就是以下这个过程

if(i==8) 

#include 
   
    using namespace std;int a[9]={0};bool b[9]={0},c[17]={0},d[17]={0};int sum=0;void print(){    sum++;    for(int i=1;i<=8;i++)    {        for(int j=1;j<=8;j++)        {            if(a[i]==j)                cout<<"1 ";            else                cout<<"0 ";        }        cout<
   

转载地址：http://kgoo.baihongyu.com/