文章出處

N皇后問題

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 13319 Accepted Submission(s): 6028

Problem Description

在N*N的方格棋盤放置了N個皇后，使得它們不相互攻擊（即任意2個皇后不允許處在同一排，同一列，也不允許處在與棋盤邊框成45角的斜線上。
你的任務是，對于給定的N，求出有多少種合法的放置方法。

Input

共有若干行，每行一個正整數N≤10，表示棋盤和皇后的數量；如果N=0，表示結束。

Output

共有若干行，每行一個正整數，表示對應輸入行的皇后的不同放置數量。

Sample Input

1 8 5 0

Sample Output

1 92 10

這是一道學習回溯法的經典例題。

直接用解答樹進行DFS搜索。

我們可以讓vis[0][i]表示行， vis[1][cur+i]表示主對角線， vis[2][cur-i+n]表示從對角線（由于cur-i可能為負值，所以都加上一個n）。

#include<cstdio>
#include<cstring>
#include<algorithm>

int C[50], vis[3][50], tot, n;

void dfs(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][i+cur]=vis[2][cur-i+n] = 1;
            dfs(cur+1);
            vis[0][i] = vis[1][i+cur]=vis[2][cur-i+n] = 0;
        }
    }
}

int main()
{
    while(scanf("%d", &n)!=EOF&&n)
    {
        tot = 0;
        memset(vis, 0, sizeof(vis));
        dfs(0);
        printf("%d\n", tot);
    }
    return 0;
}

無奈上面的代碼依然超時。然而小恪機智的發現，此題的數據是這么的親民！就10個數。用上面的程序打表飄過。

#include<cstdio>
int C[11] = {0, 1, 0, 0 ,2 ,10 ,4 ,40 ,92 ,352, 724};

int main()
{
    int n;
    while(scanf("%d", &n)!=EOF&&n)
    {
        printf("%d\n", C[n]);
    }
    return 0;
}