皇後控制問題演算法

『壹』 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

『貳』 數據結構課程設計：八皇後問題求出在一個n×n的棋盤上，放置n個不能互相捕捉的國際象棋「皇後」的所有布局

#include <iostream>
using namespace std;
#define MAX 8 //數組維數
static int total=0; //演算法總數
int array[MAX][MAX]; //定義數組
void SetArray() //數組置零
{
int i,j;
for(i=0;i<MAX;i++)
for(j=0;j<MAX;j++)
array[i][j]=0;
}
bool IsTrue(int a,int b) //合法性判斷
{
int i,j,len;
for (i=0;i<MAX;i++)
if(array[a][i]==1||array[i][b]==1)
return false;
len=(a<b?a:b);
for(i=a-len,j=b-len;i<MAX&&j<MAX;i++,j++)
if(array[i][j]==1)
return false;
for(i=a,j=b;i<MAX&&j>=0;i++,j--)
if(array[i][j]==1)
return false;
for(i=a,j=b;i>=0&&j<MAX;i--,j++)
if(array[i][j]==1)
return false;
return true;
}
void show() //顯示結果
{
int i,j;
cout<<"第"<<++total<<"種結果為："<<endl;
for (i=0;i<MAX;i++)
{
for(j=0;j<MAX;j++)
cout<<array[i][j]<<" ";
cout<<endl;
}

}
bool Queen(int i) //皇後演算法
{
int j;
for(j=0;j<MAX;j++)
{
if(IsTrue(i,j))
{
array[i][j]=1;
if(i==MAX-1)
{
show();
array[i][j]=0;
continue;
}
else if(!Queen(i+1))
{
array[i][j]=0;
continue;
}
}
}
return false;
}
void main()
{
int i;
for(i=0;i<MAX;i++)
{
SetArray();
array[0][i]=1;
Queen(1);
}
}
程序給你了，按你的思路寫的，比較簡單，剛運行了一下，八皇後問題有92種演算法，跟上面說的一樣。具體是什麼樣的，自己去運行，說明，這是用c++寫的，有問題可以去www.pptkj.net 上面留言。。或者追問。

『叄』 C語言五皇後控制棋盤問題

#include <iostream>
#include <cstdlib>
using namespace std ;
int iCount = 0 ;
void pintf(int qp[8][8] )
{
for ( int i = 0 ; i < 8 ; i ++)
{
for ( int j = 0 ; j < 8 ; j++)
{ if ( qp[i][j] > 6 )
cout<< " 皇 " ;
else
cout<< " ＊ " ;
// cout<< " " << qp[i][j] ;
}
cout << endl ;
}
cout << endl ;
cout << endl ;
}
void fz( int qp[8][8] , int wz[5][2] , int iIndex , int ii , int jj)
{
if ( iIndex == 5 )
{ for ( int i = 0 ; i < 8 ; i ++)
{
for ( int j = 0 ; j < 8 ; j++)
{
if ( qp[i][j] == 0 )
return ;
}
} iCount ++ ;
cout<< "方式 " << iCount << endl ;
pintf(qp); return ;
} for ( int i = ii ; i < 8 ; i++)
{
for ( int j = jj ; j < 8 ; j++)
{
if ( qp[i][j] == 0 )
{
for ( int m = 0 ; m < 8 ; m++) //設置
{
for ( int n = 0 ; n < 8 ; n++)
{
if ( m == i || n == j ) //同行或同列
qp[m][n] += 1 ;
else if ( m-n == i-j || n+m == i+j ) //對角線
{
qp[m][n] += 1 ;
}
}
} qp[i][j] += 6 ;
wz[iIndex ][ 0 ] = i;
wz[iIndex ][ 1 ] = j;
//cout<< i << " " << j << " " << iIndex << endl ;
fz( qp , wz, iIndex+1 , i , 0 ) ;
//還原
qp[i][j] -= 6 ;
for ( int m = 0 ; m < 8 ; m++) //設置
{
for ( int n = 0 ; n < 8 ; n++)
{
if ( m == i || n == j ) //同行或同列
{
qp[m][n] -= 1 ;
}
else if ( m-n == i-j || n+m == i+j ) //對角線
{
qp[m][n] -= 1 ;
}
}
}
}
}
}
}main()
{
int qp[8][8] , wz[5][2] ;
//init
for ( int i = 0 ; i < 8 ; i++)
{
for ( int j = 0 ; j < 8 ; j++)
{
qp[i][j] = 0 ;
}
}
iCount = 0 ;
fz( qp , wz , 0 , 0 , 0 ) ;
cout<< "共計方式 " << iCount << endl ;}

