八皇後演算法題
① 八皇後問題的C語言代碼
#include <math.h>
#include <stdio.h>
#define MAX 8 /* 棋子數及棋盤大小MAXxMAX */
int board[MAX];
/* 印出結果 */
void show_result()
{
int i;
for(i=0;i<MAX;i++)
printf("(%d,%d)",i,board[i]);
printf("\n");
}
/* 檢查是否在同一直橫斜線上有其它棋子 */
int check_cross(int n)
{
int i;
for(i=0;i<n;i++){
if(board[i]==board[n] || (n-i)==abs(board[i]-board[n]))return 1;
}
return 0;
}
/* 放棋子到棋盤上 */
void put_chess(int n)
{
int i;
for(i=0;i<MAX;i++){
board[n]=i;
if(!check_cross(n)){
if(n==MAX-1) show_result();/* 找到其中一種放法了...印出結果 */
else put_chess(n+1);
}
}
}
void main()
{
clrscr();
puts("The possible placements are:");
put_chess(0);
puts("\n Press any key to quit...");
getch();
return;
}
到底是哪些奇葩老師布置的作業？
② 八皇後問題是什麼問題呀
這就是著名的八皇後問題。八個皇後在排列時不能同在一行、一列或一條斜
線上。在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);
}
}
}
//歷遍完成就停止
③ 八皇後問題演算法詳解
八皇後問題，是一個古老而著名的問題，是 回溯演算法 的典型案例。該問題是國際西洋棋棋手馬克斯·貝瑟爾於1848年提出：在8×8格的國際象棋上擺放八個皇後，使其不能互相攻擊，即任意兩個皇後都不能處於同一行、同一列或同一斜線上，問有多少種擺法。 高斯 認為有76種方案。1854年在柏林的擾游象棋雜志上不同的作者發表了40種不同的解，後來有人用圖論的方法解出92種結果。
本文緩帆銷的主要描述的是基於回溯演算法轎備思想的求解演算法，並盡可能在細節上給予讀者直觀展示，以使得讀者可以有更好的理解。拋磚引玉，如有錯誤請不吝賜教。
演算法的關鍵在於用一個二維數組chess [ ] [ ] 來記錄每一個位置(第 i 行第 j 列)是否合法（行列對角線上沒有填皇後，對應於數組 chess [ i ] [ j ] 為 0），用一個一維數Queenplace [ ] 組來記錄每一行上皇後的列標（比如Queenplace [ row ] =column 表示第 row 行第 column 列填入皇後）。
行數 i 從第一行開始，遍歷每一列 j ，如果chess [ i ] [ j ] 為0，那麼說明此位置可以填入皇後，則將chess中與此位置同行同列同對角線的value自增 1 並且在 數組Queenplace 中記錄相應的坐標。然後遞歸計算每一行直到最後一行成功填入皇後並在此時列印棋盤 。最後進行回溯，恢復chess [ ] [ ] ，將chess中與此位置同行同列同對角線的value自減 1 並繼續進行下一列的計算。
④ 用C語言編寫八皇後問題
#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");
}
⑤ 八皇後問題求解的C語言程序的實現
這是個前不久,我為別人寫的一個代碼;
八皇後問題共有92種解;
以下代碼是解決:對於固定一個皇後位置,輸出所有可能情況.
如果這不適合你的答案你可以,稍微改改的哦~~
代碼如下:
#include "stdio.h"
bool board[8][8]={0};
int num=0; //滿足條件的個數
int inix,iniy; //輸入一個皇後的初始位置
void output() //輸出
{
int i, j;
for(i=0;i<8;i++)
{
for(j=0;j<8;j++)
{
if(!board[i][j]) printf("■ ");
else printf("◆ ");
}
printf("\n");
}
num++;
printf("\n\n");
return ;
}
bool check(int x,int y) //判斷是否能放
{
int i, j ;
for(i=0; i<8 ; i++)
{
if(board[i][y]==1) return false;
}
for(i=0;i<8;i++)
{
if(board[x][i]==1) return false;
}
i=x; j=y;
while(i>0 && j>0 ) { i--; j--; }
for(;i<8 && j<8 ; i++,j++)
if(board[i][j]==1) return false;
i=x; j=y;
while(i>0 && j<7 ) {i--;j++;}
for(;i<8 && j>=0 ; i++ ,j--)
if(board[i][j]==1) return false ;
return true ;
}
void search(int x,int num) // 搜索函數
{
int i;
if(num>=8) { output(); return ;}
if(x==inix-1) search(inix,num+1);
else
{
for(i=0;i<8;i++)
{
if(check(x,i))
{
board[x][i]=1;
search(x+1,num+1);
board[x][i]=0;
}
}
}
return ;
}
int main()
{
scanf("%d %d",&inix,&iniy);
board[inix-1][iniy-1] = 1 ;
search(0,0);
printf("%d\n",num);
return 0;
}
例如:
輸入 : 1 1
輸出 :
◆ ■ ■ ■ ■ ■ ■ ■
■ ■ ■ ■ ◆ ■ ■ ■
■ ■ ■ ■ ■ ■ ■ ◆
■ ■ ■ ■ ■ ◆ ■ ■
■ ■ ◆ ■ ■ ■ ■ ■
■ ■ ■ ■ ■ ■ ◆ ■
■ ◆ ■ ■ ■ ■ ■ ■
■ ■ ■ ◆ ■ ■ ■ ■
◆ ■ ■ ■ ■ ■ ■ ■
■ ■ ■ ■ ■ ◆ ■ ■
■ ■ ■ ■ ■ ■ ■ ◆
■ ■ ◆ ■ ■ ■ ■ ■
■ ■ ■ ■ ■ ■ ◆ ■
■ ■ ■ ◆ ■ ■ ■ ■
■ ◆ ■ ■ ■ ■ ■ ■
■ ■ ■ ■ ◆ ■ ■ ■
◆ ■ ■ ■ ■ ■ ■ ■
■ ■ ■ ■ ■ ■ ◆ ■
■ ■ ■ ◆ ■ ■ ■ ■
■ ■ ■ ■ ■ ◆ ■ ■
■ ■ ■ ■ ■ ■ ■ ◆
■ ◆ ■ ■ ■ ■ ■ ■
■ ■ ■ ■ ◆ ■ ■ ■
■ ■ ◆ ■ ■ ■ ■ ■
◆ ■ ■ ■ ■ ■ ■ ■
■ ■ ■ ■ ■ ■ ◆ ■
■ ■ ■ ■ ◆ ■ ■ ■
■ ■ ■ ■ ■ ■ ■ ◆
■ ◆ ■ ■ ■ ■ ■ ■
■ ■ ■ ◆ ■ ■ ■ ■
■ ■ ■ ■ ■ ◆ ■ ■
■ ■ ◆ ■ ■ ■ ■ ■
4
⑥ 八皇後究竟有多少種解法怎麼解
八皇後問題是一個古老而著名的問題，是回溯演算法的典型例題。該問題是十九世紀著名的數學家高斯1850年提出：在8X8格的國際象棋上擺放八個皇後，使其不能互相攻擊，即任意兩個皇後都不能處於同一行、同一列或同一斜線慶段上，問有多少種擺法。 高斯認為有76種方案。1854年在柏林的象譽頌譽棋雜志上不同的作者發表了40種不同的解，後來有人用圖論的方法解出92種結果。 對於八皇後問題的實現，如果結合動態的圖形演示，則可以使演算法的描述櫻猜更形象、更生動，使教學能產生良好的效果。下面是用Turbo C實現的八皇後問題的圖形程序，能夠演示全部的92組解。八皇後問題動態圖形的實現