八皇后问题-计算机技术- 科技百科 -互联网博物馆，你我的知识加油站

八皇后问题是一个古老而著名的问题，是回溯算法的典型例题。该问题是十九世纪著名的数学家高斯1850年提出：在8X8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。
高斯认为有76种方案。1854年在柏林的象棋杂志上不同的作者发表了40种不同的解，后来有人用图论的方法解出92种结果。
　　对于八皇后问题的实现，如果结合动态的图形演示，则可以使算法的描述更形象、更生动，使教学能产生良好的效果。下面是用Turbo C实现的八皇后问题的图形程序，能够演示全部的92组解。八皇后问题动态图形的实现，主要应解决以下两个问题。
（1）回溯算法的实现
　　（a）为解决这个问题，我们把棋盘的横坐标定为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)的对角线（右上至左下）有皇后
　　（b）为第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 errorn");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=1;
for (i=0;i<=14;i++) b=1;
for (i=0;i<=23;i++) c=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);
}
二、循环实现 Java

/*
* ８皇后问题：
*
* 问题描述：
* 在一个８×８的棋盘里放置８个皇后，要求每个皇后两两之间不相冲突
*（在每一横列，竖列，斜列只有一个皇后）。
*
* 数据表示：
* 用一个 8 位的 8 进制数表示棋盘上皇后的位置：
* 比如：45615353 表示：
*    第0列皇后在第4个位置
*    第1列皇后在第5个位置
*    第2列皇后在第6个位置
*    。。。
*    第7列皇后在第3个位置
*
* 循环变量从 00000000 加到 77777777 （8进制数）的过程，就遍历了皇后所有的情况
* 程序中用八进制数用一个一维数组 data【】表示
*
* 检测冲突：
*    横列冲突：data == data【j】
*    斜列冲突：(data+i) == (data【j】+j) 或者 (data-i) == (data【j】-j)
*
* 好处：
* 采用循环，而不是递规，系统资源占有少
* 可计算 n 皇后问题
* 把问题线性化处理，可以把问题分块，在分布式环境下用多台计算机一起算。
*
* ToDo：
* 枚举部分还可以进行优化，多加些判断条件速度可以更快。
* 输出部分可以修改成棋盘形式的输出
*
* @author cinc 2002-09-11
*
*/

public class Queen {
int size;
int resultCount;

public void compute ( int size ) {
      this.size = size;
      resultCount = 0;
      int data【】 = new int【size】;
      int count; // 所有可能的情况个数
      int i,j;

      // 计算所有可能的情况的个数
      count = 1;
      for ( i=0 ; i<size ; i++ ) {
         count = count * size;
      }
      // 对每一个可能的情况
      for ( i=0 ; i<count ; i++ ) {
         // 计算这种情况下的棋盘上皇后的摆放位置，用 8 进制数表示
         // 此处可优化
         int temp = i;
         for ( j=0 ; j<size ; j++ ) {
            data 【j】 = temp % size;
            temp = temp / size;
         }
         // 测试这种情况是否可行，如果可以，输出
         if ( test(data) )
            output( data );
      }
}

/*
   * 测试这种情况皇后的排列是否可行
   *
   */
public boolean test( int【】 data ) {
      int i,j;
      for ( i=0 ; i<size ; i++ ) {
         for ( j=i+1 ; j<size ; j++ ) {
            // 测试是否在同一排
            if ( data == data【j】 )
                  return false;
            // 测试是否在一斜线
            if ( (data+i) == (data【j】+j) )
                  return false;
            // 测试是否在一反斜线
            if ( (data-i) == (data【j】-j) )
                  return false;
         }
      }
      return true;
}

/*
   * 输出某种情况下皇后的坐标
   *
   */
public void output ( int【】 data ) {
      int i;
      System.out.print ( ++resultCount + ": " );
      for ( i=0 ; i<size ; i++ ) {
         System.out.print ( "(" + i + "," + data + ") " );
      }
      System.out.println ();
}
public static void main(String args【】) {
      (new Queen()).compute( 8 );
}
}
三、八皇后问题的Qbasic版的解决方案

10 I = 1

20 A(I) = 1

30 G = 1

40 FOR K = I - 1 TO 1 STEP -1

50 IF A(I) = A(K) THEN 70

60 IF ABS(A(I) - A(K)) <> I - K THEN 90

70 G = 0

80 GOTO 100

90 NEXT K

100 IF I <> 8 THEN 180

110 IF G = 0 THEN 180

120 FOR L = 1 TO 8

130 PRINT USING “##”; A(L);

140 NEXT L

150 PRINT “*”;

160 M = M + 1

170 IF M MOD 3 = 0 THEN PRINT

180 IF G = 0 THEN 230

190 IF I = 8 THEN 230

200 I = I + 1

210 A(I) = 1

220 GOTO 30

230 IF A(I) < 8 THEN 270

240 I = I - 1

250 IF I = 0 THEN 290

260 GOTO 230

270 A(I) = A(I) + 1

280 GOTO 30

290 PRINT

300 PRINT “SUM=”; USING “##”; M;

310 PRINT

320 END
四、八皇后问题的高效解法-递归版

//8 Queen 递归算法
//如果有一个Q 为 chess=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=-1;
placequeen(0);
System.out.println("nnn八皇后共有"+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=true;

//下面先把安全位数组完成
i=0;//i 是现在要检查的数组值
while (i<num){
   qsave【chess】=false;
   int k=num-i;
   if ( (chess+k >= 0) && (chess+k < QueenMax) ) qsave【chess+k】=false;
   if ( (chess-k >= 0) && (chess-k < QueenMax) ) qsave【chess-k】=false;
   i++;
}
//下面历遍安全位
for(i=0;i<QueenMax;i++){
   if (qsave==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==0);
   else
      for(int j=0;j<chess;j++) row+="--";
      row+="++";
      int j = chess;
      while(j<QueenMax-1){row+="--";j++;}
   System.out.println(row);
   }
   }
}
  //历遍完成就停止
  }
}

八皇后问题发表评论(0) 编辑词条

对词条发表评论

八皇后问题 发表评论(0) 编辑词条

对词条发表评论

八皇后问题发表评论(0) 编辑词条