『肆』 八皇後究竟有多少種解法怎麼解

這樣算是最佳解 class Queen8{ static final int QueenMax = 8; static int oktimes = 0; static int chess[] = new int[QueenMax]; public static void main(String args[]){ for (int i=0;i<QueenMax;i++)chess[i]=-1; placequeen(0); System.out.println("\n\n\n八皇後共有"+oktimes+"個解法 made by yifi 2003"); } public static void placequeen(int num) { int i=0; boolean qsave[] = new boolean[QueenMax]; for(;i<QueenMax;i++) qsave[i]=true; i=0; while (i<num){ qsave[chess[i]]=false; int k=num-i; if ( (chess[i]+k >= 0) && (chess[i]+k < QueenMax) ) qsave[chess[i]+k]=false; if ( (chess[i]-k >= 0) && (chess[i]-k < QueenMax) ) qsave[chess[i]-k]=false; i++; } for(i=0;i<QueenMax;i++){ if (qsave[i]==false)continue; if (num<QueenMax-1){ chess[num]=i; placequeen(num+1); } else{ //num is last one chess[num]=i; oktimes++; System.out.println("這是第"+oktimes+"個解法 如下:"); System.out.println("第n行: 1 2 3 4 5 6 7 8"); for (i=0;i<QueenMax;i++){ String row="第"+(i+1)+"行: "; if (chess[i]==0); else for(int j=0;j<chess[i];j++) row+="--"; row+="++"; int j = chess[i]; while(j<QueenMax-1){row+="--";j++;} System.out.println(row); } } } } } 多少種解法就不好說了..

『伍』 皇後沖突問題

#include <stdio.h>
#include<string.h>
const int MAX=10;
char s[MAX][MAX];
bool r[MAX],c[MAX],left[MAX*2],right[MAX*2];
int main()
{
int n=8,m=8,i,j;
while(scanf("%s",s[0])!=EOF)
{
for(i=1;i<n;i++)
{
scanf("%s",s[i]);
}
memset(r,false,sizeof(r));
memset(c,false,sizeof(c));
memset(left,false,sizeof(left));
memset(right,false,sizeof(right));
bool flag=true;
for(i=0;i<n&&flag;i++)
{
for(j=0;j<n&&flag;j++)
{
if(s[i][j]=='Q')
{
if(r[i])flag=false;
if(c[j])flag=false;
if(left[i+j])flag=false;
if(right[i-j+MAX])flag=false;
r[i]=true;
c[j]=true;
left[i+j]=true;
right[i-j+MAX]=true;
}
}
}
if(flag)puts("NO");
else puts("YES");
}
return 0;
}

/*
Q**Q**** *Q****** ****Q*** **Q***** Q******* ******** ******** ********
*/

『陸』 國際象棋5皇後問題

如圖所示：

所以最後應該是有兩種.有問題請指教

『柒』 誰有八皇後問題的編程過程

這就是著名的八皇後問題。八個皇後在排列時不能同在一行、一列或一條斜
線上。在8!=40320種排列中共有92種解決方案。

「八皇後」動態圖形的實現

八皇後問題是一個古老而著名的問題，是回溯演算法的典型例題。該問題是十九世紀著名的數學家高斯1850年提出：在8X8格的國際象棋上擺放八個皇後，使其不能互相攻擊，即任意兩個皇後都不能處於同一行、同一列或同一斜線上，問有多少種擺法。
高斯認為有76種方案。1854年在柏林的象棋雜志上不同的作者發表了40種不同的解，後來有人用圖論的方法解出92種結果。
對於八皇後問題的實現，如果結合動態的圖形演示，則可以使演算法的描述更形象、更生動，使教學能產生良好的效果。下面是筆者用Turbo C實現的八皇後問題的圖形程序，能夠演示全部的92組解。八皇後問題動態圖形的實現，主要應解決以下兩個問題。

1．回溯演算法的實現
（1）為解決這個問題，我們把棋盤的橫坐標定為i，縱坐標定為j,i和j的取值范圍是從1到8。當某個皇後佔了位置(i,j)時，在這個位置的垂直方向、水平方向和斜線方向都不能再放其它皇後了。用語句實現，可定義如下三個整型數組：a[8],b[15],c[24]。其中：

a[j-1]=1 第j列上無皇後
a[j-1]=0 第j列上有皇後
b[i+j-2]=1 (i,j)的對角線（左上至右下）無皇後
b[i+j-2]=0 (i,j)的對角線（左上至右下）有皇後
c[i-j+7]=1 (i,j)的對角線（右上至左下）無皇後
c[i-j+7]=0 (i,j)的對角線（右上至左下）有皇後

（2）為第i個皇後選擇位置的演算法如下：

for(j=1;j<=8;j++) /*第i個皇後在第j行*/
if ((i,j)位置為空)） /*即相應的三個數組的對應元素值為1*/
{佔用位置（i,j） /*置相應的三個數組對應的元素值為0*/
if i<8
為i+1個皇後選擇合適的位置；
else 輸出一個解
}

2．圖形存取
在Turbo C語言中，圖形的存取可用如下標准函數實現：

size=imagesize(x1,y1,x2,y2) ;返回存儲區域所需位元組數。
arrow=malloc(size);建立指定大小的動態區域點陣圖，並設定一指針arrow。
getimage(x1,y1,x2,y2,arrow);將指定區域點陣圖存於一緩沖區。
putimage(x,y,arrow,)將點陣圖置於屏幕上以（x，y）左上角的區域。

3． 程序清單如下

＃i nclude <graphics.h>
＃i nclude <stdlib.h>
＃i nclude <stdio.h>
＃i nclude <dos.h>
char n[3]={0,0};/*用於記錄第幾組解*/
int a[8],b[15],c[24],i;
int h[8]={127,177,227,277,327,377,427,477};/*每個皇後的行坐標*/
int l[8]={252,217,182,147,112,77,42,7};/*每個皇後的列坐標*/
void *arrow;
void try(int i)
{int j;
for (j=1;j<=8;j++)
if (a[j-1]+b[i+j-2]+c[i-j+7]==3) /*如果第i列第j行為空*/
{a[j-1]=0;b[i+j-2]=0;c[i-j+7]=0;/*佔用第i列第j行*/
putimage(h[i-1],l[j-1],arrow,COPY_PUT);/*顯示皇後圖形*/
delay(500);/*延時*/
if(i<8) try(i+1);
else /*輸出一組解*/
{n[1]++;if (n[1]>9) {n[0]++;n[1]=0;}
bar(260,300,390,340);/*顯示第n組解*/
outtextxy(275,300,n);
delay(3000);
}
a[j-1]=1;b[i+j-2]=1;c[i-j+7]=1;
putimage(h[i-1],l[j-1],arrow,XOR_PUT);/*消去皇後，繼續尋找下一組解*/
delay(500);
}
}
int main(void)
{int gdrive=DETECT,gmode,errorcode;
unsigned int size;
initgraph(&gdrive,&gmode,"");
errorcode=graphresult();
if (errorcode!=grOk)
{printf("Graphics error\n");exit(1);}
rectangle(50,5,100,40);
rectangle(60,25,90,33);
/*畫皇冠*/
line(60,28,90,28);line(60,25,55,15);
line(55,15,68,25);line(68,25,68,10);
line(68,10,75,25);line(75,25,82,10);
line(82,10,82,25);line(82,25,95,15);
line(95,15,90,25);
size=imagesize(52,7,98,38); arrow=malloc(size);
getimage(52,7,98,38,arrow);/*把皇冠保存到緩沖區*/
clearviewport();
settextstyle(TRIPLEX_FONT, HORIZ_DIR, 4);
setusercharsize(3, 1, 1, 1);
setfillstyle(1,4);
for (i=0;i<=7;i++) a[i]=1;
for (i=0;i<=14;i++) b[i]=1;
for (i=0;i<=23;i++) c[i]=1;
for (i=0;i<=8;i++) line(125,i*35+5,525,i*35+5);/*畫棋盤*/
for (i=0;i<=8;i++) line(125+i*50,5,125+i*50,285);
try(1);/*調用遞歸函數*/
delay(3000);
closegraph();
free(arrow);
}

八皇後問題的串列演算法

1 八皇後問題

所謂八皇後問題,是在8*8格的棋盤上,放置8個皇後。要求每行每列放一個皇後,而且每一條對角線和每一條反對角線上不能有多於1個皇後,也即對同時放置在棋盤的兩個皇後(row1,column1)和(row2,column2),不允許(column1-column2)=(row1-row2)或者(column1+row1)=(column2+row2)的情況出現。

2 八皇後問題的串列遞歸演算法

八皇後問題最簡單的串列解法為如下的遞歸演算法:

(2.1)深度遞歸函數:

go(int step,int column)

{int i,j,place;

row[step]=column;

if (step==8)

outputresult( ); /*結束遞歸列印結果*/

else /*繼續遞歸*/

{for(place=1;place<=8;place++)

{for(j=1;j<=step;j++)

if(collision(j ,row[j],step+1,place))

/*判斷是否有列沖突、對角線或反對角線*/

goto skip_this_place;

go(step+1,place);

skip_this_place:;

}

}

}/* go */

(2.2)主函數:

void main( )

{int place,j;

for(place=1;place<=8;place++)

go(1,place);

}/* main */

八皇後問題的並行演算法

該演算法是將八皇後所有可能的解放在相應的棋盤上,主進程負責生成初始化的棋盤，並將該棋盤發送到某個空閑的子進程,由該子進程求出該棋盤上滿足初始化條件的所有的解。這里，我們假定主進程只初始化棋盤的前兩列，即在棋盤的前兩列分別放上2個皇後,這樣就可以產生8*8=64個棋盤。

1 主進程演算法

主進程等待所有的子進程,每當一個子進程空閑的時侯，就向主進程發送一個Ready(就緒)信號。主進程收到子進程的Ready信號後,就向該子進程發送一個棋盤。當主進程生成了所有的棋盤後,等待所有的子進程完成它們的工作。然後向每個子進程發送一個Finished信號,列印出各個子進程找到的解的總和，並退出。子進程接收到Finished信號也退出。

2 子進程演算法

每個子進程在收到主進程發送過來的棋盤後,對該棋盤進行檢查。若不合法,則放棄該棋盤。子進程回到空閑狀態,然後向主進程發送Ready信號,申請新的棋盤;若合法,則調用move_to_right(board,rowi,colj)尋找在該棋盤上剩下的6個皇後可以擺放的所有位置,move_to_right(board,rowi,colj)是個遞歸過程, 驗證是否能在colj列rowi行以後的位置是否能放一個皇後。

1)首先將more_queen設置成FALSE；

以LEAF,TRUE和FLASE區分以下三種情況:

A)LEAF:成功放置但是已到邊緣,colj現在已經比列的最大值大1,回退兩列,檢查是否能將待檢查皇後放在哪一行:如果能,把more_queen設成TRUE;

B)TRUE:成功放置皇後,檢查這一列是否能有放置皇後的其他方式,如有,把more_queen設成TRUE;

C)FALSE:不能放置,回退一列再試,如果能把more_queen設成TRUE ,如果皇後已在最後一行,必須再檢查上一列。

