题解 P1219 【八皇后】

XG_Zepto · 2017-10-25 20:51:08 · 题解

这其实是一道很显然的回溯题，先放C++代码：

#include<cstdio>
#include<iostream>
using namespace std;
int ans[14],check[3][28]={0},sum=0,n;
void eq(int line)
{
    if(line>n)
    {
        sum++;
        if(sum>3) return;
        else
        {
            for(int i=1;i<=n;i++) printf("%d ",ans[i]);
            printf("\n");
            return;
        }
    }
    for(int i=1;i<=n;i++)
    {
        if((!check[0][i])&&(!check[1][line+i])&&(!check[2][line-i+n]))
        {
            ans[line]=i;
            check[0][i]=1; check[1][line+i]=1; check[2][line-i+n]=1;
            eq(line+1);
            check[0][i]=0; check[1][line+i]=0; check[2][line-i+n]=0;
        }
    }
}
int main()
{
    scanf("%d",&n);
    eq(1);
    printf("%d",sum);
    return 0;
}

代码中，

数组ans[line]=i表示第line行的第i列有一个棋子，保证了每行只有一个棋子；

数组check保证了每列和每条对角线上只有一个棋子，具体机制如下，没有一些奇奇怪怪难以理解的公式：

check[0]储存了棋子的列数，每一次进行ans[line]=i，使check[0][i]标记为已使用；

check[1]和check[2]储存对角线上的棋子分布情况：

如图，

对于一条从右上到左下的对角线，其上的棋子坐标应满足x+y为一定值；

对于一条从左上到右下的对角线，其上的棋子坐标应满足x-y为一定值，为了避免负数的产生，代码中用x-y+n来储存数字，具体效果读者可以自行研究。

对于语句

if((!check[0][i])&&(!check[1][line+i])&&(!check[2][line-i+n]))

只要满足这三个数字均为使用过，则在ans[line]=i处放置棋子，并将check数组中的相应数值标记为已使用，并对下一行进行搜索。

由于题目要求输出前3组解，所以计数器sum>3时不输出结果，最后在main函数中输出最终解的数量。