回溯法解决 八皇后问题

什么是八皇后

八皇后问题（英文：Eight queens），是由国际象棋棋手马克斯·贝瑟尔于1848年提出的问题，是回溯算法的典型案例。

问题表述为：在8×8格的国际象棋上摆放8个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。高斯认为有76种方案。1854年在柏林的象棋杂志上不同的作者发表了40种不同的解，后来有人用图论的方法解出92种结果。如果经过±90度、±180度旋转，和对角线对称变换的摆法看成一类，共有42类。计算机发明后，有多种计算机语言可以编程解决此问题。

这个国王好居然有八个皇后 

八皇后问题规则

以下是一个棋盘，假设以左上角为原点（1，1），向右为y轴，向下为x轴。八皇后的规则是当放了一颗棋子后，这一横排，竖排，左右斜排都不能再放置了。

如图，假设在(3，4)放一颗棋子。

那么，在(1,2),(1,4),(1,6),(2,3),(2,4),(2,5),(3,1),(3,2),(3,3),(3,4),(3,5),(3,6),(3,7),(3,8),(4,3),(4,4),(4,5),(5,2),(5,4),(5,6),(6,1),(6,4),(6,7),(7,4),(7,8),(8,4)都不能再放置棋子了。

然后请问当8个棋子都能按上去规则放完，有多少种情况。

以下，就是解法的其中之一，以每一列(y)轴来计，记为: 1 7 4 6 8 2 5 3

解决思路

很明显，这有点类似于数独问题。

解法思路就是：从第一行开始(x轴)  依次搜这行的每一列(y轴) ，如果该坐标没有被标记过，那么记录(1,1)放下了棋子，并且这行，这列，斜排都做一个标记。然后就先在这放第一颗棋子，接下来搜索第二行。

同理，依次搜第二行的每一列，可以得知在放(1,1)的时候，(2,1),(2,2)是不能再放的，所以只能先放(2,3)，然后与(2,3)有关的点做标记。接下来搜第三行.....

当某一行，出现全部都不能放的时候，就说明之前的假设有问题，所以就必须返回上一行，在上一行可行的下一个格子放棋子，(若放不了，那么还得再返回）然后继续按上述要求搜索....

当8个棋子都能放完的时候，说明有一种方案成立了，但是还没完，所以把这种方案做记录，然后返回继续搜....

直到所有情况都搜完，那么程序结束。

思路是这样，但是代码怎么去实现呢？

很明显，这是典型的回溯法。

因此，套用回溯法的模板。

void Backtrack(原参数区间/或者参数) {
    if(达到目的/或者撞到“南墙”) {
        存放结果;//或者输出结果,输出最好调用新函数
        return;
    }
 
    进行一些操作(根据实际情况可省去);
 
    for(int i=1;i<=子区间个数(换句话说,也就是父亲节点的度);i++) {//或者子参数个数
        if(没被记录) {
            做记录;//已经搜过就不再搜了
 
            Backtrack(子区间或者下个搜索的参数); //调用子区间或者参数
 
            销毁记录;//搜完,或者撞到南墙,就销毁记录
        }
    }
}

按照上述思路，是从每一行开始，依次搜每一列。所以大致确定：

代码

int hang[N],lie[N],dia1[N*2],dia2[N*2];
//hang记录每一行,lie记录每一列
//dia1记录左斜,dia2记录右斜
const int n=8;//8皇后
vector<int>queen;//queen代表每一组的8个数
vector<vector<int>>ans;//ans储存最终结果,ans[1]代表第一组,ans[2]代表第二组结果
//做记录
void record(int x,int y) {
    queen.push_back(y);
    hang[x]=1;lie[y]=1;
    dia1[x+y-1]=1;dia2[y-x+n]=1;
}
//清除记录
void derecord(int x,int y) {
    hang[x]=0;lie[y]=0;
    dia1[x+y-1]=0;dia2[y-x+n]=0;
    queen.pop_back();
}
//回溯
void backtrack(int x) {
    //当搜到n+1,也就是越界的情况，记录数值并返回
    if(x==n+1) {
        return;
    }
    //从1到n开始搜
    for(int y=1;y<=n;y++) {
        if(!hang[x]&&!lie[y]&&!dia1[x+y-1]&&!dia2[y-x+n]) {
            record(x,y);
            backtrack(x+1);
            derecord(x,y);
        }
    }
}
int main() {
	backtrack(1);
    //依次打印结果
	for(int i=0;i<ans.size();i++) {
		for(int j=0;j<n;j++) {
			cout<<ans[i][j]<<" ";
		}
		cout<<endl;
	}
	return 0;
}

拓展n皇后问题

n皇后的话，就是把上述的常量n修改为可以输入的值即可，核心代码不变。

洛谷P1219 n皇后问题