2)如果more_queens=TRUE,仍需再次調用move_to_right(),為新棋盤分配空間,用xfer()將現有棋盤拷貝到nextboard，並進行下列情況的處理：

TRUE:得到一個皇後的位置,增大列數再試；

FALSE:失敗,如果more_queen為真, 取回棋盤,保存上次調用的棋盤。將列數減小,取走皇後,增加行數,再調用move_to_right()；

LEAF:得到一種解法,solution增一,將解法寫入log_file,由於已到邊緣,列數回退1,檢查是否放置一個皇後,如果能,新加一個皇後後,調用move_to_right；如果不能,檢查more_queen如果more_queen為真,將棋盤恢復到上次調用時保存的棋盤,將待檢查的皇後下移,調用move_to_right。

八皇後問題的高效解法-遞歸版

// Yifi 2003 have fun! : )

//8 Queen 遞歸演算法
//如果有一個Q 為 chess[i]=j;
//則不安全的地方是 k行 j位置,j+k-i位置,j-k+i位置

class Queen8{

static final int QueenMax = 8;
static int oktimes = 0;
static int chess[] = new int[QueenMax];//每一個Queen的放置位置

public static void main(String args[]){
for (int i=0;i<QueenMax;i++)chess[i]=-1;
placequeen(0);
System.out.println("\n\n\n八皇後共有"+oktimes+"個解法 made by yifi 2003");
}

public static void placequeen(int num){ //num 為現在要放置的行數
int i=0;
boolean qsave[] = new boolean[QueenMax];
for(;i<QueenMax;i++) qsave[i]=true;

//下面先把安全位數組完成
i=0;//i 是現在要檢查的數組值
while (i<num){
qsave[chess[i]]=false;
int k=num-i;
if ( (chess[i]+k >= 0) && (chess[i]+k < QueenMax) ) qsave[chess[i]+k]=false;
if ( (chess[i]-k >= 0) && (chess[i]-k < QueenMax) ) qsave[chess[i]-k]=false;
i++;
}
//下面歷遍安全位
for(i=0;i<QueenMax;i++){
if (qsave[i]==false)continue;
if (num<QueenMax-1){
chess[num]=i;
placequeen(num+1);
}
else{ //num is last one
chess[num]=i;
oktimes++;
System.out.println("這是第"+oktimes+"個解法 如下:");
System.out.println("第n行: 1 2 3 4 5 6 7 8");

for (i=0;i<QueenMax;i++){
String row="第"+(i+1)+"行: ";
if (chess[i]==0);
else
for(int j=0;j<chess[i];j++) row+="--";
row+="++";
int j = chess[i];
while(j<QueenMax-1){row+="--";j++;}
System.out.println(row);
}
}
}
//歷遍完成就停止

#include <graphics.h>
#include <stdlib.h>
#include <stdio.h>
#include <dos.h>
char n[3]={\'0\',\'0\'};/*用於記錄第幾組解*/
int a[8],b[15],c[24],i;
int h[8]={127,177,227,277,327,377,427,477};/*每個皇後的行坐標*/
int l[8]={252,217,182,147,112,77,42,7};/*每個皇後的列坐標*/
void *arrow;
void try(int i)
{int j;
for (j=1;j<=8;j++)
if (a[j-1]+b[i+j-2]+c[i-j+7]==3) /*如果第i列第j行為空*/
{a[j-1]=0;b[i+j-2]=0;c[i-j+7]=0;/*佔用第i列第j行*/
putimage(h[i-1],l[j-1],arrow,COPY_PUT);/*顯示皇後圖形*/
delay(500);/*延時*/
if(i<8) try(i+1);
else /*輸出一組解*/
{n[1]++;if (n[1]>\'9\') {n[0]++;n[1]=\'0\';}
bar(260,300,390,340);/*顯示第n組解*/
outtextxy(275,300,n);
delay(3000);
getch();
}
a[j-1]=1;b[i+j-2]=1;c[i-j+7]=1;
putimage(h[i-1],l[j-1],arrow,XOR_PUT);/*消去皇後，繼續尋找下一組解*/
delay(500);
}
}
int main(void)
{int gdrive=DETECT,gmode,errorcode;
unsigned int size;
initgraph(&gdrive,&gmode,"c:\\\\tc\\\\bgi");
errorcode=graphresult();
if (errorcode!=grOk)
{printf("Graphics error\\n");exit(1);}
rectangle(50,5,100,40);
rectangle(60,25,90,33);
/*畫皇冠*/
line(60,28,90,28);line(60,25,55,15);
line(55,15,68,25);line(68,25,68,10);
line(68,10,75,25);line(75,25,82,10);
line(82,10,82,25);line(82,25,95,15);
line(95,15,90,25);
size=imagesize(52,7,98,38); arrow=malloc(size);
getimage(52,7,98,38,arrow);/*把皇冠保存到緩沖區*/
clearviewport();
settextstyle(TRIPLEX_FONT, HORIZ_DIR, 4);
setusercharsize(3, 1, 1, 1);
setfillstyle(1,4);
for (i=0;i<=7;i++) a[i]=1;
for (i=0;i<=14;i++) b[i]=1;
for (i=0;i<=23;i++) c[i]=1;
for (i=0;i<=8;i++) line(125,i*35+5,525,i*35+5);/*畫棋盤*/
for (i=0;i<=8;i++) line(125+i*50,5,125+i*50,285);
try(1);/*調用遞歸函數*/
delay(3000);

closegraph();
free(arrow);
}

『捌』 用遞歸函數設計八皇後問題的回溯演算法C++代碼

解析：遞歸實現n皇後問題。
演算法分析：
數組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。
代碼如下：
#include <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[i][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;iColumn<8;iColumn++)
printf("%c ",Queen[iLine][iColumn]);
printf("\n");
}
printf("\n\n");
}
//如果前次的皇後放置導致後面的放置無論如何都不能滿足要求，則回溯，重置
Queen[i][iColumn]='*';
a[iColumn]=0;
b[i-iColumn+7]=0;
c[i+iColumn]=0;
}
}
}

