㈠ N皇後問題
一、問題描述：
在n×n格的棋盤上放置彼此不受攻擊的n個皇後。按照國際象棋的規則，皇後可以攻擊與之處在同一行或同一列或同一斜線上的棋子。n後問題等價於再n×n的棋盤上放置n個皇後，任何2個皇後不妨在同一行或同一列或同一斜線上。
輸入：
給定棋盤的大小n (n ≤ 13)
輸出：
輸出有多少種放置方法。
二、解題思路：
要解決N皇後問題，其實就是要解決好怎麼放置這n個皇後，每一個皇後與前面的所有皇後不能在同一行、同一列、同一對角線，在這里我們可以以行優先，就是說皇後的行號按順序遞增，只考慮第i個皇後放置在第i行的哪一列，所以在放置第i個皇後的時候，可以從第1列判斷起，如果可以放置在第1個位置，則跳到下一行放置下一個皇後。如果不能，則跳到下一列...直到最後一列，如果最後一列也不能放置，則說明此時放置方法出錯，則回到上一個皇後向之前放置的下一列重新放置。此即是回溯法的精髓所在。當第n個皇後放置成功後，即得到一個可行解，此時再回到上一個皇後重新放置尋找下一個可行解...如此後，即可找出一個n皇後問題的所有可行解。
三、復雜度分析：
關於N皇後問題的復雜度問題可以說是眾說紛紜了，自己也改變過好幾次，剛開始以為棋盤是n行n列，所以理所當然應該是n^2,後來發現在每列選擇可否放置的比較上又做了一次循環，所以應該是n^3，但想了很久，發現判斷可否放置的時候不是每次都循環到n,它是根據皇後i的取值而變化的，所以復雜度應該是1/3 n^3左右，即是小於n^3的。
四、測試代碼：
在這里我寫了兩個實現方法，一個是遞歸回溯，一個是迭代回溯，思路都一樣，只是形式不同罷了。
遞歸回溯：
C代碼
#include<stdio.h>
#define N 15
int n; //皇後個數
int sum = 0; //可行解個數
int x[N]; //皇後放置的列數
int place(int k)
{
int i;
for(i=1;i<k;i++)
if(abs(k-i)==abs(x[k]-x[i]) || x[k] == x[i])
return 0;
return 1;
}
int queen(int t)
{
if(t>n && n>0) //當放置的皇後超過n時，可行解個數加1，此時n必須大於0
sum++;
else
for(int i=1;i<=n;i++)
{
x[t] = i; //標明第t個皇後放在第i列
if(place(t)) //如果可以放在某一位置，則繼續放下一皇後
queen(t+1);
}
return sum;
}
int main()
{
int t;
scanf("%d",&n);
t = queen(1);
if(n == 0) //如果n=0，則可行解個數為0，這種情況一定不要忽略
t = 0;
printf("%d",t);
return 0;
}
迭代回溯：
C代碼
#include<stdio.h>
#define N 15
int n;
int sum = 0;
int x[N];
int place(int k)
{
int i;
for(i=1;i<k;i++)
if(abs(k-i)==abs(x[k]-x[i]) || x[k] == x[i])
return 0;
return 1;
}
int queen()
{
x[1] = 0;
int t=1;
while(t>0)
{
x[t]+=1;
while(x[t]<=n && !place(t))
x[t]++;
if(x[t]<=n)
if(t == n)
sum++;
else
x[++t] = 0;
else
t--;
}
return sum;
}
int main()
{
int t;
scanf("%d",&n);
t = queen();
printf("%d",t);
return 0;
}
迭代回溯的注釋因為和遞歸回溯差不多，所以就不再附註了。在這里我們可以看到，遞歸回溯非常簡單，結構很清晰，但它有一個潛在的問題存在，即當隨著變數n的增大，遞歸法的復雜度也將成幾何級增長，也有可能會出現重復的情況，所以我們在解決問題時，如果能用迭代法解決，最好還是不要用遞歸法，除非你已經對這個遞歸了如指掌了。
通過這個N皇後問題，我想大概已經把回溯法講得很清楚了吧，回溯法得到的解展開就是一個樹，很多方法都是可以通過回溯法來解決的，效率很高，但如果基數過大的話，回溯法就顯得不是那麼適用了，這也是回溯法的弱勢吧。比如說這個N皇後問題，好像當n>60的時候，回溯法就不能完全地解決問題了，這時可以考慮用概率演算法來解決，它可以解決很大的基數，只不過結果不是很精確而已。所以我們在面對一個問題時，具體是使用什麼演算法還是要結合實際情況來考慮的，目的都是更方便、更准確地解決問題。
㈡ c語言n皇後問題
if(i==n-1)執行到了，但是 i 取值有問題，j=0的時候i就增加到5，j>0之後if(i==n-1)就不可能成立了
㈢ N皇後回溯問題 解釋下這程序 C語言
#include <stdio.h>
#define DelayTime 20000
#define TopX 10
#define TopY 5
int N;/*此處開始設置幾個全局變數 N即代表皇後個數*/
int a[8], b[15], c[15];
int Num = 0;/*Num代表解決方法個數*/
int row;
/******************************************************************************/
void BackTrack (int row)
{
int col;
for (col=1; col<=N; col++)
{
if (a[col-1] + b[row+col-2] + c[row-col+N-1] == 0) /*1，為什麼這里要等於0？ if語句里的3個表達式都代表什麼呢？*/
{
a[col-1] = 1;
b[row+col-2] = 1;
c[row-col+N-1] = 1;
gotoxy(col*2 + TopX, row + TopY); /* 2，這里的gotoxy（）語句是做什麼的？ 僅僅是跳到相應位置，列印Q*/
putch('Q');
if (row < N)
{
BackTrack (row + 1); /* 3，這句什麼意思? 遞歸調用*/
}
else
{
Num++;
gotoxy(40, 9); /* 4，這里又是做什麼的？什麼用？*/
printf("Num: %d ", Num);
delay(DelayTime); /* 5，這里又有什麼用？延遲*/
}
a[col-1] = 0;
b[row+col-2] = 0; /* 6，這個三個表達式怎麼又成0了？*/
c[row-col+N-1] = 0;
gotoxy(col*2 + TopX, row + TopY); /* 7，這又是什麼用?*/
putch('.');
}
}
}
/********************************************************************************/
void main()
{
int i, j;
clrscr();
gotoxy(1, 10);
printf("Input the number of queen: ");
while(N <= 0 || N > 100)
{
scanf("%d", &N);
if(N > 100) printf("Two huge number, input again:");
if(N <= 0) printf("Can's smaller than 1, again:");
}
clrscr();
for(i=1; i<=N; i++)
{
for(j=1; j<=N; j++)
{
gotoxy(i*2 + TopX, j + TopY); /* 8，這里又是什麼用? 將游標移動到指定位置說明：gotoxy（x，y）將游標移動到指定行y和列x。
*/
putch('.');
}
}
BackTrack(1); /* 9，為什麼是1呢？不是應該傳遞的是皇後的數量嗎?第一行，N為皇後的數量*/
gotoxy(12, 17); /* 10，這又是什麼用？*/
printf ("There are %d kinds of solution.\n", Num);
getch();
}
㈣ N皇後問題的回溯法求解屬於子集樹還是排列樹 詳細講一講
「八皇後」問題遞歸法求解 (Pascal語言) 八皇後問題是一個古老而著名的問題，是回溯演算法的典型例題。該問題是十九世紀著名的數學家高斯1850年提出：在8X8格的國際象棋上擺放八個皇後，使其不能互相攻擊，即任意兩個皇後都不能處於同一行、同一列或同一斜線上，問有多少種擺法。高斯認為有76種方案。1854年在柏林的象棋雜志上不同的作者發表了40種不同的解，後來有人用圖論的方法解出92種結果。現代教學中，把八皇後問題當成一個經典遞歸演算法例題。 演算法分析：數組a、b、c分別用來標記沖突，a數組代表列沖突，從a[0]~a[7]代表第0列到第7列，如果某列上已經有皇後，則為1，否則為0；數組b代表主對角線沖突，為b[i-j+7]，即從b[0]~b[14]，如果某條主對角線上已經有皇後，則為1，否則為0；數組c代表從對角線沖突，為c[i+j]，即從c[0]~c[14]，如果某條從對角線上已經有皇後，則為1，否則為0；另優化：第一個皇後在1~4格，最後*2，即為總解數 } program queens; var a:array [1..8] of integer; b,c,d:array [-7..16] of integer; t,i,j,k:integer; procere print; begin t:=t+1; write(t,': '); for k:=1 to 8 do write(a[k],' '); writeln; end; procere try(i:integer); var j:integer; begin for j:=1 to 8 do {每個皇後都有8種可能位置} if (b[j]=0) and (c[i+j]=0) and (d[i-j]=0) then {判斷位置是否沖突} begin a:=j; {擺放皇後} b[j]:=1; {宣布佔領第J行} c[i+j]:=1; {佔領兩個對角線} d[i-j]:=1; if i<8 then try(i+1) {8個皇後沒有擺完，遞歸擺放下一皇後} else print; {完成任務，列印結果} b[j]:=0; {回溯} c[i+j]:=0; d[i-j]:=0; end; end; begin fillchar(a,sizeof(a),0); {初始化數組} fillchar(b,sizeof(b),0); fillchar(c,sizeof(c),0); fillchar(d,sizeof(d),0); try(1);{從第1個皇後開始放置} end. 「八皇後」問題遞歸法求解 (C語言) ＃i nclude "stdio.h" static char Queen[8][8]; static int a[8]; static int b[15]; static int c[15]; static int iQueenNum=0; //記錄總的棋盤狀態數 void qu(int i); //參數i代錶行 int main() { int iLine,iColumn; //棋盤初始化，空格為*，放置皇後的地方為@ for(iLine=0;iLine<8;iLine++) { a[iLine]=0; //列標記初始化，表示無列沖突 for(iColumn=0;iColumn<8;iColumn++) Queen[iLine][iColumn]='*'; } //主、從對角線標記初始化，表示沒有沖突 for(iLine=0;iLine<15;iLine++) b[iLine]=c[iLine]=0; qu(0); return 0; } void qu(int i) { int iColumn; for(iColumn=0;iColumn<8;iColumn++) { if(a[iColumn]==0&&b[i-iColumn+7]==0&&c[i+iColumn]==0) //如果無沖突 { Queen[iColumn]='@'; //放皇後 a[iColumn]=1; //標記，下一次該列上不能放皇後 b[i-iColumn+7]=1; //標記，下一次該主對角線上不能放皇後 c[i+iColumn]=1; //標記，下一次該從對角線上不能放皇後 if(i<7) qu(i+1); //如果行還沒有遍歷完，進入下一行 else //否則輸出 { //輸出棋盤狀態 int iLine,iColumn; printf("第%d種狀態為：\n",++iQueenNum); for(iLine=0;iLine<8;iLine++) { for(iColumn=0;iColumn2)this.width=screen.width/2" vspace=2 border=0>; } printf("\n\n"screen.width/2)this.width=screen.width/2" vspace=2 border=0>; } //如果前次的皇後放置導致後面的放置無論如何都不能滿足要求，則回溯，重置 Queen[iColumn]='*'; a[iColumn]=0; b[i-iColumn+7]=0; c[i+iColumn]=0; } } } 八皇後的c語言解法： #include #include #include int n,k,a[20],num=0; int attack(int k){ int flag=0; int i=1; while ((i<k)&&(a[k]!=a)&&(fabs(a[k]-a)!=(k-i))) i++; if (i==k) flag=1; return flag; } void place(int k) { //printf(" %d",k); int i; if (k==n+1){ num=num+1; printf("num=%d:",num); for (i=1;i<n+1;i++) printf(" %d",a); printf("\n");} else { for (i=1;i<n+1;i++){ a[k]=i; if (attack(k)==1) place(k+1); else a[k]=0; } } } main(){ scanf("%d",&n); k=1; place(k); if (k!=n+1) printf("no solution!\n"); getch(); }
㈤ c語言 n皇後 求高手
八皇後問題各種語言版本：
http://ke..com/view/698719.htm
#include<iostream.h>
const int n = 15 ; //15皇後問題.改動n可變成N皇後問題
const int n_sub = n - 1 ;
int queen[n] ; //N個棋子.N對應每一列,如n=0的棋子只下在0列,1下1....類推
bool row[n] ; //棋局的每一行是否有棋,有則為1,無為0 ;
bool passive[2*n-1] ; //斜率為1的斜線方向上是不是有皇後
bool negative[2*n-1] ; //斜率為負1的斜線方向上是不是有皇後.
//之所以用全局變數,因全局數組元素值自動為0
int main()
{
int cur = 0 ;//游標,當前移動的棋子(哪一列的棋子)
bool flag = false ; //當前棋子位置是否合法
queen[0] = -1 ; //第0列棋子准備,因一開始移動的就是第0列棋子
int count = 0 ; //一共有多少種下法 ;
cout<<"============================Starting============================="<<endl ;
while(cur>=0)
{
while(cur>=0 && queen[cur]<n && !flag) //當還不確定當前位置是否可下
{
queen[cur]++ ;
// cout<<"第"<<cur<<"列棋子開始走在第"<<queen[cur]<<"行"<<endl ;
// cin.get() ;
if(queen[cur] >= n) { //如果當前列已經下完(找不到合法位置)
// cout<<"當前行是非法行,當前列棋子走完,沒有合法位置,回溯上一列棋子"<<endl ;
// cin.get() ;
queen[cur] = -1 ; //當前列棋子置於准備狀態
cur-- ; //回溯到上一列的棋子
if(cur>=0) {
row[queen[cur]] = false ;
passive[queen[cur] + cur] = false ;
negative[n_sub + cur - queen[cur]] = false ;
}
//由於要移下一步,所以回溯棋子原位置所在行應該沒有棋子啦.置row[]為false
//並且棋子對應的斜線的標志位passive[cur]和negative[cur]也應該要設為false ;
}
else {
//先判斷棋子所在行沒有棋子
if(row[queen[cur]] == false) { //當前行沒有棋子
// cout<<"棋子"<<cur<<"所在行沒有其他棋子,正在檢查斜線"<<endl ;
flag = true ; // 暫設為true,或與之前棋子斜交,則再設為false ;
//以下檢查當前棋子是否與之前的棋子斜線相交
if( passive[queen[cur] + cur] == true || negative[n_sub + cur - queen[cur]] == true) {
flag = false ;
// cout<<"出現斜線相交,該位置不合法"<<endl ;
}
else
flag = true ;
if(flag) { //沒有斜交,位置合法
// cout<<"斜線也沒有相交,該位置合法"<<endl ;
if(cur == n-1) //如果是最後一個棋子
{
// cout<<"棋子走完一輪,總走法加1"<<endl ;
count++ ; //總走法加一 ;
}
row[queen[cur]] = true ;// 當前行設為有棋子
passive[queen[cur] + cur] = true ;//當前行正斜率方向有棋子
negative[n_sub + cur - queen[cur]] = true ; //當前行負斜率方向上也有棋子
cur++ ;
if(cur >= n) {
cur-- ;
row[queen[cur]] = false ;
passive[queen[cur] + cur] = false ;
negative[n_sub + cur - queen[cur]] = false ;//原理同回溯
}
flag = false ;
}
}
}//else
}
}
cout<<n<<"皇後問題一共有"<<count<<"種解法"<<endl ;
return 0 ;
}
你自己修改一下吧。
㈥ 如何用C語言解決N皇後問題並作出流程圖
#include"iostream"
using namespace std;
const max_board = 13;
class Queen
{
public :
Queen(int size);
bool is_solved() const; //判斷是否已經填滿
void print() const; //列印結果
bool unguarded(int col) const; //判斷是否被鎖定
void insert(int col); //在該位放置皇後
void remove(int col); //移除皇後
// void solve_from(Queen &configuration);
int board_size; //邊界
private :
int count; //已放置皇後的數目
bool queen_square[max_board][max_board]; //棋盤
};
Queen::Queen(int size)
{
if(size<1)
board_size=1;
else
if(size>13)
board_size=13;
else
board_size=size;
count=0;
for(int i=0;i<board_size;i++)
for(int j=0;j<board_size;j++)
{
queen_square[i][j]=false;
}
}
bool Queen::is_solved() const
{
return count==board_size;
}
void Queen::print() const
{
for(int i=0;i<board_size;i++)
{
for(int j=0;j<board_size;j++)
{
cout<<queen_square[i][j]<<' ';
}
cout<<endl;
}
cout<<endl;
}
bool Queen::unguarded(int col) const
{
int i;
bool ok=true;
for(i=0;ok&&i<count;i++)
{
ok=!queen_square[i][col];
}
for(i=1;i<=col&&i<=count&&ok;i++)
{
ok=!queen_square[count-i][col-i];
}
for(i=1;i<board_size-col&&i<=count&&ok;i++)
{
ok=!queen_square[count-i][col+i];
}
return ok;
}
void Queen::insert(int col)
{
queen_square[count++][col]=true;
}
void Queen::remove(int col)
{
queen_square[--count][col]=false;
}
void solve_from(Queen &configuration)
{
if(configuration.is_solved())
configuration.print();
else
for(int col=0;col<configuration.board_size;col++)
if(configuration.unguarded(col))
{
configuration.insert(col);
solve_from(configuration);
configuration.remove(col);
}
}
int main()
{
int n;
cout<<"please input the size:\t";
cin>>n;
Queen queen(n);
solve_from(queen);
return 0;
}
㈦ 求教C語言回溯法寫出八皇後問題的92種解
(1)全排列
將自然數1~n進行排列，共形成n!中排列方式，叫做全排列。
例如3的全排列是：1/2/3、1/3/2、2/1/3、2/3/1、3/1/2、3/2/1，共3!=6種。
(2)8皇後（或者n皇後）
保證8個皇後不能互相攻擊，即保證每一橫行、每一豎行、每一斜行最多一個皇後。
我們撇開第三個條件，如果每一橫行、每一豎行都只有一個皇後。
將8*8棋盤標上坐標。我們討論其中的一種解法：
- - - - - - - Q
- - - Q - - - -
Q - - - - - - -
- - Q - - - - -
- - - - - Q - -
- Q - - - - - -
- - - - - - Q -
- - - - Q - - -
如果用坐標表示就是：(1,8) (2,4) (3,1) (4,3) (5,6) (6,2) (7,7) (8,5)
將橫坐標按次序排列，縱坐標就是8/4/1/3/6/2/7/5。這就是1~8的一個全排列。
我們將1~8的全排列存入輸入a[]中(a[0]~a[7])，然後8個皇後的坐標就是(i+1,a[i])，其中i為0~7。
這樣就能保證任意兩個不會同一行、同一列了。
置於斜行，你知道的，兩個點之間連線的斜率絕對值為1或者-1即為同一斜行，充要條件是|x1-x2|=|y1-y2|（兩個點的坐標為（x1,y1）(x2,y2)）。我們在輸出的時候進行判斷，任意兩個點如果滿足上述等式，則判為失敗，不輸出。
下面附上代碼：添加必要的注釋，其中全排列的實現看看注釋應該可以看懂：
#include<stdio.h>
#include<math.h>
#include<string.h>
#include<stdlib.h>
intprinted;
//該函數用於畫圖，這里為了節約空間則略去
//讀者只需要將draw(a,k);去掉注釋即可畫圖
voiddraw(int*a,intk)
{
inti,j;
for(i=0;i<k;i++)
{
printf(" ");
for(j=0;j<k;j++)
//有皇後輸出Q，否則輸出-
if(a[i]-1==j)printf("Q");elseprintf("-");
printf(" ");
}
printf(" ");
}
//遞歸實現全排列,a是數組，iStep是位置的測試點，k是皇後的個數，一般等於8
voidSettle(int*a,intiStep,intk)
{
inti,j,l,flag=1;
//如果iStep的數字等於a之前的數字，則存在重復，返回
for(i=0;i<iStep-1;i++)
if(a[iStep-1]==a[i])return;
//如果iStep==k，即遞歸結束到最後一位，可以驗證是否斜行滿足
if(iStep==k)
{
//雙重循環判斷是否斜行滿足
for(j=0;j<k;j++)
for(l=0;l<k&&l!=j;l++)
//如果不滿足，則flag=0
if(fabs(j-l)==fabs(a[j]-a[l]))flag=0;
//如果flag==1，則通過了斜行的所有測試，輸出。
if(flag)
{
for(i=0;i<k;i++)
printf("(%d,%d)",i+1,a[i]);
printf(" ");
//如果去掉這里的注釋可以獲得畫圖，由於空間不夠，這里略去
// draw(a,k);
//printed變數計算有多少滿足題意的結果，是全局變數
printed++;
}
flag=1;
}
//如果未測試至最後末尾，則測試下一位（遞歸）
for(i=1;i<=k;i++)
{
a[iStep]=i;
Settle(a,iStep+1,k);
}
}
voidmain()
{
int*a;
intk;
//輸入維數，建立數組
printf("Enterthesizeofthesquare:");
scanf("%d",&k);
a=(int*)calloc(k,sizeof(int));
//清屏，從iStep=0處進入遞歸
system("cls");
Settle(a,0,k);
//判斷最後是否有結果
if(!printed)printf("Noanswersaccepted! ");
elseprintf("%dstatesavailable! ",printed);
}
附輸出結果（輸入k=8）：
(1,1)(2,5)(3,8)(4,6)(5,3)(6,7)(7,2)(8,4)
(1,1)(2,6)(3,8)(4,3)(5,7)(6,4)(7,2)(8,5)
(1,1)(2,7)(3,4)(4,6)(5,8)(6,2)(7,5)(8,3)
(1,1)(2,7)(3,5)(4,8)(5,2)(6,4)(7,6)(8,3)
(1,2)(2,4)(3,6)(4,8)(5,3)(6,1)(7,7)(8,5)
(1,2)(2,5)(3,7)(4,1)(5,3)(6,8)(7,6)(8,4)
(1,2)(2,5)(3,7)(4,4)(5,1)(6,8)(7,6)(8,3)
(1,2)(2,6)(3,1)(4,7)(5,4)(6,8)(7,3)(8,5)
(1,2)(2,6)(3,8)(4,3)(5,1)(6,4)(7,7)(8,5)
(1,2)(2,7)(3,3)(4,6)(5,8)(6,5)(7,1)(8,4)
(1,2)(2,7)(3,5)(4,8)(5,1)(6,4)(7,6)(8,3)
(1,2)(2,8)(3,6)(4,1)(5,3)(6,5)(7,7)(8,4)
(1,3)(2,1)(3,7)(4,5)(5,8)(6,2)(7,4)(8,6)
(1,3)(2,5)(3,2)(4,8)(5,1)(6,7)(7,4)(8,6)
(1,3)(2,5)(3,2)(4,8)(5,6)(6,4)(7,7)(8,1)
(1,3)(2,5)(3,7)(4,1)(5,4)(6,2)(7,8)(8,6)
(1,3)(2,5)(3,8)(4,4)(5,1)(6,7)(7,2)(8,6)
(1,3)(2,6)(3,2)(4,5)(5,8)(6,1)(7,7)(8,4)
(1,3)(2,6)(3,2)(4,7)(5,1)(6,4)(7,8)(8,5)
(1,3)(2,6)(3,2)(4,7)(5,5)(6,1)(7,8)(8,4)
(1,3)(2,6)(3,4)(4,1)(5,8)(6,5)(7,7)(8,2)
(1,3)(2,6)(3,4)(4,2)(5,8)(6,5)(7,7)(8,1)
(1,3)(2,6)(3,8)(4,1)(5,4)(6,7)(7,5)(8,2)
(1,3)(2,6)(3,8)(4,1)(5,5)(6,7)(7,2)(8,4)
(1,3)(2,6)(3,8)(4,2)(5,4)(6,1)(7,7)(8,5)
(1,3)(2,7)(3,2)(4,8)(5,5)(6,1)(7,4)(8,6)
(1,3)(2,7)(3,2)(4,8)(5,6)(6,4)(7,1)(8,5)
(1,3)(2,8)(3,4)(4,7)(5,1)(6,6)(7,2)(8,5)
(1,4)(2,1)(3,5)(4,8)(5,2)(6,7)(7,3)(8,6)
(1,4)(2,1)(3,5)(4,8)(5,6)(6,3)(7,7)(8,2)
(1,4)(2,2)(3,5)(4,8)(5,6)(6,1)(7,3)(8,7)
(1,4)(2,2)(3,7)(4,3)(5,6)(6,8)(7,1)(8,5)
(1,4)(2,2)(3,7)(4,3)(5,6)(6,8)(7,5)(8,1)
(1,4)(2,2)(3,7)(4,5)(5,1)(6,8)(7,6)(8,3)
(1,4)(2,2)(3,8)(4,5)(5,7)(6,1)(7,3)(8,6)
(1,4)(2,2)(3,8)(4,6)(5,1)(6,3)(7,5)(8,7)
(1,4)(2,6)(3,1)(4,5)(5,2)(6,8)(7,3)(8,7)
(1,4)(2,6)(3,8)(4,2)(5,7)(6,1)(7,3)(8,5)
(1,4)(2,6)(3,8)(4,3)(5,1)(6,7)(7,5)(8,2)
(1,4)(2,7)(3,1)(4,8)(5,5)(6,2)(7,6)(8,3)
(1,4)(2,7)(3,3)(4,8)(5,2)(6,5)(7,1)(8,6)
(1,4)(2,7)(3,5)(4,2)(5,6)(6,1)(7,3)(8,8)
(1,4)(2,7)(3,5)(4,3)(5,1)(6,6)(7,8)(8,2)
(1,4)(2,8)(3,1)(4,3)(5,6)(6,2)(7,7)(8,5)
(1,4)(2,8)(3,1)(4,5)(5,7)(6,2)(7,6)(8,3)
(1,4)(2,8)(3,5)(4,3)(5,1)(6,7)(7,2)(8,6)
(1,5)(2,1)(3,4)(4,6)(5,8)(6,2)(7,7)(8,3)
(1,5)(2,1)(3,8)(4,4)(5,2)(6,7)(7,3)(8,6)
(1,5)(2,1)(3,8)(4,6)(5,3)(6,7)(7,2)(8,4)
(1,5)(2,2)(3,4)(4,6)(5,8)(6,3)(7,1)(8,7)
(1,5)(2,2)(3,4)(4,7)(5,3)(6,8)(7,6)(8,1)
(1,5)(2,2)(3,6)(4,1)(5,7)(6,4)(7,8)(8,3)
(1,5)(2,2)(3,8)(4,1)(5,4)(6,7)(7,3)(8,6)
(1,5)(2,3)(3,1)(4,6)(5,8)(6,2)(7,4)(8,7)
(1,5)(2,3)(3,1)(4,7)(5,2)(6,8)(7,6)(8,4)
(1,5)(2,3)(3,8)(4,4)(5,7)(6,1)(7,6)(8,2)
(1,5)(2,7)(3,1)(4,3)(5,8)(6,6)(7,4)(8,2)
(1,5)(2,7)(3,1)(4,4)(5,2)(6,8)(7,6)(8,3)
(1,5)(2,7)(3,2)(4,4)(5,8)(6,1)(7,3)(8,6)
(1,5)(2,7)(3,2)(4,6)(5,3)(6,1)(7,4)(8,8)
(1,5)(2,7)(3,2)(4,6)(5,3)(6,1)(7,8)(8,4)
(1,5)(2,7)(3,4)(4,1)(5,3)(6,8)(7,6)(8,2)
(1,5)(2,8)(3,4)(4,1)(5,3)(6,6)(7,2)(8,7)
(1,5)(2,8)(3,4)(4,1)(5,7)(6,2)(7,6)(8,3)
(1,6)(2,1)(3,5)(4,2)(5,8)(6,3)(7,7)(8,4)
(1,6)(2,2)(3,7)(4,1)(5,3)(6,5)(7,8)(8,4)
(1,6)(2,2)(3,7)(4,1)(5,4)(6,8)(7,5)(8,3)
(1,6)(2,3)(3,1)(4,7)(5,5)(6,8)(7,2)(8,4)
(1,6)(2,3)(3,1)(4,8)(5,4)(6,2)(7,7)(8,5)
(1,6)(2,3)(3,1)(4,8)(5,5)(6,2)(7,4)(8,7)
(1,6)(2,3)(3,5)(4,7)(5,1)(6,4)(7,2)(8,8)
(1,6)(2,3)(3,5)(4,8)(5,1)(6,4)(7,2)(8,7)
(1,6)(2,3)(3,7)(4,2)(5,4)(6,8)(7,1)(8,5)
(1,6)(2,3)(3,7)(4,2)(5,8)(6,5)(7,1)(8,4)
(1,6)(2,3)(3,7)(4,4)(5,1)(6,8)(7,2)(8,5)
(1,6)(2,4)(3,1)(4,5)(5,8)(6,2)(7,7)(8,3)
(1,6)(2,4)(3,2)(4,8)(5,5)(6,7)(7,1)(8,3)
(1,6)(2,4)(3,7)(4,1)(5,3)(6,5)(7,2)(8,8)
(1,6)(2,4)(3,7)(4,1)(5,8)(6,2)(7,5)(8,3)
(1,6)(2,8)(3,2)(4,4)(5,1)(6,7)(7,5)(8,3)
(1,7)(2,1)(3,3)(4,8)(5,6)(6,4)(7,2)(8,5)
(1,7)(2,2)(3,4)(4,1)(5,8)(6,5)(7,3)(8,6)
(1,7)(2,2)(3,6)(4,3)(5,1)(6,4)(7,8)(8,5)
(1,7)(2,3)(3,1)(4,6)(5,8)(6,5)(7,2)(8,4)
(1,7)(2,3)(3,8)(4,2)(5,5)(6,1)(7,6)(8,4)
(1,7)(2,4)(3,2)(4,5)(5,8)(6,1)(7,3)(8,6)
(1,7)(2,4)(3,2)(4,8)(5,6)(6,1)(7,3)(8,5)
(1,7)(2,5)(3,3)(4,1)(5,6)(6,8)(7,2)(8,4)
(1,8)(2,2)(3,4)(4,1)(5,7)(6,5)(7,3)(8,6)
(1,8)(2,2)(3,5)(4,3)(5,1)(6,7)(7,4)(8,6)
(1,8)(2,3)(3,1)(4,6)(5,2)(6,5)(7,7)(8,4)
(1,8)(2,4)(3,1)(4,3)(5,6)(6,2)(7,7)(8,5)
92statesavailable!
㈧ c語言題目求一詳細的解答
回溯法求解~創建幾個數組：a[x][y]表示在第x列的第y行上置一皇後；b[]，c[]，d[]分別記錄各行和兩條斜線上是否有皇後，用0和1標記。從第一列開始置皇後，每次置完以後檢驗，作擴展或回溯調整，並同時更新b，c，d。直至得出n個皇後的全部為止結束。
程序比較長。。。我網上找了一個回溯法的程序：
這是一個古老的具有代表性的問題，用計算機求解時的演算法也很多，這里僅介紹一種。
採用一維數組來進行處理。數組的下標i表示棋盤上的第i列，a[i]的值表示皇後在第i列所放的位置。如：a[1]=5，表示在棋盤的第一例的第五行放一個皇後。
程序中首先假定a[1]=1，表示第一個皇後放在棋盤的第一列的第一行的位置上，然後試探第二列中皇後可能的位置，找到合適的位置後，再處理後續的各列，這樣通過各列的反復試探，可以最終找出皇後的全部擺放方法。
程序採用回溯法，演算法的細節參看程序。
#include<stdio.h>
#defineNUM8/*定義數組的大小*/
inta[NUM
1];
intmain()
{
inti,k,flag,not_finish=1,count=0;
i=1;/*正在處理的元素下標，表示前i-1個元素已符合要求，正在處理第i個元素*/
a[1]=1;/*為數組的第一個元素賦初值*/
printf(":\n");
while(not_finish)/*not_finish=1:處理尚未結束*/
{
while(not_finish
㈨ n皇後問題 c++
回溯法程序：
#include<iostream.h>
#include<string.h>
#include<time.h>
#define size 100
int board[size];
int ver[size];
int ru[size*2];//右上
int rd[size*2];//右下
int n,find; int rec[size];
//回溯搜索
void dfs(int t)
{
int i;
if(find) return;
if(t==n)
{
find=1;
for(i=0;i<n;i++)
{
rec[i]=board[i];
}
return;
}
for(i=0;i<n;i++)
{
if(ver[i]==1) continue;
if(ru[i-t+n]==1) continue;
if(rd[i+t]==1) continue;
ver[i]=1;
ru[i-t+n]=1;
rd[i+t]=1;
board[t]=i;
dfs(t+1);
rd[i+t]=0;
ru[i-t+n]=0;
ver[i]=0;
}
return;
}
int main()
{
int i,j,t1,t2;
cout<<"輸入棋盤大小：";
cin>>n;
t1=clock();
find=0; memset(ver,0,sizeof(ver));
memset(ru,0,sizeof(ru)); memset(rd,0,sizeof(rd));
dfs(0);
t2=clock();
if(find)
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
if(rec[i]==j) cout<<'X';
else cout<<'+';
}
cout<<endl;
}
else
cout<<"Can't find!n";
cout<<"耗費時間："<<t2-t1<<"msn";
return 0;
}
既然是回溯法，樓主可以看看回溯法
---------2 回溯法：如果在第i行無論如何放置皇後，都和前面i-1行的皇後互相攻擊的話，說明i-1行的皇後位置不合理，於是就回退一行，重新計算。這類似於走迷宮，如果在某個路口實在不下去了，只好退後一步重新選擇。在退後一步重新選擇的時候，顯然可以排除已經嘗過的路線。
下面重點分析回溯法解決N皇後問題。
很容易想到，在同一行上只能放置一個皇後，因此nxn的棋盤上放n個皇後的方案必然是每一行上放一個皇後。這樣的話，我們可以使用一個一維數組q[n]來保存最後的方案，其中q[i]的含義是第i行上皇後的位置。比如q[3]=5，則表示第三行上的皇後在第5格。
上面無論哪種方法，都要解決一個問題：如何量化的判斷兩個皇後是否相互攻擊？有了數組q的定義，我們很容易發現如下的規律：
對於兩個皇後q[i]和q[j]，互相不攻擊的條件是：
1 i != j，即不在同一行。
2 q[i] != q[j]，即不再同一列。
3 |q[i] - q[j]| != |i - j|，即不在一個對角線上。
根據前面的分析，我們假設前面的i-1行的皇後已經布好，即互不攻擊，則在第i行上的皇後位置為q[i]，那麼我們可以把q[i]依次和前面的i-1行比較，如果q[i]和前面的i-1行互不攻擊的話，則說明第i行的皇後q[i]就是一個合理的位置，則繼續尋找i+1行的皇後合理位置。如果第i行的皇後和前面的i-1行的某個皇後有攻擊，則第i行的皇後需要右移一格，重新和前面的i-1行進行比較。
在進行具體處理時，要注意邊界條件，即回退到棋盤第一行以及皇後已經右移到棋盤的最後一行的最後一格的情況，都意味著當前皇後位置使得N皇後問題無解。
下面是演算法：
PROCEDURE QUEEN(n)
FOR i = 1 TO n DO q[i] = 1
i = 1
loop:
IF(q[i] <= n) THEN
{
k = 1
WHILE((k < i) and ((q[k] - q[i])) * (|q[k] - q[i]| - |k - i| ) != 0)
DO k = k + 1
IF(k < i) THEN q[i] = q[i] + 1
ELSE
{
i = i + 1
IF(i > n) THEN
{
OUTPUT q[i] (i = 1,2,...,n)
q[n] = q[n] + 1
i = n
}
}
}
ELSE
{
q[i] = 1
i = i - 1
IF(i < 1) THEN RETURN
q[i] = q[i] + 1
}
TOGO loop
RETURN
㈩ 利用《數據結構》課程知識完成C語言程序設計「N皇後問題」（堆棧，一維數組，普通演算法都可以，用C語言寫
#include<stdio.h>//N皇後問題
#include<
stdlib.h
>
#include<stdio.h>
#include<
iostream.h
>
#include<
time.h
>
#include<dos.h>
#include<malloc.h>
typedefstruct{
int*elem;
intlength;
intlistsize;
}Sqlist;
intInitList(Sqlist&L){//初始化
L.elem=(int*)malloc(100*sizeof(int));
if(!L.elem)
return0;
L.length=0;
L.listsize=100;
return1;
}
intInsert(Sqlist&L,inte){//插入
intm=0,i=0;
int*p=&L.elem[0],*j=&L.elem[0];
if(L.length==0)
{*p=e;L.length++;return1;}
for(i;i<L.length;i++)
if(e>=*(p+i))
m=i+1;
for(i=L.length;i>m;i--)
*(j+i)=*(j+i-1);
L.elem[m]=e;
L.length++;
return1;
}
voidPrint(Sqlist&L,intn){//
遍歷
列印輸出
intk=1,i=0;int*p=&L.elem[0];
for(i=0;i<n*n;i++,k++){
printf("%d",*(p+i));
if(k==n){k=0;printf(" ");}}
printf(" ");
}
intReturnK(Sqlist&L,intk){//返回第K個元素的值
int*p=&L.elem[0];
return*(p+k-1);
}
voidFuK(Sqlist&L,intk,inte){//將第k個元素賦值為e
int*p=&L.elem[0];
*(p+k-1)=e;
}
intTiaoJian(SqlistL,intn,int&e){//是否滿足皇後問題判斷
intb[100];
intm=0,h=2*n;
for(intk=0;k<2*n;k++)b[k]=0;
for(inti=1;i<=n*n;i++)
if(ReturnK(L,i)==1)
{b[m]=(i-1)/n+1;m++;b[m]=i-(b[m-1]-1)*n;m++;}
for(intc=0;c<2*n;c++)
if(b[c]==0){h=c;break;}
for(c=0;c<h-2;c=c+2)
for(intd=c+2;d<h;d=d+2)
if(b[c]==b[d]||b[c+1]==b[d+1]||b[d+1]-b[c+1]==b[d]-b[c]||b[d+1]-b[c+1]==b[c]-b[d])
return0;
if(h==2*n){
printf(" %d皇後問題第%d個排列！ ",n,e);e++;
}
return1;
}
voidTrial(Sqlist&L,inti,intn,int&e){//皇後問題
intj;
if(i>n){Print(L,n);}
elsefor(j=1;j<=n;j++){
FuK(L,n*i-n+j,1);
if(TiaoJian(L,n,e)==1)
Trial(L,i+1,n,e);
FuK(L,n*i-n+j,0);
}
}
voidmain(){
intk,i=0;
printf(" 請輸入要n皇後問題個數： ");
scanf("%d",&k);
time_trawtime;
structtm
*timeinfo;
time(&rawtime);
timeinfo=localtime(&rawtime);
SqlistL1;
InitList(L1);
for(i=0;i<k*k;i++)
Insert(L1,0);
inte=1;
Trial(L1,1,k,e);
printf("Thecurrentdate/timeis:%s",asctime(timeinfo));
time(&rawtime);
timeinfo=localtime(&rawtime);
printf("Thecurrentdate/timeis:%s",asctime(timeinfo));
printf("哈哈哈哈(^o^)/~ ");
system("pause");
}