八皇后

Description

會(huì)下國(guó)際象棋的人都很清楚：皇后可以在橫、豎、斜線上不限步數(shù)地吃掉其他棋子。如何將8個(gè)皇后放在棋盤上（有8 * 8個(gè)方格），使它們誰(shuí)也不能被吃掉！這就是著名的八皇后問題。?
對(duì)于某個(gè)滿足要求的8皇后的擺放方法，定義一個(gè)皇后串a(chǎn)與之對(duì)應(yīng)，即a=b₁b₂...b₈，其中b_i為相應(yīng)擺法中第i行皇后所處的列數(shù)。已經(jīng)知道8皇后問題一共有92組解（即92個(gè)不同的皇后串）。
給出一個(gè)數(shù)b，要求輸出第b個(gè)串。串的比較是這樣的：皇后串x置于皇后串y之前，當(dāng)且僅當(dāng)將x視為整數(shù)時(shí)比y小。

Input

第1行是測(cè)試數(shù)據(jù)的組數(shù)n，后面跟著n行輸入。每組測(cè)試數(shù)據(jù)占1行，包括一個(gè)正整數(shù)b(1 <= b <= 92)

Output

輸出有n行，每行輸出對(duì)應(yīng)一個(gè)輸入。輸出應(yīng)是一個(gè)正整數(shù)，是對(duì)應(yīng)于b的皇后串。

Sample Input

2 1 92

Sample Output

15863724 84136275

題解：回溯法的應(yīng)用。注意判斷對(duì)角線之前是否存在皇后的方法。

題目地址：http://bailian.openjudge.cn/practice/2754/

代碼：
1 #include<stdio.h> 2 #include<string.h> 3 #include<stdbool.h> 4 5 int i,j,n,m,num, 6 a[10],b[100][10]; 7 8 bool f[3][50]; 9 10 int 11 pre() 12 { 13 memset(f,1,sizeof(f)); 14 memset(a,0,sizeof(a)); 15 memset(b,0,sizeof(b)); 16 num=0; 17 return 0; 18 } 19 20 void 21 dfs(int x) 22 { 23 int i; 24 if(x==9) 25 { 26 num++; 27 for(i=1;i<=8;i++) 28 b[num][i]=a[i]; 29 } 30 31 for(i=1;i<=8;i++) 32 if (f[0][i]&&f[1][x+i]&&f[2][x-i+8]) 33 { 34 a[x]=i; 35 f[0][i]=f[1][x+i]=f[2][x-i+8]=0; 36 dfs(x+1); 37 f[0][i]=f[1][x+i]=f[2][x-i+8]=1; 38 } 39 } 40 41 int 42 main() 43 { 44 int cas,i; 45 scanf("%d",&cas); 46 pre(); 47 dfs(1); 48 while(cas--) 49 { 50 scanf("%d",&n); 51 for(i=1;i<=8;i++) 52 printf("%d",b[n][i]); 53 printf("\n"); 54 } 55 return 0; 56 }

?

?

轉(zhuǎn)載于:https://www.cnblogs.com/sxiszero/p/3695622.html

總結(jié)

以上是生活随笔為你收集整理的[OpenJudge] 百练2754 八皇后的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。