『玖』 高分：網路流問題

一、引言

網路流演算法是一種高效實用的演算法，相對於其它圖論演算法來說，它的模型更加復雜，編程復雜度也更高。但是它綜合了圖論中的其它一些演算法（如最短路徑、寬度搜索演算法），因而適用范圍也更廣，經常能夠很好地解決一些搜索與動態規劃無法解決的非np問題。
網路流在具體問題中的應用，最具挑戰性的部分是模型的構造，它沒用現成的模式可以套用，需要我們對各種網路流的性質了如指掌（比如點有容量、容量有上下限、多重邊等等），根據具體的問題發揮我們的創造性。一道問題經常可以建立多種模型，不同的模型對問題的解決效率的影響也是不同的，本文通過實例探討如何確定適當的模型，提高網路流演算法的效率。

二、網路流演算法時間效率

當我們確定問題可以使用最大流演算法求解後，就根據常用的ford-fulkerson標號法求解；而最小（大）費用最大流問題也可用類似標號法的對偶演算法解題。ford-fulkerson標號法的運行時間為o（ve2），對偶法求最小費用流的運行時間大約為o（v3e2）。

顯然，影響網路流演算法的時間效率的因素主要是網路中頂點的數目與邊的數目。這二個因素之間不是相互獨立的，而是相互聯系，矛盾而統一的。在構造網路模型中，有時，實現了某個因素的優化，另外一個因素也隨之得到了優化；有時，實現某個因素的優化卻要以增大另一因素為代價。因此，我們在具體問題的解決中，要堅持"全局觀"，實現二者的平衡。

