八皇后動態圖形的實現

2019-11-17 05:38:42

字體：大中小

來源：轉載

供稿：網友

　　八皇后問題是一個古老而聞名的問題，是回溯算法的典型例題。該問題是十九世紀聞名的數學家高斯1850年提出：在8X8格的國際象棋上擺放八個皇后，使其不能互相攻擊，即任意兩個皇后都不能處于同一行、同一列或同一斜線上，問有多少種擺法。
　　高斯認為有76種方案。1854年在柏林的象棋雜志上不同的作者發表了40種不同的解，后來有人用圖論的方法解出92種結果。
　　對于八皇后問題的實現，假如結合動態的圖形演示，則可以使算法的描述更形象、更生動，使教學能產生良好的效果。下面是筆者用Turbo C實現的八皇后問題的圖形程序，能夠演示全部的92組解。八皇后問題動態圖形的實現，主要應解決以下兩個問題。
1．回溯算法的實現
（1）為解決這個問題，我們把棋盤的橫坐標定為i，縱坐標定為j,i和j的取值范圍是從１到８。當某個皇后占了位置(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,copy)將位圖置于屏幕上以（x，y）左上角的區域。3．程序清單如下#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);
}
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)
{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(TR ipLEX_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);
}

上一篇：WinHelp API命令方法

下一篇：八皇后問題