《八皇后问题》解题报告
这里八皇后问题使用递归式深搜解法。要点在于：首先深搜方法得出部分排列，再判断这样的排列是否满足不互相攻击，满足则进行下一阶段搜索，否则搜索本阶段下一个部分排列，至本阶段搜索完则回溯。
主要的两个难点是深搜函数和判断是否会相互攻击。前者已经有详细的讲解，故不做过多叙述；主要对后者做讨论。我们把问题作简化：很容易知道，对于每行与每列，有且只有一个皇后。如果对64个点选出8个做深搜进行判断，既不利于判断函数编写，也不利于程序的效率（程序需要运行64！/56！次）。既然具备简化问题的条件，我们应该积极地寻求解决问题的方法。我们利用下标存储行号，建立数组存储每一行对应的列，就极大地简化了数据量。
接下来是判断函数的编写。做一个简单的推理：添加一个新的皇后时，只需检查它与之前的皇后是否有冲突。同时由于新皇后一定在旧后的下边，故简化后我们只需判断新皇后是否在如图线上：（为节省时间简化问题至6个皇后）（黄色六芒星表示皇后，红色圆表示攻击范围）。
对问题再次做简化以适应于简易的算法：我们得到需要判断的某行，在这样的一行，对于某个皇后，最多只有两个位置可被攻击到。进行一次循环并判断，即可得到所求的解。这样的点可以用简单的几何方法求得。
至此把判断的问题难点已经攻破。
#define STATUS
int& //沿用我曾看过的一本数据结构书的方法
把返回状态的函数返回值类型
&&&&&&&&&&&&&
//定义为status
#include&&
//提供getch()方法以中断程序提供视点
#include& //提供memset方法但似乎没用上。。
&&&&&&&&&&&&&
//好多东西说成了java的方式。。
wer=0,ans[100];//wer存储题解个数
ans数组存储解并即时输出
STATUS vis[100];
//vis 数组表示当前的访问状态&&
dfs(int);& //深度搜索的函数声明
print();&& //输出的函数声明
judge(int,int);//判断函数声明
&& for(int
i=1;i&=Q;i++)
printf("%d",ans[i]);//依序输出当前取得的解
printf("\n");&&&
wer++;&&&&&&&&&&
//解的个数自增
if(wer==0)getch();//每输出10个暂停一下
STATUS judge(int
n,int p)//这里判断是否放置的皇后会互相攻击
{&&&&&&&&&&&&&&&
//传来的参数表示新皇后放置 第n行第p列&
&&&&&&&&&&&&&&&&
&& for(int
i=1;i对于从第一个到第n个每一个皇后进行下列检测
&//if(p==ans[i])return -1;//首先判断是否处于同一列上
&//突然意识到没有这样做的必要,因为八皇后问题实质上是全排列的特例,
&//不可能出现两皇后同列
&int shift=n-i;//存储“偏移量”，对应新添加的n+1层在对角线上的点
&&&&&&&&&&
&//相对第一层列坐标的位置变化，详见我编完程序画张图~
&if(p==ans[i]+shift||p==ans[i]-shift)&
return -1;
&&&&&&&&&&
//判断是否在一条对角线上
&&&&&&&&&&
//i+-shift可能会溢出，但是溢出后不会相等，故无需做判断&
0;& //检测通过&&&&&&&&&&&
}&&&&&&&&&&&&&&&&&&&&
void dfs(int
&if(n==Q+1)//递推至n+1层
print();//输出答案
&& for(int
i=1;i&=Q;i++)//升序搜索满足条件的答案
if(!vis[i])//如果这一列没有皇后
if(judge(n,i)==0)//如果对于新皇后放置在第n行第p列的情况不致互相攻击
&&&&&&&&&&
ans[n]=i;//把第n行的皇后放置在第i列
&&&&&&&&&&
vis[i]=1;//第i列已放置皇后
&&&&&&&&&&
dfs(n+1);//进行下一行的搜索
&&&&&&&&&&
vis[i]=0;//此时已经是回溯到上一行的搜索，重新把第i列置空
dfs(1);//从第1行进行皇后的搜索
printf("%d\n",wer);//输出解的个数
getch();//全部运行完毕 制造断点供观看
这是我第一次做这样的解题报告，排版什么的都很渣，希望勿怪。部分思路沿用自网上及此前的知识储备，还有很多想法是自己想到的。
值得注意的是，与上一次的全排列不同，主函数调用dfs函数时参数是1，否则无法产生正确结果。计算机世界千变万化，有时候我们需要存储更多的数据来减少计算（动态规划等）；有时候我们却在简化存储方式的同时也简化了问题。我们致力于做更好的算法，这条路任重道远，我们会继续下去！
黑科大Acm小组
已投稿到：
以上网友发言只代表其个人观点，不代表新浪网的观点或立场。4138人阅读
Algorithm（4）
八皇后问题递归求解
& & & && 首先介绍一下八皇后问题，八问题，是一个古老而著名的问题，是的典型例题。该问题是十九世纪著名的数学家1850年提出：在8X8格的上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。
高斯认为有76种方案。1854年在的象棋杂志上不同的作者发表了40种不同的解，后来有人用图论的方法解出92种结果。计算机发明后，有多种方法可以解决此问题。
&首先采取按行放置皇后，即先放第一行的皇后，放置后，然后在第二行上放置皇后，并进行借测，不冲突的话继续放置第三行，一次类推，到最后发现超过8行后结束。
* 八皇后问题
* @author Yuedong
public class EightQueens {
static int b[]={0,0,0,0,0,0,0,0};
static int sum=0;
static int times=1;
public static void main(String[] args){
search(0);
System.out.println(&一共有&+sum+&个结果&);
* 搜索指定行
* @param row
private static void search(int row){
if(row==8){
sum++;
printResult();
for(int i=0;i&8;i++){
if(check(row,i)){
search(row+1);
* 检查m,n 这个位置是否冲突
* @param row
* @param col
private static boolean check(int row,int col){
for(int i=0;i&i++){
if(b[i]==col){
if((b[i]+i)==(row+col)){
if((b[i]-i)==(col-row)){
* 打印结果
private static void printResult(){
System.out.print(times+++&： &);
for(int i=0;i&8;i++){
System.out.print(b[i]+& &);
System.out.println(& &);
参考知识库
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：472901次
积分：5025
积分：5025
排名：第4593名
原创：117篇
评论：121条
(1)(1)(1)(4)(1)(3)(1)(3)(6)(2)(2)(1)(1)(3)(2)(5)(12)(1)(2)(3)(2)(9)(4)(2)(7)(5)(7)(6)(2)(2)(3)(17)1107人阅读
会下国际象棋的人都很清楚：皇后可以在横、竖、斜线上不限步数地吃掉其他棋子。如何将8个皇后放在棋盘上（有8 * 8个方格），使它们谁也不能被吃掉！这就是著名的八皇后问题。 对于某个满足要求的8皇后的摆放方法，定义一个皇后串a与之对应，即a=b1b2...b8，其中bi为相应摆法中第i行皇后所处的列数。已经知道8皇后问题一共有92组解（即92个不同的皇后串）。给出一个数b，要求输出第b个串。串的比较是这样的：皇后串x置于皇后串y之前，当且仅当将x视为整数时比y小。&
第1行是测试数据的组数n，后面跟着n行输入。每组测试数据占1行，包括一个正整数b(1 &= b &= 92)
n行，每行输出对应一个输入。输出应是一个正整数，是对应于b的皇后串
解题思路一
因为要求出92种不同摆放方法中的任意一种，所以我们不妨把92种不同的摆放方法一次性求出来，存放在一个数组里。为求解这道题我们需要有一个矩阵仿真棋盘，每次试放一个棋子时只能放在尚未被控制的格子上，一旦放置了一个新棋子，就在它所能控制的所有位置上设置标记，如此下去把八个棋子放好。当完成一种摆放时，就要尝试下一种。若要按照字典序将可行的摆放方法记录下来，就要按照一定的顺序进行尝试。也就是将第一个棋子按照从小到大的顺序尝试；对于第一个棋子的每一个位置，将第二个棋子从可行的位置从小到大的顺序尝试；在第一第二个棋子固定的情况下，将第三个棋子从可行的位置从小到大的顺序尝试；依次类推。
首先，我们有一个8*8的矩阵仿真棋盘标识当前已经摆放好的棋子所控制的区域。用一个有92行每行8个元素的二维数组记录可行的摆放方法。用一个递归程序来实现尝试摆放的过程。基本思想是假设我们将第一个棋子摆好，并设置了它所控制的区域，则这个问题变成了一个7皇后问题，用与8皇后同样的方法可以获得问题的解。那我们就把重心放在如何摆放一个皇后棋子上，摆放的基本步骤是：从第1到第8个位置，顺序地尝试将棋子放置在每一个未被控制的位置上，设置该棋子所控制的格子，将问题变为更小规模的问题向下递归，需要注意的是每次尝试一个新的未被控制的位置前，要将上一次尝试的位置所控制的格子复原。
参考程序一
#include &stdio.h&
#include &math.h&
int queenPlaces[92][8]; //存放92种皇后棋子的摆放方法
int count = 0;
int board[8][8]; //仿真棋盘
void putQueen(int ithQueen); //递归函数，每次摆好一个棋子
void main()
for(i = 0; i & 8; i++){
for(j = 0; j & 8; j++)
board[i][j] = -1;
for(j = 0; j & 92; j++)
queenPlaces[j][i] = 0;
putQueen(0); //从第0个棋子开始摆放，运行的结果是将queenPlaces生成好
scanf(&%d&, &n);
for(i = 0; i & i++){
scanf(&%d&, &ith);
for(j = 0; j & 8; j++)
printf(&%d&, queenPlaces[ith - 1][j]);
printf(&\n&);
void putQueen(int ithQueen){
if(ithQueen == 8){
for(i = 0; i & 8; i++){
if(board[i][ithQueen] == -1){
//摆放皇后
board[i][ithQueen] = ithQ
//将其后所有的摆放方法的第ith个皇后都放在i+1的位置上
//在i增加以后，后面的第ith个皇后摆放方法后覆盖此时的设置
for(k = k & 92; k++)
queenPlaces[k][ithQueen] = i + 1;
//设置控制范围
for(k = 0; k & 8; k++)
for(r = 0; r & 8; r++)
if(board[k][r] == -1 &&
(k == i || r == ithQueen || abs(k - i) == abs(r - ithQueen)))
board[k][r] = ithQ
//向下级递归
putQueen(ithQueen + 1);
//回溯，撤销控制范围
for(k = 0; k & 8; k++)
for(r = 0; r & 8; r++)
if(board[k][r] == ithQueen) board[k][r] = -1;
解题思路二
上面的方法用一个二维数组来记录棋盘被已经放置的棋子的控制情况，每次有新的棋子放置时用了枚举法来判断它控制的范围。还可以用三个一维数组来分别记录每一列，每个45度的斜线和每个135度的斜线上是否已经被已放置的棋子控制，这样每次有新的棋子放置时，不必再搜索它的控制范围，可以直接通过三个一维数组判断它是否与已经放置的棋子冲突，在不冲突的情况下，也可以通过分别设置三个一维数组的相应的值，来记录新棋子的控制范围。
参考程序二
#include &stdio.h&
record[92][9], mark[9], count = 0; //record记录全部解，mark记录当前解；
bool range[9], line1[17], line2[17]; //分别记录列方向，45度，135度方向上被控制的情况
void tryToPut(int ); //求全部解的过程
void main()
int i, testtimes,
scanf(&%d&, &testtimes);
for(i = 0; i &=8; i++)
range[i] =
for(i = 0; i & 17; i ++)
line1[i] = line2[i] =
tryToPut(1);
while(testtimes --){
scanf(&%d&, &num);
for(i = 1; i &=8; i++)
printf(&%d&, record[num - 1][i]);
printf(&\n&);
void tryToPut(int i){
if(i & 8){ //如果最后一个皇后被放置完毕，将当前解复制到全部解中
for(int k = 1; k & 9; k ++)
record[count][k] = mark[k];
for(int j=1; j&=8; j++){ 逐一尝试将当前皇后放置在不同列上
if(range[j] && line1 [i + j] && line2[i - j + 9]){ //如果与前面的不冲突，
//则把当前皇后放置在当前位置
range[j] = line1[i + j] = line2[i - j + 9] =
tryToPut(i + 1);
range[j] = line1[i + j] = line2[i - j + 9] =
解题思路三
这个题目也可以不用仿真棋盘来模拟已放置棋子的控制区域，而只用一个有8个元素的数组记录已经摆放的棋子摆在什么位置，当要放置一个新的棋子时，只需要判断它与已经放置的棋子之间是否冲突就行了。
参考程序三
#include &stdio.h&
int ans[92][8], n, b, i, j, num, hang[8];
void queen(int i){
if(i == 8){ //一组新的解产生了
for(j = 0; j & 8; j++)
ans[num][j] = hang[j] + 1;
for (j=0; j&8; j++){ //将当前皇后i逐一尝试放置在不同的列
for(k=0; k&i; k++) //逐一判定i与前面的皇后是否冲突
if( hang[k] == j || (k - i) == (hang[k] - j) || (i - k) == (hang[k] - j ))
if (k == i) {
//放置i，尝试第i+1个皇后
queen(i + 1);
void main( ){
scanf(“%d”, &n);
for(i = 0; i & i++){
scanf(“%d”, &b);
for(j = 0; j & 8; j++)
printf(“%d”, ans[b - 1][j]);
printf(“\n”);
实现中常见的问题
问题一： 使用枚举法，穷举8个皇后的所有可能位置组合，逐一判断是否可以互相被吃掉，得到超时错误；
问题二：对于多组输入，有多组输出，没有在每组输出后加换行符，得到格式错；
问题三：对输入输出的函数不熟悉，试图将数字转换成字符或者将8个整数转换成8位的十进制整数来完成输出，形成不必要的冗余代码。
参考知识库
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：6593次
排名：千里之外
原创：31篇
(1)(1)(21)(4)(3)(1)(1)八皇后问题答案
八皇后问题答案
09-03-12 &匿名提问
几天没有上Qzone了。 --------------------------------- 八皇后问题：国际象棋中，皇后是可以横走，直走，斜走最强大的棋子。在一个8乘8的棋盘上，如何放置最多数量的皇后，使这些皇后互相不吃。答案中的数字很简单，因为每行每列最多只能一个皇后，所以最多只能8个皇后出现在一个64格棋盘上。但是如何放这些皇后让她们互相不吃，就有点头疼了。 背后的小故事： 1995年我第一次在数学读物上看到这个八皇后问题，同时也知道如何手动的使用穷举法去做这个题目，但是没有想过用计算机去解决它。1997年来新加坡后，有天我的Roommate，来自清华的一个朋友，在自学离散数学 [阅读全文] [PDF]
请登录后再发表评论!
练手写的，参考吧，因为找不到C++写的，只好自己写了一个答案：0 1 2 3 4 5 6 #0 1 2 # 4 5 6 7# 1 2 3 4 5 6 70 1 # 3 4 5 6 70 1 2 3 4 # 6 70 # 2 3 4 5 6 70 1 2 3 4 5 # 70 1 2 3 # 5 6 7count=92#include &stdio.h&#include &iostream&#include &iomanip&class Queen{public:    Queen(int i=0):count(0)    {        cout&&&Queen.&&&        for(int i=0;i&8;i++)flag[i]=0;    }    void printFlag()    {        for(int i=0;i&8;i++)        {            for(int k=0;k&flag[i];k++)    cout&&k&&& &;            cout&&&#&&&& &;            for(int k=0;k&8-flag[i]-1;k++)    cout&&k+flag[i]+1&&& &;            cout&&        }        cout&&    }    void trial(int x, int y)    {        //cout&&&x=&&&x&&& y=&&&y&&        flag[y]=x;        if(7 == y)        {            count++;            printFlag();                    }        int loop=0;        for(int j=0;j&8;j++)        {            if(1 == getFlag(x,j,y))            {                loop++;                trial(j,y+1);            }        }        //if(5 == loop){count++;        printFlag();}        //for(int i=0;i&8;i++) flag[i]=0;            }    int getFlag(int x, int j, int y)    {        for(int i=0;i&=y;i++)        {            if(j == flag[i]||(j == flag[i]+(y+1-i))||(j == flag[i]-(y+1-i)))            return 0;//false        }        return 1;    }    void getCount()    {        cout&&&count=&&&count&&    }private:            int flag[8];};int main(){    cout&&&testCase12=================================&&&    Q    int i=0;    for(i=0;i&8;i++)    a.trial(i,0);    a.getCount();    return 0;}
请登录后再发表评论!
八皇后问题是一个古老而著名的问题，是回溯算法的典型例题。该问题是十九世纪著名的数学家高斯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 * void try(int i) { 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, 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 进制数表示棋盘上皇后的位置： * 比如： 表示： * 第0列皇后在第4个位置 * 第1列皇后在第5个位置 * 第2列皇后在第6个位置 * 。。。 * 第7列皇后在第3个位置 * * 循环变量从
（8进制数）的过程，就遍历了皇后所有的情况 * 程序中用八进制数用一个一维数组 data[] 表示 * * 检测冲突： * 横列冲突：data == data[j] * 斜列冲突：(data+i) == (data[j]+j) 或者 (data-i) == (data[j]-j) * * 好处： * 采用循环，而不是递规，系统资源占有少 * 可计算 n 皇后问题 * 把问题线性化处理，可以把问题分块，在分布式环境下用多台计算机一起算。 * * ToDo： * 枚举部分还可以进行优化，多加些判断条件速度可以更快。 * 输出部分可以修改成棋盘形式的输出 * * @author cinc * */ public class Queen { int resultC public void compute ( int size ) { this.size = resultCount = 0; int data[] = new int[size]; // 所有可能的情况个数 int i,j; // 计算所有可能的情况的个数 count = 1; for ( i=0 ; i& i++ ) { count = count * } // 对每一个可能的情况 for ( i=0 ; i& i++ ) { // 计算这种情况下的棋盘上皇后的摆放位置，用 8 进制数表示 // 此处可优化 int temp = for ( j=0 ; j& j++ ) { data [j] = temp % temp = temp / } // 测试这种情况是否可行，如果可以，输出 if ( test(data) ) output( data ); } } /* * 测试这种情况皇后的排列是否可行 * */ public boolean test( int[] data ) { int i,j; for ( i=0 ; i& i++ ) { for ( j=i+1 ; j& j++ ) { // 测试是否在同一排 if ( data == data[j] ) // 测试是否在一斜线 if ( (data+i) == (data[j]+j) ) // 测试是否在一反斜线 if ( (data-i) == (data[j]-j) ) } } } /* * 输出某种情况下皇后的坐标 * */ public void output ( int[] data ) { System.out.print ( ++resultCount + &: & ); for ( i=0 ; i& 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&QueenMi++)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&QueenMi++) qsave= //下面先把安全位数组完成 i=0;//i 是现在要检查的数组值 while (i&num){ qsave[chess]= int k=num-i; if ( (chess+k &= 0) && (chess+k & QueenMax) ) qsave[chess+k]= if ( (chess-k &= 0) && (chess-k & QueenMax) ) qsave[chess-k]= i++; } //下面历遍安全位 for(i=0;i&QueenMi++){ if (qsave==false) 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&QueenMi++){ String row=&第&+(i+1)+&行: &; if (chess==0); else for(int j=0;j&j++) row+=&--&; row+=&++&; int j = 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&QueenMi++)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&QueenMi++) qsave= //下面先把安全位数组完成 i=0;//i 是现在要检查的数组值 while (i&num){ qsave[chess]= int k=num-i; if ( (chess+k &= 0) && (chess+k & QueenMax) ) qsave[chess+k]= if ( (chess-k &= 0) && (chess-k & QueenMax) ) qsave[chess-k]= i++; } //下面历遍安全位 for(i=0;i&QueenMi++){ if (qsave==false) 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&QueenMi++){ String row=&第&+(i+1)+&行: &; if (chess==0); else for(int j=0;j&j++) row+=&--&; row+=&++&; int j = while(j&QueenMax-1){row+=&--&;j++;} System.out.println(row); } } } //历遍完成就停止 } }[编辑本段]六、c＃实现 采用的思路大致是这样： 将一个皇后向下移动一个位置； 如果没有成功移动（超出边界），失败； 如果成功移动，则判断当前位置是否可用？如果不可用，则重做 1； 继续给下一个皇后安排位置。 结束条件： 如果第一个皇后的所有位置都尝试完毕仍然没有可用的解决方案或者最后一个皇后已经安排完毕。 代码如下： 1// AppEntry.cs 2using S 3 4namespace Chenglin 5{ 6 class AppEntry 7 { 8 static void Main(string[] args) 9 { 10 int queenNumber = 8; 11 QueenRowCollection q = new QueenRowCollection(queenNumber); 12 13 14 DateTime timeStarted = DateTime.N 15 flag = q.PositionQueens(); 16 TimeSpan ts = DateTime.Now.Subtract( timeStarted ); 17 18 19 if( flag ) { 20 Console.WriteLine( q.ToString() ); 21 } 22 else { 23 Console.WriteLine( &Failed& ); 24 } 25 26 Console.WriteLine( & seconds has been elapsed.&, ts.TotalSeconds ); 27 } 28 } 29} 1// QueenRowCollection.cs 2using S 3using System.T 4 5namespace Chenglin 6{ 7 public class QueenRowCollection 8 { 9 10 public QueenRowCollection( int numberOfQueens ){ 11 this.numberOfQueens = numberOfQ 12 this.rows = new QueenRow[ numberOfQueens ]; 13 14 for( int i=0;i&numberOfQi++ ){ 15 rows = new QueenRow( numberOfQueens ); 16 } 17 } 18 19 public bool PositionQueens() 20 { 21 return PositionQueen( 0 ); 22 } 23 24 private bool PositionQueen( int row ) 25 { 26 if( row&=this.numberOfQueens ) { 27 28 } 29 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 46 } 47 } 48 } 49 50 // No position is available for the current queen, 51 // 52 53 } 54 55 private bool PositionAvailable( int row, int column ){ 56 for( int i=row-1; i&=0; i-- ) 57 { 58 if( rows.PositionOccupied( column ) ) 59 60 61 if( rows.PositionOccupied( column-(i-row) ) ) 62 63 64 if( rows.PositionOccupied( column+(i-row) ) ) 65 66 } 67 68 69 } 70 71 public override string ToString() 72 { 73 StringBuilder s = new StringBuilder(); 74 75 foreach( QueenRow q in rows ){ 76 s.AppendFormat( &&, q, Environment.NewLine ); 77 } 78 79 return s.ToString(); 80 } 81 82 private int numberOfQ 83 private QueenRow [] 84 } 85} 1// QueenRow.cs 2using S 3using System.T 4 5namespace Chenglin 6{ 7 public class QueenRow 8 { 9 public QueenRow( int numberOfPositions ) 10 { 11 this.numberOfPositions = numberOfP 12 this.currentPosition = -1; 13 this.columns = new bool[ numberOfPositions ]; 14 } 15 16 public bool MoveNext(){ 17 if( currentPosition&=0 && currentPosition&this.numberOfPositions ){ 18 columns[currentPosition] = 19 } 20 21 if( currentPosition&this.numberOfPositions-1){ 22 currentPosition ++; 23 columns[currentPosition] = 24 25 } 26 else { 27 currentPosition = -1; 28 29 } 30 } 31 32 public bool PositionOccupied( int column ){ 33 if( column&0 || column&=numberOfPositions ){ 34 35 } 36 37 return columns[column]; 38 } 39 40 public override string ToString() 41 { 42 StringBuilder s = new StringBuilder(); 43 44 foreach( bool b in columns ){ 45 s.AppendFormat( & &, (b ? &*& : &-&) ); 46 } 47 48 return s.ToString(); 49 } 50 51 public int CurrentPosition 52 { 53 get { return currentP } 54 } 55 56 private int currentP 57 private int numberOfP 58 private bool [] 59 } 60} 程序运行的时候，当皇后个数增加的时候，运行的时间也会急剧增加！下面这副图表示了皇后个数与运行时间的大致关系： 用PASCAL 解决八皇后问题 program JamesB var x:array[1..8] c,i,d,z: function panduan( a,b:integer): var i: begin panduan:= for i:=a to b-1 do if (x=x) or (abs(i-b)=abs(x-x)) then panduan:= begin z:=0; for i:=1 to 8 do x:=1; c:=2; x[1]:=1; while c&9 do begin if x[c]&=8 then if panduan(1,c) then c:=c+1 else if x[c]&8 then x[c]:=x[c]+1 else begin if (c=2) and (x[1]=8) x[c]:=1; c:=c-1; x[c]:=x[c]+1; end else begin x[c]:=1; c:=c-1; x[c]:=x[c]+1; if c=9 then begin z:=z+1; for i:=1 to 8 do write(x); x[c-1]:=1; c:=c-2; x[c]:=x[c]+1; writeln(z); end. var a:array [1..8] b,c,d:array [-7..16] t,i,j,k: begin t:=t+1; write(t,' '); for k:=1 to 8 do write(a[k],' '); procedure try(i:integer); var j: begin for j:=1 to 8 do {每个皇后都有8种可能位置} if (b[j]=0) and (c=0) and (d=0) then {判断位置是否冲突} begin a:=j; {摆放皇后} b[j]:=1; {宣布占领第J行} c:=1; {占领两个对角线} d:=1; if i&8 then try(i+1) {8个皇后没有摆完，递归摆放下一皇后} {完成任务，打印结果} b[j]:=0; {回溯} c:=0; d:=0; begin for k:=-7 to 16 do {数据初始化} begin b[k]:=0; c[k]:=0; d[k]:=0; try(1);{从第1个皇后开始放置} end. var x:array[1..8] y:array[1..8,1..8] a,b,c:array[-7..16] i,count: {输出棋盘} var k,j: begin for k:=1 to 8 do begin for j:=1 to 8 do y[k,j]:= for k:=1 to 8 do y[k,x[k]]:= for k:=1 to 8 do begin for j:=1 to 8 do if y[k,j] then write('Q ') else write('_ '); procedure try(i:integer); var j: begin for j:=1 to 8 do if a[j] and b and c then begin x:=j; a[j]:= b:= c:= if i&8 then try(i+1){试下一个皇后位置} inc(count); a[j]:={还原} b:= c:= begin for i:=-7 to 16 do begin a:= b:= c:= count:=0; try(1); writeln(count); end.
请登录后再发表评论!
有特殊权利的
请登录后再发表评论!
八皇后问题：国际象棋中，皇后是可以横走，直走，斜走最强大的棋子。在一个8乘8的棋盘上，如何放置最多数量的皇后，使这些皇后互相不吃。答案中的数字很简单，因为每行每列最多只能一个皇后，所以最多只能8个皇后出现在一个64格棋盘上。但是如何放这些皇后让她们互相不吃，就有点头疼了。 背后的小故事： 1995年我第一次在数学读物上看到这个八皇后问题，同时也知道如何手动的使用穷举法去做这个题目，但是没有想过用计算机去解决它。1997年来新加坡后，有天我的Roommate，来自清华的一个朋友，在自学离散数学。。。。。。。。。。
请登录后再发表评论!
八皇后问题是一个古老而著名的问题，是回溯算法的典型例题。该问题是十九世纪著名的数学家高斯1850年提出：在8X8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。 高斯认为有76种方案。1854年在柏林的象棋杂志上不同的作者发表了40种不同的解，后来有人用图论的方法解出92种结果。 一 回溯算法的实现 1. 一般算法 (1) 头文件：eigqueprob.h #include&stdio.h& #define N 8 /* N 表示皇后的个数 */ /* 用来定义答案的结构体 */ typedef struct { /* 答案的行号 */ /* 答案的列号 */ }ANSWER_TYPE; /* 用来定义某个位置是否被占用 */ typedef enum { notoccued = 0, /* 没被占用 */ occued = 1 /* 被占用 */ }IFOCCUED; /* 该列是否已经有其他皇后占用 */ IFOCCUED rowoccu[N]; /* 左上-右下对角位置已经有其他皇后占用 */ IFOCCUED LeftTop_RightDown[2*N-1]; /* 右上-左下对角位置已经有其他皇后占用*/ IFOCCUED RightTop_LefttDown[2*N-1]; /* 最后的答案记录 */ ANSWER_TYPE answer[N]; (2)主程序文件 #include &eigqueprob.h& /* 寻找下一行占用的位置 */ void nextline(int LineIndex) { static asnnum = 0; /* 统计答案的个数 */ int RowIndex = 0; /* 列索引 */ int PrintIndex = 0; /* 按列开始遍历 */ for (RowIndex=0;RowIndex&N;RowIndex++) { /* 如果列和两个对角线上都没有被占用的话，则占用该位置 */ if ( ( notoccued == rowoccu[RowIndex] )\ &&( notoccued == LeftTop_RightDown[LineIndex-RowIndex+N-1] )\ &&( notoccued == RightTop_LefttDown[LineIndex+RowIndex] ) ) { /* 标记已占用 */ rowoccu[RowIndex] = LeftTop_RightDown[LineIndex-RowIndex+N-1] = RightTop_LefttDown[LineIndex+RowIndex] = /* 标记被占用的行、列号 */ answer[LineIndex].line = LineI answer[LineIndex].row = RowI /* 如果不是最后一行，继续找下一行可以占用的位置 */ if ( (N-1) & LineIndex ) { nextline(LineIndex+1); } /* 如果已经到了最后一行，输出结果 */ else { asnnum++; printf(&\nThe %dth answer is :&,asnnum); for (PrintIndex=0;PrintIndex&N;PrintIndex++) { printf(&(%d,%d) &,answer[PrintIndex].line+1,answer[PrintIndex].row+1); } /* 每10个答案一组，与其他组隔两行 */ if ((asnnum % 10) == 0) printf(&\n\n&); } /* 清空占用标志，寻找下一组解 */ rowoccu[RowIndex] = LeftTop_RightDown[LineIndex-RowIndex+N-1] = RightTop_LefttDown[LineIndex+RowIndex] = } } } main() { int i = 0; /* 调用求解函数*/ nextline(i); /* 保持屏幕结果*/ getchar(); } 2. 带图形显示的实现 对于八皇后问题的实现，如果结合动态的图形演示，则可以使算法的描述更形象、更生动，使教学能产生良好的效果。下面是用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++) /*第j个皇后在第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 * void try(int i) { 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, 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 进制数表示棋盘上皇后的位置： * 比如： 表示： * 第0列皇后在第4个位置 * 第1列皇后在第5个位置 * 第2列皇后在第6个位置 * 。。。 * 第7列皇后在第3个位置 * * 循环变量从
（8进制数）的过程，就遍历了皇后所有的情况 * 程序中用八进制数用一个一维数组 data[] 表示 * * 检测冲突： * 横列冲突：data == data[j] * 斜列冲突：(data+i) == (data[j]+j) 或者 (data-i) == (data[j]-j) * * 好处： * 采用循环，而不是递规，系统资源占有少 * 可计算 n 皇后问题 * 把问题线性化处理，可以把问题分块，在分布式环境下用多台计算机一起算。 * * ToDo： * 枚举部分还可以进行优化，多加些判断条件速度可以更快。 * 输出部分可以修改成棋盘形式的输出 * * @author cinc * */ public class Queen { int resultC public void compute ( int size ) { this.size = resultCount = 0; int data[] = new int[size]; // 所有可能的情况个数 int i,j; // 计算所有可能的情况的个数 count = 1; for ( i=0 ; i& i++ ) { count = count * } // 对每一个可能的情况 for ( i=0 ; i& i++ ) { // 计算这种情况下的棋盘上皇后的摆放位置，用 8 进制数表示 // 此处可优化 int temp = for ( j=0 ; j& j++ ) { data [j] = temp % temp = temp / } // 测试这种情况是否可行，如果可以，输出 if ( test(data) ) output( data ); } } /* * 测试这种情况皇后的排列是否可行 * */ public boolean test( int[] data ) { int i,j; for ( i=0 ; i& i++ ) { for ( j=i+1 ; j& j++ ) { // 测试是否在同一排 if ( data == data[j] ) // 测试是否在一斜线 if ( (data+i) == (data[j]+j) ) // 测试是否在一反斜线 if ( (data-i) == (data[j]-j) ) } } } /* * 输出某种情况下皇后的坐标 * */ public void output ( int[] data ) { System.out.print ( ++resultCount + &: & ); for ( i=0 ; i& 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&QueenMi++)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&QueenMi++) qsave= //下面先把安全位数组完成 i=0;//i 是现在要检查的数组值 while (i&num){ qsave[chess]= int k=num-i; if ( (chess+k &= 0) && (chess+k & QueenMax) ) qsave[chess+k]= if ( (chess-k &= 0) && (chess-k & QueenMax) ) qsave[chess-k]= i++; } //下面历遍安全位 for(i=0;i&QueenMi++){ if (qsave==false) 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&QueenMi++){ String row=&第&+(i+1)+&行: &; if (chess==0); else for(int j=0;j&j++) row+=&--&; row+=&++&; int j = 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&QueenMi++)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&QueenMi++) qsave= //下面先把安全位数组完成 i=0;//i 是现在要检查的数组值 while (i&num){ qsave[chess]= int k=num-i; if ( (chess+k &= 0) && (chess+k & QueenMax) ) qsave[chess+k]= if ( (chess-k &= 0) && (chess-k & QueenMax) ) qsave[chess-k]= i++; } //下面历遍安全位 for(i=0;i&QueenMi++){ if (qsave==false) 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&QueenMi++){ String row=&第&+(i+1)+&行: &; if (chess==0); else for(int j=0;j&j++) row+=&--&; row+=&++&; int j = while(j&QueenMax-1){row+=&--&;j++;} System.out.println(row); } } } //历遍完成就停止 } }[编辑本段]六、c＃实现 采用的思路大致是这样： 将一个皇后向下移动一个位置； 如果没有成功移动（超出边界），失败； 如果成功移动，则判断当前位置是否可用？如果不可用，则重做 1； 继续给下一个皇后安排位置。 结束条件： 如果第一个皇后的所有位置都尝试完毕仍然没有可用的解决方案或者最后一个皇后已经安排完毕。 代码如下： 1// AppEntry.cs 2using S 3 4namespace Chenglin 5{ 6 class AppEntry 7 { 8 static void Main(string[] args) 9 { 10 int queenNumber = 8; 11 QueenRowCollection q = new QueenRowCollection(queenNumber); 12 13 14 DateTime timeStarted = DateTime.N 15 flag = q.PositionQueens(); 16 TimeSpan ts = DateTime.Now.Subtract( timeStarted ); 17 18 19 if( flag ) { 20 Console.WriteLine( q.ToString() ); 21 } 22 else { 23 Console.WriteLine( &Failed& ); 24 } 25 26 Console.WriteLine( & seconds has been elapsed.&, ts.TotalSeconds ); 27 } 28 } 29} 1// QueenRowCollection.cs 2using S 3using System.T 4 5namespace Chenglin 6{ 7 public class QueenRowCollection 8 { 9 10 public QueenRowCollection( int numberOfQueens ){ 11 this.numberOfQueens = numberOfQ 12 this.rows = new QueenRow[ numberOfQueens ]; 13 14 for( int i=0;i&numberOfQi++ ){ 15 rows = new QueenRow( numberOfQueens ); 16 } 17 } 18 19 public bool PositionQueens() 20 { 21 return PositionQueen( 0 ); 22 } 23 24 private bool PositionQueen( int row ) 25 { 26 if( row&=this.numberOfQueens ) { 27 28 } 29 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 46 } 47 } 48 } 49 50 // No position is available for the current queen, 51 // 52 53 } 54 55 private bool PositionAvailable( int row, int column ){ 56 for( int i=row-1; i&=0; i-- ) 57 { 58 if( rows.PositionOccupied( column ) ) 59 60 61 if( rows.PositionOccupied( column-(i-row) ) ) 62 63 64 if( rows.PositionOccupied( column+(i-row) ) ) 65 66 } 67 68 69 } 70 71 public override string ToString() 72 { 73 StringBuilder s = new StringBuilder(); 74 75 foreach( QueenRow q in rows ){ 76 s.AppendFormat( &&, q, Environment.NewLine ); 77 } 78 79 return s.ToString(); 80 } 81 82 private int numberOfQ 83 private QueenRow [] 84 } 85} 1// QueenRow.cs 2using S 3using System.T 4 5namespace Chenglin 6{ 7 public class QueenRow 8 { 9 public QueenRow( int numberOfPositions ) 10 { 11 this.numberOfPositions = numberOfP 12 this.currentPosition = -1; 13 this.columns = new bool[ numberOfPositions ]; 14 } 15 16 public bool MoveNext(){ 17 if( currentPosition&=0 && currentPosition&this.numberOfPositions ){ 18 columns[currentPosition] = 19 } 20 21 if( currentPosition&this.numberOfPositions-1){ 22 currentPosition ++; 23 columns[currentPosition] = 24 25 } 26 else { 27 currentPosition = -1; 28 29 } 30 } 31 32 public bool PositionOccupied( int column ){ 33 if( column&0 || column&=numberOfPositions ){ 34 35 } 36 37 return columns[column]; 38 } 39 40 public override string ToString() 41 { 42 StringBuilder s = new StringBuilder(); 43 44 foreach( bool b in columns ){ 45 s.AppendFormat( & &, (b ? &*& : &-&) ); 46 } 47 48 return s.ToString(); 49 } 50 51 public int CurrentPosition 52 { 53 get { return currentP } 54 } 55 56 private int currentP 57 private int numberOfP 58 private bool [] 59 } 60} 程序运行的时候，当皇后个数增加的时候，运行的时间也会急剧增加！下面这副图表示了皇后个数与运行时间的大致关系： 用PASCAL 解决八皇后问题 program JamesB var x:array[1..8] c,i,d,z: function panduan( a,b:integer): var i: begin panduan:= for i:=a to b-1 do if (x=x) or (abs(i-b)=abs(x-x)) then panduan:= begin z:=0; for i:=1 to 8 do x:=1; c:=2; x[1]:=1; while c&9 do begin if x[c]&=8 then if panduan(1,c) then c:=c+1 else if x[c]&8 then x[c]:=x[c]+1 else begin if (c=2) and (x[1]=8) x[c]:=1; c:=c-1; x[c]:=x[c]+1; end else begin x[c]:=1; c:=c-1; x[c]:=x[c]+1; if c=9 then begin z:=z+1; for i:=1 to 8 do write(x); x[c-1]:=1; c:=c-2; x[c]:=x[c]+1; writeln(z); end. var a:array [1..8] b,c,d:array [-7..16] t,i,j,k: begin t:=t+1; write(t,' '); for k:=1 to 8 do write(a[k],' '); procedure try(i:integer); var j: begin for j:=1 to 8 do {每个皇后都有8种可能位置} if (b[j]=0) and (c=0) and (d=0) then {判断位置是否冲突} begin a:=j; {摆放皇后} b[j]:=1; {宣布占领第J行} c:=1; {占领两个对角线} d:=1; if i&8 then try(i+1) {8个皇后没有摆完，递归摆放下一皇后} {完成任务，打印结果} b[j]:=0; {回溯} c:=0; d:=0; begin for k:=-7 to 16 do {数据初始化} begin b[k]:=0; c[k]:=0; d[k]:=0; try(1);{从第1个皇后开始放置} end. var x:array[1..8] y:array[1..8,1..8] a,b,c:array[-7..16] i,count: {输出棋盘} var k,j: begin for k:=1 to 8 do begin for j:=1 to 8 do y[k,j]:= for k:=1 to 8 do y[k,x[k]]:= for k:=1 to 8 do begin for j:=1 to 8 do if y[k,j] then write('Q ') else write('_ '); procedure try(i:integer); var j: begin for j:=1 to 8 do if a[j] and b and c then begin x:=j; a[j]:= b:= c:= if i&8 then try(i+1){试下一个皇后位置} inc(count); a[j]:={还原} b:= c:= begin for i:=-7 to 16 do begin a:= b:= c:= count:=0; try(1); writeln(count); end.
请登录后再发表评论!
