从八皇后问题看回溯法

八皇后问题是入门回溯法的经典问题，本文借用八皇后问题来阐述一下笔者对于八皇后问题的一些看法。

在我看来，回溯法有点像高中时候的排列组合，都是可以在有限的步骤中完成，而每一步有只有有限的选择，这句话也构成了回溯法的核心。

每一次成功的放置，代表着解答树上某一个节点的产生：下面结合八皇后问题来描述

先来看代码

//回溯法用于可以在有限的步骤中得到结果，而每一步又只有有限次的选择的情况
//解答树可以这样来理解，解答树的每一个节点是在它的那一步看起来是正确的合理的。
//其实一个完整的解答树（包括哪些失败的不合理的点）是把每一步的每一个选择都作为了一个节点，虽然其中有失败的节点。
//回溯法的作用就是找出（不完整的解答树）
//提高效率的方式？在判断是否符合条件的操作上下功夫
//比如说在求全排列的时候，DFS比next_permutation效率高的原因？
#include
#include
#include
using namespace std;

const int maxn = 50 + 5;
int tot = 0;
int n;
int vis[3][maxn];


void search(int cur)
{
    if(cur == n)
        tot++;
    else 
    {
        for(int i = 0;i )
        {
            if(!vis[0][i] && !vis[1][cur + i] && !vis[2][cur - i + n])
            {
                vis[0][i] = vis[1][cur + i] = vis[2][cur - i + n] = 1;
                search(cur + 1);
                vis[0][i] = vis[1][cur + i] = vis[2][cur - i + n] = 0;
            }
        }
    }
}


int main()
{
    memset(vis,0,sizeof(vis));
    n = 8;
    search(0);
    printf("%d\n",tot);return 0;
}

首先，完成八皇后问题只需要八步，当然对应于上面这个函数search中的形参cur.

每一步的选择有多少种呢？在八皇后问题中，第i步的，代表要往第i行(行号和步骤号都从0开始)放置皇后，而每一步实际上都有8种选择，因为只能往0~7列上放置皇后。所以完整的（包括了失败的节点）解答树应该是一棵8叉完全树。但是，在这些选择中并不是每一种选择都是成功的，有的在本步就可以确定是错误的，有的需要结合后面几步来判断是不是正确的，但总的来说，只有当前这一步的选择在当前这一步被认为正确以后，真正意义上的解答树中的节点就生成了。

而回溯的意义就是，当在某一步做完选择之后，不管这一步在整个解答树中看起来是正确的还是错误的，都会去判断这一步的下一种选择，就好像是又弯了回来一样。

解答树中的节点个数是确定的，可以提高效率的地方在：如何迅速的判断在当前这一步中的选择是正确的。

方法有两种：

第一种是去遍历之前已经确定好的哪些行，与当前行的选择做比较，来判断是不是正确的

第二种是直接判断我们想要放皇后的      行/列/主对角线/副对角线   是否可以放置。这需要一个vis的二维数组vis[3][maxn]，第一行用来判断列，第二行主对角线，第三行副对角线。

可以明显的看出来，第二种的速度比第一种快多了。

联想到之前的全排列问题：

全排列问题的解决实际上也是回溯法

一共有n个位置需要确定是什么

每个位置上一共有n种选择

在非可重集上的DFS方式中，在n个选择中判断的方式就是vis数组

而在可重集上求排列（next_permutation）中，在n个选择中判断的方式是遍历已经放好元素的cur-1个位置

回溯法需要好好的品味，总的来说只有三步，第一：有几个步骤，第二：每一步有多少种选择，第三：判断这次选择是否符合条件的方式