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
Source
2008 HZNU Programming Contest
数据比较小，直接搜索吧，标记地图用累加的即可，因为结果是唯一的，所有把搜索的结果都保存在数组中，直接输出、
1 #include <stdio.h> 2 #include <stdlib.h> 3 #include <string.h> 4 int D,SIGN; 5 int Map[12][12]; 6 7 void Sign_Part1(int i,int j,int D) 8 { 9 int ii,jj; 10 for(ii=0;ii<D;ii++) 11 if(ii!=j) Map[i][ii]+=1; 12 for(jj=0;jj<D;jj++) 13 if(jj!=i)Map[jj][j]+=1; 14 for(ii=0;i-ii>=0&&j-ii>=0;ii++) 15 if(i-ii!=i&&j-ii!=j)Map[i-ii][j-ii]+=1; 16 for(ii=0;i+ii<D&&j+ii<D;ii++) 17 if(i+ii!=i&&j+ii!=j)Map[i+ii][j+ii]+=1; 18 for(ii=0;i-ii>=0&&j+ii<D;ii++) 19 if(i-ii!=i&&j+ii!=j)Map[i-ii][j+ii]+=1; 20 for(ii=0;i+ii<D&&j-ii>=0;ii++) 21 if(i+ii!=i&&j-ii!=j)Map[i+ii][j-ii]+=1; 22 Map[i][j]+=1; 23 /* for(ii=0;ii<D;ii++) 24 { 25 for(jj=0;jj<D;jj++) 26 printf("%d ",Map[ii][jj]); 27 putchar(' '); 28 } 29 putchar(' '); 30 getch();*/ 31 } 32 33 void Sign_Part2(int i,int j,int D) 34 { 35 int ii,jj; 36 for(ii=0;ii<D;ii++) 37 if(ii!=j) Map[i][ii]-=1; 38 for(jj=0;jj<D;jj++) 39 if(jj!=i)Map[jj][j]-=1; 40 for(ii=0;i-ii>=0&&j-ii>=0;ii++) 41 if(i-ii!=i&&j-ii!=j)Map[i-ii][j-ii]-=1; 42 for(ii=0;i+ii<D&&j+ii<D;ii++) 43 if(i+ii!=i&&j+ii!=j)Map[i+ii][j+ii]-=1; 44 for(ii=0;i-ii>=0&&j+ii<D;ii++) 45 if(i-ii!=i&&j+ii!=j)Map[i-ii][j+ii]-=1; 46 for(ii=0;i+ii<D&&j-ii>=0;ii++) 47 if(i+ii!=i&&j-ii!=j)Map[i+ii][j-ii]-=1; 48 Map[i][j]-=1; 49 } 50 51 int Put_Chese(int x,int d,int D) 52 { 53 int i; 54 if(d==D){SIGN+=1;return 1;} 55 if(x+1>=D)return 0; 56 for(i=0;i<D;i++) 57 { 58 if(Map[x+1][i]==0) 59 { 60 Sign_Part1(x+1,i,D); 61 Put_Chese(x+1,d+1,D); 62 Sign_Part2(x+1,i,D); 63 } 64 } 65 return 0; 66 } 67 68 int main() 69 { 70 int i,j,NUM[11]; 71 D=1; 72 while(D) 73 { 74 if(D==11)break; 75 SIGN=0; 76 memset(Map,0,sizeof(Map)); 77 for(i=0;i<D;i++) 78 { 79 Sign_Part1(0,i,D); 80 Put_Chese(0,1,D); 81 Sign_Part2(0,i,D); 82 } 83 NUM[D]=SIGN; 84 D++; 85 } 86 87 while(scanf("%d",&j),j) 88 printf("%d ",NUM[j]); 89 return 0; 90 }
修改：2015.5.8
1 #include <iostream> 2 #include <stdio.h> 3 #include <stdlib.h> 4 using namespace std; 5 int N,SUM; 6 int Map[12][12]; 7 void Cread_() 8 { 9 for(int i=0;i<=N+1;i++) 10 { 11 for(int j=0;j<=N+1;j++) 12 { 13 if(i==0||j==0||i==N+1||j==N+1)Map[i][j]=-1; 14 else Map[i][j]=0; 15 } 16 } 17 return ; 18 } 19 void Deal(int x,int y,int sign) 20 { 21 int i,j; 22 Map[x][y]+=sign; 23 for(i=1;Map[x][y-i]!=-1;i++)Map[x][y-i]+=sign; 24 for(i=1;Map[x][y+i]!=-1;i++)Map[x][y+i]+=sign; 25 for(i=1;Map[x+i][y]!=-1;i++)Map[x+i][y]+=sign; 26 for(i=1;Map[x-i][y]!=-1;i++)Map[x-i][y]+=sign; 27 28 for(i=1;Map[x-i][y-i]!=-1;i++)Map[x-i][y-i]+=sign; 29 for(i=1;Map[x-i][y+i]!=-1;i++)Map[x-i][y+i]+=sign; 30 for(i=1;Map[x+i][y-i]!=-1;i++)Map[x+i][y-i]+=sign; 31 for(i=1;Map[x+i][y+i]!=-1;i++)Map[x+i][y+i]+=sign; 32 } 33 34 void BFS(int x) 35 { 36 int i,j; 37 if(x==N+1) 38 { 39 SUM++; 40 } 41 for(j=1;j<=N;j++) 42 { 43 if(Map[x][j]==0) 44 { 45 Deal(x,j,1); 46 BFS(x+1); 47 Deal(x,j,-1); 48 } 49 } 50 } 51 int main() 52 { 53 int i; 54 int Sum[11]; 55 for(N=1;N<=10;N++) 56 { 57 SUM=0;Cread_(); 58 for(i=1;i<=N;i++) 59 { 60 if(Map[1][i]==0) 61 { 62 Deal(1,i,1); 63 BFS(2); 64 Deal(1,i,-1); 65 } 66 } 67 Sum[N]=SUM; 68 } 69 while(scanf("%d",&N)!=EOF) 70 { 71 if(N==0)break; 72 73 printf("%d ",Sum[N]); 74 } 75 return 0; 76 }