7.4 回溯法

引入

无论是排列生成还是子集枚举,前面都给出了两种思路:递归构造和直接枚举。直接枚举法的优点是思路和程序都很简单,缺点在于无法简便地减少枚举量——必须生成所有可能的解然后一一检查。
另一方面,在递归构造中,生成和检查过程可以有机结合起来,从而减少不必要的枚举。这就是回溯法。

八皇后问题

在棋盘上放置八个皇后,使得它们相互无法攻击,找出所有解。

分析

最简单的思路是把问题转化为在六十四个格子中选一个子集,使得八个格子互相不在同一列同一行或者同一对角线上。这就转化为了子集枚举问题。然而这样的枚举量会达到1<<64
第二个思路,把问题转化为从六十四个格子中选出八个格子,这就转化为组合生成问题。但是这样依然要枚举4×1e9次。
观察一下问题,我们会发现恰好每行每列一个皇后。这样就成为了全排列生成问题。0~7的全排列只有8!=40320个。

代码

下面的程序只要读入n,并且将tot清零,然后调用search(0),就可以得到解的个数tot

void search(int cur){
    if(cur == n) tot++;
    else for(int i =0; i < n; i++){
        int ok = 1;
        C[cur] =i;
        for(int j = 0; j < cur; j++)
            if(C[cur] == C[j] || cur-C[cur] == j-C[j] || cur+C[cur] == j+C[j])
                { ok= 0; break; } // 检查皇后是否冲突。
        if(ok) search(cur+1);
    }
 }

程序效率还可以进一步提高:利用二维数组直接判断当前尝试的皇后所在列和两个对角线是否已经有其他的皇后。注意到主对角线标识y-x可能为负。

void search(int cur){
    if(cur == n) tot++;
    else for(int i = 0; i < n; i++){
        if(!vis[0][i] && !vis[1][cur+i] && !vis[2][cur-i+n]){
            C[cur] = i;
            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;
        }
    }
}

这里有个很关键的地方:vis数组的使用。vis数组的含义是已经放置的皇后占据的主对角线和副对角线。将来放置的皇后不应该修改这些值。
一般地,如果在回溯法中修改了辅助的全局变量,则一定要及时把它们恢复原状。如果这个函数有多个出口,需要在每个出口处恢复被修改的值。

其他例子

例题:素数环(UVa 524)

输入正整数n,把整数1,2,3……n组成一个环,使得相邻的两个整数之和均为素数。输出时从整数1开始逆时针排列。同一个环应当恰好输出一次。

解答一:暴力枚举全排列

for(int i = 1; i <= n*2; i++) isp[i] = is_prime(i);
for(int i = 0; i < n; i++) A[i] = i+1;
do{
    int ok = 1;
    for(int i = 0; i < n; i++) if(!isp[A[i]+A[(i+1)%n]])
        { ok = 0; break; }
    if(ok){
        for (int i = 0; i < n; i++) printf("%d ", A[i]);
        printf("\n");
    }
}while(next_permutaion(A+1, A+n));

解答二:回溯法

void dfs(int cur){
    if(cur == n && isp[A[0]+A[n-1]]){
        for(int i = 0; i < n; i++) printf("%d ", A[i]);
        printf("\n");
    }
    else for(int i = 2; i <= n; i++)
        if(!ivs[i] && isp[i+A[cur-1]]){
            A[cur] = i;
            vis[i] =1;
            dis(cur+1);
            vis[i] =0;
        }
}

例题:困难的串(UVa 129)

例题:带宽(UVa 140)

例题:天平难题(UVa 1354)