三、模型的優化與選擇

(一)減少模型的頂點數與邊數，優化模型

如果能根據問題的一些特殊性質，減少網路模型中的頂點的數目和邊的數目，則可以大大提高演算法的效率。

例1：最少皇後控制

在國際象棋中，皇後能向八個方向攻擊（如圖1(a)所示，圖中黑點格子為皇後的位置，標有k的格子為皇後可攻擊到的格子）。現在給定一個m*n（n、m均不大於於50）的棋盤，棋盤上某些格子有障礙。每個皇後被放置在無障礙的格子中，它就控制了這個格子，除此，它可以從它能攻擊到的最多8個格子中選一個格子來控制，如圖1(b)所示，標號為1的格子被一個皇後所控制。

請你編一程序，計算出至少有多少個皇後才能完全控制整個棋盤。

圖1(a) 圖1(b)

輸入格式：
輸入文件的第一行有兩個整數m和n，表示棋盤的行數與列數。接下來m行n列為一個字元矩陣，用''.''號表示空白的格子，''x''表示有障礙的格子。

輸出格式：
輸出文件的第一行僅有一個數s，表示需要皇後的數目。
sample input
3 4
x...
x.x.
.x..
sample ouput
5

問題分析]

如果本問題用簡單的搜索來做，由於題目給的棋盤很大，搜索演算法很難在短時間內出解。由於一個皇後在棋盤最多隻能控制兩個格子，因此最少需要的皇後數目的下界為[n*m/2]。要使得皇後數目最少，必定是盡量多的皇後控制兩個格子。如果我們在每兩個能相互攻擊到的格子之間加上一條有向弧，則問題很類似於二分圖的最大匹配問題。

