N皇后问题

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)

Total Submission(s): 38673    Accepted Submission(s): 16434

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

 

 

注意：题中说输入有若干行，并没有说只有N个输入，说明可能有重复的输入测试数据，所以应该提前打表，即事先将这N个结果保存在数组中，不然的话会超时。

 

1 #include 
      
        2  3 using namespace std; 4  5 int N;    //待输入的皇后数 6 int total;    //N个皇后的摆法总数 7 int queenPos[12];    //每一行的皇后摆放的位置(即每一行的皇后摆放在改行的列数) 8  9 void NQueen(int k)    //摆放第k个皇后(前k-1个皇后已经摆放好)10 {11     if (k == N)12         total++;13 14     for (int i = 0; i < N; ++i)        //逐个尝试第k个皇后的位置15     {16         int j;17         for (j = 0; j < k; ++j)        //和已经摆好的k个皇后进行位置比较，看是否冲突18         {19             if (queenPos[j] == i || abs(queenPos[j] - i) == abs(k - j))20                 break;21         }22 23         if (j == k)    //说明第i个位置和之前摆的k个皇后的位置都没有冲突24         {25             queenPos[k] = i;    26             NQueen(k + 1);27         }28     }29 }30 31 int main()32 {33     //直接像注释上这样写就会超时34     /*while (cin >> N && N != 0)35     {36         total = 0;37         NQueen(0);38         cout << total << endl;39 40     }*/41 42     //要先保存结果43     int ans[12];44     for (N = 1; N <= 10; ++N)45     {46         total = 0;47         NQueen(0);48         ans[N] = total;49     }50     while (cin >> N && N != 0)51     {52         cout << ans[N] << endl;53 54     }55     56 57     return 0;58 }