[USACO][Section 1.5][搜索] Checker Challenge

题目大意：

给出一个整数n，表示棋盘大小为n*n。找出所有棋子摆放n个棋子的方案，要求每行、每列、每条对角线上至多有一个棋子。

思路：

利用深搜按行搜索。需要注意的是对角线的标记方式，下面程序采用的方法是由上至下将棋子所在位置按两条对角线方向映射到(t1,0)和(t2,n)位置，并用northwest[t1]、southeast[t2]进行标记。

代码：

/*
ID: lujunda1
LANG: C++
PROG: checker
*/
#include
#include
using namespace std;
bool row[14],col[14],southeast[28],northwest[28];
//row[]、col[]分别用来判断某行、某列是否已有棋子。
//southeast[]、northwest[]分别用来判断某点所在的两条对角线上是否已有棋子。 
int n,res[14],sum=0;
//res[]存储每行的棋子位置。
//sum表示方案数量。 
bool check(int y,int x)
//检查(x,y)所处行、列、对角线上是否有其他棋子。 
{
    if(row[y]||col[x]||southeast[y+(n-x)]||northwest[y+x-1])
        return false;
    return true;
}
void mark(int i,int j,bool val)
//对(i,j)所处行、列、对角线进行标记或取消标记。 
{
    row[i]=val;
    col[j]=val;
    southeast[i+(n-j)]=val;
    northwest[i+j-1]=val;
}
void dfs(int r)
//按行递归搜索所有解决方案 
{
    if(r==n+1&&sum++<3)
    //输出前3个解决方案。 
    {
        for(int i=1;i<=n;i++)
            if(i-1)
                printf(" %d",res[i]);
            else
                printf("%d",res[i]);
        printf("\n");
        return;
    }
    for(int i=1;i<=n;i++)
    //遍历r行上的n个位置。 
        if(check(r,i))
        //若(r,i)位置可以摆放棋子。 
        {
            mark(r,i,true);
            //对(r,i)位置进行标记。 
            res[r]=i;
            //记录结果。 
            dfs(r+1);
            //递归到下一行。 
            mark(r,i,false);
            //取消标记。 
        }
}
int main()
{
    freopen("checker.in","r",stdin);
    freopen("checker.out","w",stdout);
    for(int i=1;i<14;i++)
        row[i]=col[i]=false;
    for(int i=1;i<28;i++)
        southeast[i]=northwest[i]=false;
    scanf("%d",&n);
    dfs(1);
    printf("%d\n",sum);
}