八皇后问题php 八皇后问题java

很多站长朋友们都不太清楚八皇后问题php，今天小编就来给大家整理八皇后问题php，希望对各位有所帮助，具体内容如下：

本文目录一览： 1、八皇后问题算法详解 2、谁能解释一下什么叫八皇后问题？ 3、八皇后问题 4、什麽是“八皇后问题”？八皇后问题算法详解

八皇后问题，是一个古老而著名的问题，是回溯算法的典型案例。该问题是国际西洋棋棋手马克斯·贝瑟尔于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 并继续进行下一列的计算。

谁能解释一下什么叫八皇后问题？

八皇后问题：

在8×8的国际象棋盘上，放置八个皇后，使任何一个皇后都不能吃掉另一个

国际象棋规则中，皇后可以吃到任何一个与他在同一行、同一列或者同一斜线上的敌方棋子，所以八皇后问题的所有解满足：

8个皇后都不在同一行、同一列，或者同一斜线上；

或者：

任意行、列或者斜线上有且仅有一个皇后。

比如，以下解就满足条件：

※ 0 1 2 3 4 5 6 7

q[0] 0 ●○○○○○○○

q[1] 4 ○○○○●○○○

q[2] 7 ○○○○○○○●

q[3] 5 ○○○○○●○○

q[4] 2 ○○●○○○○○

q[5] 6 ○○○○○○●○

q[6] 1 ○●○○○○○○

q[7] 3 ○○○●○○○○

八皇后问题

八皇后问题是一个古老而著名的问题，是回溯算法的典型例题。该问题是十九世纪著名的数学家高斯1850年提出：在8X8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。

高斯认为有76种方案。1854年在柏林的象棋杂志上不同的作者发表了40种不同的解，后来有人用图论的方法解出92种结果。事实上就是有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．程序清单如下

＃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);

}

//历遍完成就停止

什麽是“八皇后问题”？

八皇后问题

开放分类：编程、计算机

高斯认为有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 + ": " );

for ( i=0 ; i<size ; i++ ) {

System.out.print ( "(" + i + "," + data + ") " );

}

System.out.println ();

}

public static void main(String args[]) {

(new Queen())测试数据pute( 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);

}

//历遍完成就停止

}

五、java实现//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);

}

//历遍完成就停止

}

六、c＃实现

采用的思路大致是这样：

将一个皇后向下移动一个位置；

如果没有成功移动（超出边界），失败；

如果成功移动，则判断当前位置是否可用？如果不可用，则重做 1；

继续给下一个皇后安排位置。

结束条件：

如果第一个皇后的所有位置都尝试完毕仍然没有可用的解决方案或者最后一个皇后已经安排完毕。

代码如下：

1// AppEntry.cs

2using System;

4namespace Chenglin

6 class AppEntry

7 {

8 static void Main(string[] args)

9 {

10 int queenNumber = 8;

11 QueenRowCollection q = new QueenRowCollection(queenNumber);

13 bool flag;

14 DateTime timeStarted = DateTime.Now;

15 flag = q.PositionQueens();

16 TimeSpan ts = DateTime.Now.Subtract( timeStarted );

19 if( flag ) {

20 Console.WriteLine( q.ToString() );

21 }

22 else {

23 Console.WriteLine( "Failed" );

24 }

26 Console.WriteLine( " seconds has been elapsed.", ts.TotalSeconds );

27 }

28 }

29} 1// QueenRowCollection.cs

2using System;

3using System.Text;

5namespace Chenglin

7 public class QueenRowCollection

8 {

10 public QueenRowCollection( int numberOfQueens ){

11 this.numberOfQueens = numberOfQueens;

12 this.rows = new QueenRow[ numberOfQueens ];

14 for( int i=0;i<numberOfQueens;i++ ){

15 rows = new QueenRow( numberOfQueens );

16 }

17 }

19 public bool PositionQueens()

20 {

21 return PositionQueen( 0 );

22 }

24 private bool PositionQueen( int row )

25 {

26 if( row>=this.numberOfQueens ) {

27 return true;

28 }

30 QueenRow q = rows[row];

31 while( q.MoveNext() )

32 {

33 if( PositionAvailable( row, q.CurrentPosition ) ) {

34 // An available position has been found for the current queen,

35 // and try to find a proper position for the next queen.

36 //

37 // If no available position can be found for the next queen,

38 // the current queen should move to the next position and try again.

39 //

40 if( PositionQueen( row+1 ) )

41 {

42 // Both the current queen and the next queen

43 // have found available positions.

44 //

45 return true;

46 }

47 }

48 }

50 // No position is available for the current queen,

51 //

52 return false;

53 }

55 private bool PositionAvailable( int row, int column ){

56 for( int i=row-1; i>=0; i-- )

57 {

58 if( rows.PositionOccupied( column ) )

59 return false;

61 if( rows.PositionOccupied( column-(i-row) ) )

62 return false;

64 if( rows.PositionOccupied( column+(i-row) ) )

65 return false;

66 }

68 return true;

69 }

71 public override string ToString()

72 {

73 StringBuilder s = new StringBuilder();

75 foreach( QueenRow q in rows ){

76 s.AppendFormat( "", q, Environment.NewLine );

77 }

79 return s.ToString();

80 }

82 private int numberOfQueens;

83 private QueenRow [] rows;

84 }

85} 1// QueenRow.cs

2using System;

3using System.Text;

5namespace Chenglin

7 public class QueenRow

8 {

9 public QueenRow( int numberOfPositions )

10 {

11 this.numberOfPositions = numberOfPositions;

12 this.currentPosition = -1;

13 this.columns = new bool[ numberOfPositions ];

14 }

16 public bool MoveNext(){

17 if( currentPosition>=0 currentPosition<this.numberOfPositions ){

18 columns[currentPosition] = false;

19 }

21 if( currentPosition<this.numberOfPositions-1){

22 currentPosition ++;

23 columns[currentPosition] = true;

24 return true;

25 }

26 else {

27 currentPosition = -1;

28 return false;

29 }

30 }

32 public bool PositionOccupied( int column ){

33 if( column<0 || column>=numberOfPositions ){

34 return false;

35 }

37 return columns[column];

38 }

40 public override string ToString()

41 {

42 StringBuilder s = new StringBuilder();

44 foreach( bool b in columns ){

45 s.AppendFormat( " ", (b ? "*" : "-") );

46 }

48 return s.ToString();

49 }

51 public int CurrentPosition

52 {

53 get { return currentPosition; }

54 }

56 private int currentPosition;

57 private int numberOfPositions;

58 private bool [] columns;

59 }

60}

程序运行的时候，当皇后个数增加的时候，运行的时间也会急剧增加！下面这副图表示了皇后个数与运行时间的大致关系：

关于八皇后问题php的介绍到此就结束了，不知道本篇文章是否对您有帮助呢？如果你还想了解更多此类信息，记得收藏关注本站，我们会不定期更新哦。

查看更多关于八皇后问题php 八皇后问题java的详细内容...

声明：本文来自网络，不代表【好得很程序员自学网】立场，转载请注明出处：http://haodehen.cn/did165250

更新时间：2023-02-17 阅读：33次