程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C >> C語言基礎知識 >> 八皇後動態圖形的實現

八皇後動態圖形的實現

編輯:C語言基礎知識

  八皇後問題是一個古老而聞名的問題,是回溯算法的典型例題。該問題是十九世紀聞名的數學家高斯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,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)
  {printf("Graphics error ");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. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved