八皇后问题

来源(百度百科)

From: http://baike.baidu.com/view/698719.html

八皇后问题是一个古老而著名的问题,是回溯算法的典型例题。该问题是十九世纪著名的数学家高斯1850年提出:在8X8格的国际象棋上摆放八个皇后,使其不能互相攻击,即任意两个皇后都不能处于同一行、同一列或同一斜线上,问有多少种摆法。
高斯认为有76种方案。1854年在柏林的象棋杂志上不同的作者发表了40种不同的解,后来有人用图论的方法解出92种结果。
对于八皇后问题的实现,如果结合动态的图形演示,则可以使算法的描述更形象、更生动,使教学能产生良好的效果。下面是用Turbo C实现的八皇后问题的图形程序,能够演示全部的92组解。八皇后问题动态图形的实现,主要应解决以下两个问题。
(1)回溯算法的实现
(a)为解决这个问题,我们把棋盘的横坐标定为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)的对角线(右上至左下)有皇后
(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 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=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×8的棋盘里放置8个皇后,要求每个皇后两两之间不相冲突
*(在每一横列,竖列,斜列只有一个皇后)。
*
* 数据表示:
* 用一个 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 + &quot;: &quot; );
        for ( i=0 ; i<size ; i++ ) {
            System.out.print ( &quot;(&quot; + i + &quot;,&quot; + data + &quot;) &quot; );
        }
        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("\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=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);
                }
            }
        }
        //历遍完成就停止
    }
}

Link: http://www.asm32.net/article_details.aspx?id=3481


浏览次数 173 发布时间 2008-02-03 15:51:36 从属分类 ARITHMETIC 【评论】【 】【打印】【关闭
 
| www.asm32.net | 2006版 | 资料中心 | linux | asm/asm32 | C/C++ | VC++ | java | Python | 书签 | ASP.Net书签 | 京ICP备09029108号-1