首页 > 代码库 > N皇后问题

N皇后问题

2024-07-05 23:22:18   232人阅读

N皇后问题

Time Limit : 2000/1000ms (Java/Other)   Memory Limit : 32768/32768K (Java/Other)
Total Submission(s) : 39   Accepted Submission(s) : 14

Font: Times New Roman | Verdana | Georgia

Font Size: ← →

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

2008 HZNU Programming Contest
 1 #include <stdio.h>
 2 #include <stdlib.h>
 3 int D,SIGN;
 4 int Map[12][12];
 5 
 6 void Sign_Part1(int i,int j,int D)
 7 {
 8     int ii,jj;
 9     for(ii=0;ii<D;ii++)
10        if(ii!=j) Map[i][ii]+=1;
11     for(jj=0;jj<D;jj++)
12         if(jj!=i)Map[jj][j]+=1;
13     for(ii=0;i-ii>=0&&j-ii>=0;ii++)
14         if(i-ii!=i&&j-ii!=j)Map[i-ii][j-ii]+=1;
15     for(ii=0;i+ii<D&&j+ii<D;ii++)
16         if(i+ii!=i&&j+ii!=j)Map[i+ii][j+ii]+=1;
17     for(ii=0;i-ii>=0&&j+ii<D;ii++)
18         if(i-ii!=i&&j+ii!=j)Map[i-ii][j+ii]+=1;
19     for(ii=0;i+ii<D&&j-ii>=0;ii++)
20         if(i+ii!=i&&j-ii!=j)Map[i+ii][j-ii]+=1;
21     Map[i][j]+=1;
22   /* for(ii=0;ii<D;ii++)
23     {
24         for(jj=0;jj<D;jj++)
25             printf("%d ",Map[ii][jj]);
26         putchar(‘\n‘);
27     }
28     putchar(‘\n‘);
29     getch();*/
30 }
31 
32 void Sign_Part2(int i,int j,int D)
33 {
34     int ii,jj;
35     for(ii=0;ii<D;ii++)
36        if(ii!=j) Map[i][ii]-=1;
37     for(jj=0;jj<D;jj++)
38         if(jj!=i)Map[jj][j]-=1;
39     for(ii=0;i-ii>=0&&j-ii>=0;ii++)
40         if(i-ii!=i&&j-ii!=j)Map[i-ii][j-ii]-=1;
41     for(ii=0;i+ii<D&&j+ii<D;ii++)
42         if(i+ii!=i&&j+ii!=j)Map[i+ii][j+ii]-=1;
43     for(ii=0;i-ii>=0&&j+ii<D;ii++)
44         if(i-ii!=i&&j+ii!=j)Map[i-ii][j+ii]-=1;
45     for(ii=0;i+ii<D&&j-ii>=0;ii++)
46         if(i+ii!=i&&j-ii!=j)Map[i+ii][j-ii]-=1;
47     Map[i][j]-=1;
48 }
49 
50 int Put_Chese(int x,int d,int D)
51 {
52     int i;
53     if(d==D){SIGN+=1;return 1;}
54     if(x+1>=D)return 0;
55     for(i=0;i<D;i++)
56     {
57         if(Map[x+1][i]==0)
58         {
59             Sign_Part1(x+1,i,D);
60             Put_Chese(x+1,d+1,D);
61             Sign_Part2(x+1,i,D);
62         }
63     }
64     return 0;
65 }
66 
67 int main()
68 {
69     int i,j,NUM[11];
70     D=1;
71     while(D)
72     {
73         if(D==11)break;
74         SIGN=0;
75         memset(Map,0,sizeof(Map));
76         for(i=0;i<D;i++)
77         {
78             Sign_Part1(0,i,D);
79             Put_Chese(0,1,D);
80             Sign_Part2(0,i,D);
81         }
82         NUM[D]=SIGN;
83         D++;
84     }
85 
86     while(scanf("%d",&j),j)
87         printf("%d\n",NUM[j]);
88     return 0;
89 }
View Code

 


联系
我们