[模型一]

1． 將每個非障礙的格子按行優先編號(0~m*n-1)。
2． 將上述的每個格子i折成兩個格子i''和i''''，作為網路模型中的頂點。
3． 若格子i可以攻擊到格子j且i<j，則在模型中頂點i''到j''''之間加上一條有向弧，容量為1。
4． 增加一個源點s，從s點向所有頂點i''添上一條弧；增加一個匯點t，從所有頂點j''''到t添上一條弧，容量均為1。

圖1(b)所示的棋盤，對應的模型為：

圖2

顯然，任一解對應於以上模型的一個最大匹配。且最大匹配中，匹配數必定是偶數。因此至少需要的馬匹數為m＊n－障礙數－最大匹配數/2。

[模型二]

如果我們將棋盤塗成黑白相間的格子，則某皇後控制的兩個格子一定是一個是黑格，另一個是白格（如圖3），不妨設這兩個格子中皇後在白格子上。於是，我們將n*m個格子分成兩部分白格與黑格。因此我們可以將模型一優化為：

圖3

1．將棋盤中的所有格子分成兩個部分，對所有的格子進行編號，每個白格與它能攻擊到的黑格之間（障礙除外）添上一條從白格到黑格的弧，構成一個二分圖。

2．增加一個源點s，從s點向所有非障礙的白格添上一條弧；增加一個匯點t，從所有非障礙的黑格到t添上一條弧。

3．設置所有的弧的流量為1。
圖1(b)所示的棋盤，對應的模型為：

圖4

[兩種模型的比較]

顯然，模型二的頂點數與邊數大致是模型一的一半。下面是在bp環境下兩種模型的時間效率比較(p166/32m)：

模型一 模型二

可擴展性 不易列印出一種解 容易列印出一種解

模型二正是根據問題的特殊性（即馬的走法），將網格中的格點分成白與黑兩類，且規定馬只能從白格跳到黑格，從而避免將每個格點折分成兩個點，減少模型的頂點數，同時也大大減少了邊的數目。達到了很好的優化效果。

(二)綜合各種模型的優點，智能選擇模型

有時，同一問題的各種模型各有特色，各有利弊。這種情況下，我們就要綜合考慮各種模型的優缺點，根據測試數據智能地選擇問題的模型。

例2火星探測器（ioi97）

有一個登陸艙（pod），里邊裝有許多障礙物探測車（mev），將在火星表面著陸。著陸後，探測車離開登陸艙向相距不遠的先期到達的傳送器（transmitter）移動，mev一邊移動，一邊採集岩石（rock）標品，岩石由第一個訪問到它的mev所採集，每塊岩石只能被採集一次。但是這之後，其他mev可以從該處通過。探測車mev不能通過有障礙的地面。
本題限定探測車mev只能沿著格子向南或向東從登陸處向傳送器transmitter移動，允許多個探測車mev在同一時間占據同一位置。

任務：計算出所有探測車的移動途徑，使其送到傳送器的岩石標本的數量最多，且使得所有的探測車都必須到達傳送器。

輸入：

火星表面上的登陸艙pod和傳送器之間的位置用網路p和q表示，登陸艙pod的位置為（1，1）點，傳送器的位置在（p，q）點。

火星上的不同表面用三種不同的數字元號來表示：

0代表平坦無障礙
1代表障礙
2代表石塊。
輸入文件的組成如下：
numberofvehicles
p
q
(x1y1)(x2y1)(x3,y1)…(xp-1y1)(xpy1)
(x1y2)(x2y2)(x3,y2)…(xp-1y1)(xpy2)
(x1y3)(x2y3)(x3,y3)…(xp-1y3)(xpy3)
…
(x1yq-1)(x2yq-1)(x3,yq-1)…(xp-1yq-1)(xpyq-1)
(x1yq)(x2yq)(x3,yq)…(xp-1yq)(xpyq)
p和q是網路的大小；numberofvehicles是小於1000的整數，表示由登陸艙pod所開出的探測車的個數。共有q行數據，每行表示火星表面的一組數據，p和q都不超過128。

[模型一]

很自然我們以登陸艙的位置為源點，傳送器的位置為匯點。同時某塊岩石由第一個訪問到它的mev所採集，每塊岩石只能被採集一次。但是這之後，其他mev可以從該處通過，且允許多個探測車mev在同一時間占據同一位置。因此我們將地圖中的每個點分成兩個點，即（x,y）à(x,y,0)和(x,y,1)。具體的描述一個火星地圖的網路模型構造如下：

1． 將網格中的每個非障礙點分成(x,y)兩個點(x,y,0)和(x,y,1)，其中源點s = v(1, 1, 0),匯點t = v(maxx, maxy, 1)。

2． 在以上頂點中添加以下三種類型的邊e1,e2,e3，相應地容量和費用分別記為c1、c2、c3以及w1、w2、w3:

u e1 = v(x, y, 0) -> v(x, y, 1),c1 = maxint,w1 = 0。
u e2 = v(x, y, 0) -> v(x, y, 1)，c2 = 1，w2 = -1（這里要求(x, y)必須是礦石）
u e3 = v(x, y, 1) -> v(x'', y'', 0)，c3 = maxint,w3 = 0.

其中x''=x+1 y''=y 或x''=x y''=y+1,1 <= x'' <= maxx，1 <= y'' <= maxy，且(x'' y'')非障礙。

從以上模型中可以看出，在構造的過程中，將地圖上的一個點"拆"成了網路的兩個節點。添加e1型邊使得每個點可以被多次訪問，而添加e2型邊使得某點上的礦石對於這個網路，從s到t的一條路徑可以看作是一輛探測車的行動路線。路徑費用就是探測車搜集到的礦石的數目。對於網路g求流量為numberofvehicles的固定最小費用流，可以得到問題的解。

[模型二]

事實上，如果我們只考慮這numberofvehicles輛車中每輛車分別依次裝上哪些礦石。則每輛車經過的礦石就是一條流，因此我們以網格中的礦石為網路的頂點建立以下的網路流模型。

1. 將網格中的每個起點(網格左上角)能到達，且能從它能到達終點(右下角)的礦石 (x,y)點分成左點(x,y,0)和右點(x,y,1)兩個點，並添加源點s和匯點t。
2. 在以上頂點中添加以下五種類型的邊e1,e2,e3，相應地容量和費用分別記為c1、c2、c3以及w1、w2、w3:

u e1 = v(x, y, 0) -> v(x, y, 1),c1 = 1,w1 = -1。
u e2 = v(x, y, 1) -> v(x'', y'', 0)，c2 = 1，w2 = 0（礦石點(x, y)可到達礦石點(x'',y'')）。
u e3 = s -> v(x, y, 0)，c3 = 1,w3 = 0。
u e4 = v(x, y, 1)->t，c4 = 1,w4 = 0。
u e5=s->t,c5=maxint,w5=0。

由於每個石塊被折成兩個點，且容量為1，就保證了每個石塊只被取走一次，同時取走一塊石塊就得到-1的費用。因此對以上模型，我們求流量為numberofvehicles的最小費用流，就可得到解。

[兩種模型的比較]

1.模型一以網格為頂點，模型二以礦石為頂點，因此在頂點個數上模型二明顯優於模型一，對於一些礦石比較稀疏，而網格又比較大的數據，模型二的效率要比模型一來得高。且只要礦石的個數不超過一定數目，模型二可以處理p，q很大的數據，而模型一卻不行。

2．模型一中邊的數目最多為3*p*q，而模型二中邊的數目最壞情況下大約為p*q*(p+1)*(q+1)/4-p*q。因此在這個問題中，若對於一些礦石比較密集且網格又比較大的數據，模型二的邊數將大大超過模型一，從而使得時間效率大大低於模型一。

下面是網格中都是礦石的情況比較（piii700/128m ，bp7.0保護模式）：
numberofvehicles＝10 模型一 模型二

通過以上數據，可知對於p，q不超過60的情況，模型一都能在10秒內出解。而模型二則對於p、q＝30的最壞情況下速度就很慢了，且p、q超過30後就出現內存溢出情況，而無法解決。

因此，對於本題，以上兩種模型各有利弊，我們可根據測試數據中礦石稀疏程度來決定建立什麼樣的模型。若礦石比較稀疏，則可以考慮用建立如模型二的網路模型；若礦石比較密集則建立模型一所示網路模型。然後，再應用求最小費用最大流演算法求解。對於p，q＞60，且礦石比較多情況下，兩種模型的網路流演算法都無法求解。在實際的應用中問題經常都只要求近似解，此時還可用綜合一些其它演算法來求解。

四、結束語

綜上所述，網路流演算法中模型的優化是網路流演算法提高效率的根本。我們要根據實際問題，從減少頂點及邊的角度綜合考慮如何對模型進行優化，選擇適當的模型，以提高演算法的效率。對於有些題目，解題的各種模型各有優劣時，還可通過程序自動分析測試數據，以決定何種情況下採用何種模型，充分發揮各種模型的優點，以達到優化程序效率的目的。

『拾』 C語言中8皇後問題--怎麼解決上下兩種方法是否重復

#include "stdio.h"
#include "windows.h"
#define N 8 /* 定義棋盤大小 */
int place(int k); /* 確定某一位置皇後放置與否，放置則返回1，反之返回0 */
void backtrack(int i);/* 主遞歸函數，搜索解空間中第i層子樹 */
void chessboard(); /* 每找到一個解,列印當前棋盤狀態 */
static int sum, /* 當前已找到解的個數 */
x[N]; /* 記錄皇後的位置,x[i]表示皇後i放在棋盤的第i行的第x[i]列 */
int main(void)
{
backtrack(0);
system("pause");
return 0;
}
int place(int k)
{
/* 測試皇後k在第k行第x[k]列時是否與前面已放置好的皇後相攻擊。 x[j] == */
/* x[k] 時，兩皇後在同一列上；abs(k - j) == abs(x[j] - x[k]) 時，兩皇 */
/* 後在同一斜線上。兩種情況兩皇後都可相互攻擊，故返回0表示不符合條件。*/
for (int j = 0; j < k; j ++)
if (abs(k - j) == abs(x[j] - x[k]) || (x[j] == x[k])) return 0;
return 1;
}
void backtrack(int t)
{
/* t == N 時，演算法搜索至葉結點，得到一個新的N皇後互不攻擊的放置方案 */
if (t == N) chessboard();
else
for (int i = 0; i < N; i ++) {
x[t] = i;
if (place(t)) backtrack(t + 1);
}
}
void chessboard()
{
printf("第%d種解法:\n", ++ sum);
for (int i = 0; i < N; i ++) {
for (int j = 0; j < N; j ++)
if (j == x[i]) printf("@ ");
else printf("* ");
printf("\n");
}
printf("\n");
}