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