HDU 2553 N皇后问题 --- 经典回溯

题目链接： http://acm.hdu.edu.cn/showproblem.php?pid=2553

DFS+回溯

/* HDU 2553 N皇后问题 --- 经典回溯 */
#include <cstdio>
#include <cstring>

const int maxn = 15;
int cnt, n;
bool visit[3][maxn*2];//3个数组分别标记列，y+x斜线，y-x斜线是否冲突 注意要*2

/* 从第r行开始满足条件地放置皇后 r表示行(从0开始)*/
void dfs(int r){
    if (r == n){
        ++cnt; //搜索边界，只要到达这里，所有皇后比不冲突
    }
    else{
        //判断列的放置位置, i表示列-->y
        for (int i = 0; i < n; ++i){
            //由于y-x可能小于零而导致数组越界，故y-x应加上n 即i-r+n;
            if (!visit[0][i] && !visit[1][r + i] && !visit[2][r - i + n]){
                //若要打印解 则在此处记录
                //C[r] = i;
                visit[0][i] = visit[1][r + i] = visit[2][r - i + n] = 1;
                dfs(r + 1);
                visit[0][i] = visit[1][r + i] = visit[2][r - i + n] = 0;
            }
        }
    }
}

int main()
{
    while (scanf("%d", &n) == 1 && n){
        memset(visit, 0, sizeof (visit));
        cnt = 0;
        dfs(0);
        printf("%d
", cnt);
    }
    return 0;
}

然而，以上代码会超时，因此选择打表过：

/* HDU 2553 N皇后问题 --- 打表 */
#include <cstdio>

int main()
{
    int a[11] = { 0, 1, 0, 0, 2, 10, 4, 40, 92, 352, 724 };
    int n;
    while (scanf("%d", &n) == 1 && n){
        printf("%d
", a[n]);
    }

    return 0;
}