N皇后问题

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

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 

Author

cgf

Source

Recommend

lcy

DFS + 打表

深搜代码：

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #include 
         
           5 #include 
          
            6 #include 
           
             7 #define LL long long 8 #define MAXI 2147483647 9 #define MAXL 922337203685477580710 #define dg(i) cout << "*" << i << endl;11 using namespace std;12 13 int n, q[11]; //每行一个皇后，第i行的皇后的位置是q[i]14 15 bool check(int r)16 {17 int i;18 for(i = 1; i < r; i++)19 if(q[i] == q[r])20 return false;21 for(i = r - 1; i > 0; i--)22 if(q[i] == q[r] - (r - i) || q[i] == q[r] + r - i)23 return false;24 return true;25 }26 27 //r为将要处理的行28 int DFS(int r)29 {30 if(r == n + 1) return 1;31 int cnt = 0;32 for(q[r] = 1; q[r] <= n; q[r]++)33 {34 if(check(r))35 {36 cnt += DFS(r + 1);37 }38 }39 return cnt;40 }41 42 int main()43 {44 int ans;45 while(scanf("%d", &n) && n)46 {47 memset(q, 0, sizeof(q));48 ans = 0;49 for(q[1] = 1; q[1] <= n; q[1]++)50 {51 ans += DFS(2);52 }53 printf("%d\n", ans);54 }55 return 0;56 }