點(diǎn)擊打開(kāi)鏈接

N皇后問(wèn)題

Time Limit: 2000/1000 MS (Java/Others)????Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 30795????Accepted Submission(s): 13372

?

Problem Description

在N*N的方格棋盤(pán)放置了N個(gè)皇后，使得它們不相互攻擊（即任意2個(gè)皇后不允許處在同一排，同一列，也不允許處在與棋盤(pán)邊框成45角的斜線上。
你的任務(wù)是，對(duì)于給定的N，求出有多少種合法的放置方法。

Input

共有若干行，每行一個(gè)正整數(shù)N≤10，表示棋盤(pán)和皇后的數(shù)量；如果N=0，表示結(jié)束。

Output

共有若干行，每行一個(gè)正整數(shù)，表示對(duì)應(yīng)輸入行的皇后的不同放置數(shù)量。

Sample Input

1 8 5 0

Sample Output

1 92 10

Author

cgf

Source

2008 HZNU Programming Contest

Recommend

lcy???|???We have carefully selected several similar problems for you:??1016?1312?1181?1010?2614

回溯法：

當(dāng)把問(wèn)題分成若干步驟并遞歸求解時(shí)，如果當(dāng)前步驟沒(méi)有合法選擇，則函數(shù)將返回上一級(jí)遞歸調(diào)用，這種現(xiàn)象稱為回溯。

遞歸枚舉算法的過(guò)程中，把生成和檢查有機(jī)的結(jié)合起來(lái)，從而減少不必要的枚舉，通常稱為回溯算法

思路：
恰好每一行放置一個(gè)皇后，用c[x]表示第x行皇后的列編號(hào)，

則問(wèn)題變?yōu)槿帕猩蓡?wèn)題，0-7的全排列為8！=40320，枚舉量不會(huì)超過(guò)它

既然是逐行放置的，則皇后肯定不會(huì)橫向攻擊，只需要檢查縱向和斜向攻擊即可。

條件“?cur-C[cur] == j-C[j] || cur+C[cur] == j+C[j]?” 用來(lái)判斷皇后 (cur,C[cur]) 和 (j,C[j]) 是否在同一條對(duì)角線上。

?求解答案的代碼：

#include<bits/stdc++.h> using namespace std; //n皇后 int tot;//解的個(gè)數(shù) int c[12];//c[x]表示第x行皇后的列編號(hào) void search(int n,int cur) {if(cur==n)//遞歸邊界tot++;//只要走到這里，所有皇后必然不沖突elsefor(int i=0;i<n;i++){//恰好每行每列各放置一個(gè)皇后int ok=1;c[cur]=i;//嘗試把第cur行的皇后放在第i列for(int j=0;j<cur;j++)//檢查是否與前面的皇后沖突if(c[cur]==c[j]||cur-c[cur]==j-c[j]||cur+c[cur]==j+c[j]){ok=0;break;}if(ok) search(n,cur+1);//如果合法，則繼續(xù)遞歸} } int main() {/*while(cin>>n&&n){tot=0;search(0);cout<<tot<<endl;}*/for(int n=0;n<12;n++){tot=0;search(n,0);cout<<tot<<",";}return 0; }

AC代碼

#include<iostream> using namespace std; int main() {int a[]={1,1,0,0,2,10,4,40,92,352,724,2680};int n;while(cin>>n&&n){cout<<a[n]<<endl;}return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的HDU2553 N皇后 回溯法+打表的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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