八皇后问题，是一个古老而著名的问题，是回溯算法的典型例题。该问题是十九世纪著名的数学家高斯1850年提出：在8X8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。 高斯认为有76种方案。1854年在柏林的象棋杂志上不同的作者发表了40种不同的解，后来有人用图论的方法解出92种结果。计算机发明后，有多种方法可以解决此问题。

一般算法(用C语言解8皇后问题 代码 注 八皇后问题有92种解法。)

Erlang代码

C代码的一个例子((1) 头文件 (2)主程序文件)

易语言

C代码的另一个例子

IOCCC的一个实现

循环实现 Java(* 数据表示 * 好处 * ToDo)

Qbasic版的解决方案

高效解法-递归版

c#非递归实现(思路 结束条件 代码)

C# 递归实现(思路： 堆栈修改： 代码：)

C++实现

Python实现

PASCAL实现

SHELL实现

独立解

VB实现?

一般算法

用C语言解8皇后问题

“残卷法”思想

设置一个三维数组，第一个下标是皇后的行坐标，第二个下标是皇后的列坐标，第三个下标是残卷号。相当于有N张叠在一起的8*8棋盘，每张棋盘只在复制前面棋盘及皇后后加放置一个皇后。直到放满8皇后后才是一张完整的8皇后图，称完卷。

这里实际操作时多加一行多加一列即第0行第0列，但这一行/列不作输出，只是作此行/列有无皇后的参考。

代码

#include "stdio.h"

void main()

{static int a[9][10][1645],x,y,i,j,z=1,k,flag,h,m,n=0;

for(k=1;k<=z;k++)

{for(x=1;x<=8;x++)

{if(x==8 && m==0) {flag=z+1;m=1;}//残卷算到了第8行，表明已经是完卷。即完卷从l号残卷开始的。

if(a[x][0][k]==2) continue;//参考行等于2则表明此行己有皇后，下一行

for(y=1;y<=8;y++)

{if(a[0][y][k]==2) continue;//参考列等于2则表明此列己有皇后，下一列

if(x>1) if(a[x-1][y-1][k]==1||a[x-1][y+1][k]==1) continue;//左右对角线有皇后，下一列

if(x>2) if(a[x-2][y-2][k]==1||a[x-2][y+2][k]==1) continue;

if(x>3) if(a[x-3][y-3][k]==1||a[x-3][y+3][k]==1) continue;

if(x>4) if(a[x-4][y-4][k]==1||a[x-4][y+4][k]==1) continue;

if(x>5) if(a[x-5][y-5][k]==1||a[x-5][y+5][k]==1) continue;

if(x>6) if(a[x-6][y-6][k]==1||a[x-6][y+6][k]==1) continue;

if(x>7) if(a[x-7][y-7][k]==1||a[x-7][y+7][k]==1) continue;

for(i=0;i<9;i++)

for(j=0;j<9;j++)

a[i][j][z+1]=a[i][j][k];//复制当前残卷内容

a[x][y][z+1]=1;//放置一个皇后到新残卷

a[0][y][z+1]=2;//设置参考列为2，表明此列有皇后

a[x][0][z+1]=2;//设置参考行为2，表明此行有皇后

z++;//取下一个残卷号

}

break;　}

for(k=flag;k<=z;k++)

{//输出8皇后

for(i=1;i<=8;i++)

{for(j=1;j<=8;j++)

printf("%d ",a[i][j][k]);

printf(" ");

for(j=1;j<=8;j++)

printf("%d ",a[9-j][i][k]);//将上图顺时针旋转90度得到新图

printf(" ");

for(j=1;j<=8;j++)

printf("%d ",a[9-i][9-j][k]);//将上图顺时针旋转90度得到新图

printf(" ");

for(j=1;j<=8;j++)

printf("%d ",a[j][9-i][k]);//将上图顺时针旋转90度得到新图

printf(" ");

printf("\");

}

printf("\");

n++;if(n%4==0) getchar();

}

printf("总共%d种 Hyber-bin制作",n*4);//输出总共有多少种

}

注 八皇后问题有92种解法。

我是深搜的，有一点值得注意，显然，八皇后问题每行必须有一个皇后，所以，对棋盘深搜时，第一个皇后的位置不妨设为第一行，这样只对第一行进行搜索，同理，第二个皇后不妨设为第二行，以此类推。这就是我下面代码中深搜只有一个for循环的原因，不这么思考，总会有不小心多次输出同一结果的情形。

下面附我的代码：

#include<iostream>

using namespace std;

struct node1

{bool b[8][8];　};//棋盘模拟，不可以放皇后的地方值为0，可以为1；

struct node2

{　int x,y;};//记录放皇后的位置坐标

//node1 a[9];

node1 visited[9];

node2 zb[8];

int num;//记录有多少中方法

void print()//输出用的函数，坐标从0开始，到7/。

{printf("case%d: ",++num);　for(int i=0;i<=7;i++)

{printf("%d,%d\\t",zb[i].x,zb[i].y);　}

cout<<'\';

}

int x1,x2,x3,x4,y1,y2,y3,y4;

void vis(int x,int y,int step)//模拟记录在第step步时，把皇后放在x,y位置后，哪些地方就不能放皇后了。

{

x1=x;y1=y;

x2=x;y2=y;

x3=x;y3=y;

x4=x;y4=y;

visited[step]=visited[step-1];

for(int i=0;i<8;i++)

{

visited[step].b[x][i]=0;

visited[step].b[i][y]=0;

}

while(x1<8&&y1<8)

{

visited[step].b[x1][y1]=0;

x1++;y1++;

}

while(x4<8&&y4>=0)

{

visited[step].b[x4][y4]=0;

x4++;y4--;

}

}

void DFS(int step)

{

if(step==9)//step=9时，说明已经放了八个皇后了，该是输出的时候了。

print();

else

{

for(int j=0;j<8;j++)

if(visited[step-1].b[step-1][j])

{

zb[step-1].x=step-1;

zb[step-1].y=j;

vis(step-1,j,step);

DFS(step+1);

}

}

}

int main()

{

num=0;

memset(visited,1,sizeof(visited));

DFS(1);

//cout<<"hello world"<<endl;

system("pause");

}

Erlang代码

-module(queen).

-export([printf/0, attack_range/2]).

-define(MaxQueen, 4).

%寻找字符串所有可能的排列

%perms([]) ->

% [[]];

%perms(L) ->

% [[H | T] || H <- L, T <- perms(L -- [H])].

perms([]) ->

[[]];

perms(L) ->

[[H | T] || H <- L, T <- perms(L -- [H]), attack_range(H,T) == []].

printf() ->

L = lists:seq(1, ?MaxQueen),

io:format("~p~n", [?MaxQueen]),

perms(L).

%检测出第一行的数字攻击到之后各行哪些数字

%left向下行的左侧检测

%right向下行的右侧检测

attack_range(Queen, List) ->

attack_range(Queen, left, List) ++ attack_range(Queen, right, List).

attack_range(_, _, []) ->

[];

attack_range(Queen, left, [H | _]) when Queen - 1 =:= H ->

[H];

attack_range(Queen, right, [H | _]) when Queen + 1 =:= H ->

[H];

attack_range(Queen, left, [_ | T]) ->

attack_range(Queen - 1, left, T);

attack_range(Queen, right, [_ | T]) ->

attack_range(Queen + 1, right, T).

C代码的一个例子

(1) 头文件

eigqueprob.h

#include

#define N 8 /* N 表示皇后的个数 */

/* 用来定义答案的结构体 */

typedef struct

{

int line; /* 答案的行号 */

int row; /* 答案的列号 */

}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　{

/* 如果列和两个对角线上都没有被占用的话，则占用该位置 */

if ( ( notoccued == rowoccu[RowIndex] )\\

&&( notoccued == LeftTop_RightDown[LineIndex-RowIndex+N-1] )\\

&&( notoccued == RightTop_LefttDown[LineIndex+RowIndex] ) )

{

/* 标记已占用 */

rowoccu[RowIndex] = occued;

LeftTop_RightDown[LineIndex-RowIndex+N-1] = occued;

RightTop_LefttDown[LineIndex+RowIndex] = occued;

/* 标记被占用的行、列号 */

answer[LineIndex].line = LineIndex;

answer[LineIndex].row = RowIndex;

/* 如果不是最后一行，继续找下一行可以占用的位置 */

if ( (N-1) > LineIndex )

{

nextline(LineIndex+1);

}

/* 如果已经到了最后一行，输出结果 */

else

{

asnnum++;

printf("\The %dth answer is :",asnnum);

for (PrintIndex=0;PrintIndex　{

printf("(%d,%d) ",answer[PrintIndex].line+1,answer[PrintIndex].row+1);

}

/* 每10个答案一组，与其他组隔两行 */

if ((asnnum % 10) == 0)

printf("\\");

}

/* 清空占用标志，寻找下一组解 */

rowoccu[RowIndex] = notoccued;

LeftTop_RightDown[LineIndex-RowIndex+N-1] = notoccued;

RightTop_LefttDown[LineIndex+RowIndex] = notoccued;

}

}

}

main()

{

int i = 0;

/* 调用求解函数*/

nextline(i);

/* 保持屏幕结果*/

getchar();

}

带图形显示的实现

对于八皇后问题的实现，如果结合动态的图形演示，则可以使算法的描述更形象、更生动，使教学能产生良好的效果。下面是用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++) /*第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

#include

#include

#include

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

}

易语言

.版本 2

.支持库 iext3

.支持库 iext

.程序集 启动窗口程序集

.程序集变量 皇后位置数组, 整数型, , "0", 如：皇后位置数组[j]=4，表示第j列，第皇后位置数组[j]行有皇后

.程序集变量 行数组, 整数型, , "0", 行数组[k]=1,表示第k行没有皇后

.程序集变量 右高左低数组, 整数型, , "0", 右高左低数组[k]=1,表示第k条右高左低的斜线上没有皇后

.程序集变量 左高右低数组, 整数型, , "0", 左高右低数组[k]=1,表示第k条左高右低的斜线上没有皇后

.程序集变量 棋盘行列值, 整数型, , , 棋盘规模变量

.子程序 __启动窗口_创建完毕

' 使用算法：递归法

' 问题：N后问题

' 问题描述：

' 国际象棋中皇后可以攻击所在行，列，斜线上的每一个位置，按照此规则要在一个n*n的棋盘上放n个皇后使每一个皇后都不互相攻击

' 问题分析：

' （1） 引入1个数组模拟棋盘上皇后的位置

' 皇后位置数组[j]=4，表示第j列，第皇后位置数组[j]行有皇后

' 引入3个工作数组

' 行数组[k]=1,表示第k行没有皇后

' 右高左低数组[k]=1,表示第k条右高左低的斜线上没有皇后

' 左高右低数组[k]=1,表示第k条左高右低的斜线上没有皇后

' 观察棋盘找到规律

' 同一右高左低的斜线上的方格，它们的行号和列号之和相等；

' 同一左高右低的斜线上的方格，它们的行号和列号只差相等；

' 开始时，所有行和斜线上都没有皇后，从第一列的第一行配置第一个皇后开始，在第m列的皇后位置数组[m]行放置了一个合理的皇后之后，准备考察第m+1列时，在数组 行数组[]，右高左低数组[]，左高右低数组[]中为第m列，皇后位置数组[m]的位置设定有皇后标志

' 如果按此放置位置得不到结果，则把当前列中的有皇后标记改为无皇后标记。

' 依次类推

' 当在棋盘最后一列上也找到合适的位置后得到结果。

' 通过上面规律可以推导出结果。

' 备注：

.子程序 __启动窗口_尺寸被改变

问题编辑框.宽度 = 高级选择夹1.宽度 － 16

问题编辑框.高度 = 高级选择夹1.高度 － 43

分析编辑框.宽度 = 问题编辑框.宽度

分析编辑框.高度 = 问题编辑框.高度

分组框1.宽度 = 高级选择夹1.宽度 － 18

分组框1.高度 = 高级选择夹1.高度 － 36

超级列表框1.宽度 = 分组框1.宽度 － 184

超级列表框1.高度 = 分组框1.高度 － 33

.子程序 _计算图形按钮_被单击

.局部变量 局部计次变量, 整数型, , , 在计次循环中记录循环次数

.局部变量 局部计次变量2, 整数型

.局部变量 返回值, 整数型, , , 返回是否放置所有皇后成功

' 清空列表框

.计次循环首 (超级列表框1.取列数 (), )

超级列表框1.删除列 (0)

.计次循环尾 ()

.计次循环首 (超级列表框1.取表项数 (), )

超级列表框1.删除表项 (0)

.计次循环尾 ()

' 获得输入棋盘规模数据

棋盘行列值 = 到数值 (输入编辑框.内容)

.如果真 (棋盘行列值 < 1) ' 棋盘不能为0或负数

输入编辑框.内容 = “4”

返回 ()

.如果真结束

' 如果输入的棋盘规模过大提示是否等待

.如果真 (棋盘行列值 > 28)

.如果真 (信息框 (“您输入的数值过大，处理数据时程序将会有一段时间无响应，是否继续？”, #是否钮 + #询问图标, “请问：”) ≠ #是钮)

' 如果不想等待很长时间则返回

返回 ()

.如果真结束

.如果真结束

' 根据的到值定义棋盘行列，定义相关两斜行的值

重定义数组 (行数组, 假, 棋盘行列值)

重定义数组 (右高左低数组, 假, 2 × 棋盘行列值)

重定义数组 (左高右低数组, 假, 2 × 棋盘行列值)

重定义数组 (皇后位置数组, 假, 棋盘行列值)

' 行数组 [1]=1，表示第1行没有皇后

.计次循环首 (棋盘行列值, 局部计次变量)

行数组 [局部计次变量] = 1

.计次循环尾 ()

' 右高左低数组[1]=1，表示第1条右高左低的斜线上没有皇后

' 左高右低数组[1]=1，表示第1条左高右低的斜线上没有皇后

.计次循环首 (2 × 棋盘行列值, 局部计次变量)

右高左低数组 [局部计次变量] = 1

左高右低数组 [局部计次变量] = 1

.计次循环尾 ()

' 从第一列开始找出合适的放置方法

返回值 = 皇后问题子程序 (1)

.判断开始 (返回值 = 1)

标签2.标题 = “找到结果” ' 得到结果显示在超级列表框中

超级列表框1.插入列 (, “0”, , , , )

超级列表框1.置列宽 (0, 30)

' 画棋盘列

.计次循环首 (棋盘行列值, 局部计次变量)

超级列表框1.插入列 (, 到文本 (局部计次变量), , , , )

超级列表框1.置列宽 (局部计次变量, 30)

.计次循环尾 ()

' 画棋盘行

.计次循环首 (棋盘行列值, 局部计次变量)

超级列表框1.插入表项 (, 到文本 (局部计次变量), , , , )

.计次循环尾 ()

' 显示排列结果

.计次循环首 (棋盘行列值, 局部计次变量)

.计次循环首 (棋盘行列值, 局部计次变量2)

' 如果当前行列坐标上有皇后

.判断开始 (皇后位置数组 [局部计次变量] = 局部计次变量2)

超级列表框1.置标题 (局部计次变量2 － 1, 局部计次变量, “皇”)

.默认

超级列表框1.置标题 (局部计次变量2 － 1, 局部计次变量, “*”)

.判断结束

.计次循环尾 ()

.计次循环尾 ()

.默认

标签2.标题 = “没有合适结果”

.判断结束

.子程序 皇后问题子程序, 整数型, , 在n*n棋盘的第k列上找合理的皇后放置位置

.参数 当前判断列, 整数型, , 当前在试探位置所在的列

.局部变量 局部计次变量, 整数型, , , 试探合理位置时记录当前的行

.局部变量 结果控制变量, 整数型, , , 找到结果变量为1，没有结果变量为0

局部计次变量 = 1

结果控制变量 = 0

.判断循环首 (结果控制变量 = 0 且 局部计次变量 ≤ 棋盘行列值) ' 没有找到合理的解，并且还有没试过的行，继续循环

.如果真 (行数组 [局部计次变量] = 1 且 右高左低数组 [当前判断列 + 局部计次变量] = 1 且 左高右低数组 [棋盘行列值 + 当前判断列 － 局部计次变量] = 1) ' 是否在行，列，两斜线上都没有放置过皇后

皇后位置数组 [当前判断列] = 局部计次变量

' 数组值等于 0，表示已经有皇后

行数组 [局部计次变量] = 0

右高左低数组 [当前判断列 + 局部计次变量] = 0

左高右低数组 [棋盘行列值 + 当前判断列 － 局部计次变量] = 0

.判断开始 (当前判断列 = 棋盘行列值)

返回 (1) ' 如果已经是最后一列，找到解，返回 1

.默认

结果控制变量 = 皇后问题子程序 (当前判断列 + 1) ' 不是最后列，到下一列去放皇后，返回是否能放置皇后的信息

.判断结束

行数组 [局部计次变量] = 1

右高左低数组 [当前判断列 + 局部计次变量] = 1

左高右低数组 [棋盘行列值 + 当前判断列 － 局部计次变量] = 1

.如果真结束

局部计次变量 = 局部计次变量 + 1

.判断循环尾 ()

返回 (结果控制变量) ' 返回最终是否有解的信息

C代码的另一个例子

#include "stdio.h"

#include "windows.h"

#define N 8 /* 定义棋盘大小 */

int place(int k); /* 确定某一位置皇后放置与否，放置则返回1，反之返回0 */

void backtrack(int i);/* 主递归函数，搜索解空间中第i层子树 */

void chessboard(); /* 每找到一个解,打印当前棋盘状态 */

static int sum, /* 当前已找到解的个数 */

x[N]; /* 记录皇后的位置,x[i]表示皇后i放在棋盘的第i行的第x[i]列 */

int main(void)

{

backtrack(0);

system("pause");

return 0;

}

int place(int k)

{

/* 测试皇后k在第k行第x[k]列时是否与前面已放置好的皇后相攻击。 x[j] == */

/* x[k] 时，两皇后在同一列上；abs(k - j) == abs(x[j] - x[k]) 时，两皇 */

/* 后在同一斜线上。两种情况两皇后都可相互攻击，故返回0表示不符合条件。*/

for (int j = 0; j < k; j ++)

if (abs(k - j) == abs(x[j] - x[k]) || (x[j] == x[k])) return 0;

return 1;

}

void backtrack(int t)

{

/* t == N 时，算法搜索至叶结点，得到一个新的N皇后互不攻击的放置方案 */

if (t == N) chessboard();

else

for (int i = 0; i < N; i ++) {

x[t] = i;

if (place(t)) backtrack(t + 1);

}

}

void chessboard()

{

printf("第%d种解法:\", ++ sum);

for (int i = 0; i < N; i ++) {

for (int j = 0; j < N; j ++)

if (j == x[i]) printf("@ ");

else printf("* ");

printf("\");

}

printf("\");

}

IOCCC的一个实现

#include

#define q(o) a[j]o[j+i+7]o[j-i+31]

int a[39];

void main(int i,int j)

{

for(j=9;--j;i>8?printf("%10d ",a[j]):q(|a)||(q(=a)=i,main(i+1,j),q(=a)=0));

}

循环实现 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

* 枚举部分还可以进行优化，多加些判断条件速度可以更快。

* 输出部分可以修改成棋盘形式的输出

*/

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　count = count * size;

}

// 对每一个可能的情况

for ( i=0 ; i　// 计算这种情况下的棋盘上皇后的摆放位置，用 8 进制数表示

// 此处可优化

int temp = i;

for ( j=0 ; 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　for ( j=i+1 ; 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　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　placequeen(0);

System.out.println("\\\八皇后共有"+oktimes+"个解法 made by yifi 2003");

}

public static void placequeen(int num){ //num 为现在要放置的行数

int i=0;

boolean qsave[] = new boolean[QueenMax];

for(;i　//下面先把安全位数组完成

i=0;//i 是现在要检查的数组值

while (i　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　if (qsave==false)continue;

if (num　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　String row="第"+(i+1)+"行: ";

if (chess==0);

else

for(int j=0;j　row+="++";

int j = chess;

while(j　System.out.println(row);

}

}

}

//历遍完成就停止

}

}

c#非递归实现

思路

采用的思路大致是这样：

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

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

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

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

结束条件

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

代码

1// AppEntry.cs

2using System;

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 bool flag;

14 DateTime timeStarted = DateTime.Now;

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 System;

3using System.Text;

4

5namespace Chenglin

6{

7 public class QueenRowCollection

8 {

9

10 public QueenRowCollection( int numberOfQueens ){

11 this.numberOfQueens = numberOfQueens;

12 this.rows = new QueenRow[ numberOfQueens ];

13

14 for( int i=0;i　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 return true;

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 return true;

46 }

47 }

48 }

49

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

51 //

52 return false;

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 return false;

60

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

62 return false;

63

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

65 return false;

66 }

67

68 return true;

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 numberOfQueens;

83 private QueenRow [] rows;

84 }

85} 1// QueenRow.cs

2using System;

3using System.Text;

4

5namespace Chenglin

6{

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 }

15

16 public bool MoveNext(){

17 if( currentPosition>=0 && currentPosition　18 columns[currentPosition] = false;

19 }

20

21 if( currentPosition　22 currentPosition ++;

23 columns[currentPosition] = true;

24 return true;

25 }

26 else {

27 currentPosition = -1;

28 return false;

29 }

30 }

31

32 public bool PositionOccupied( int column ){

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

34 return false;

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 currentPosition; }

54 }

55

56 private int currentPosition;

57 private int numberOfPositions;

58 private bool [] columns;

59 }

60}

C# 递归实现

思路：

按列分别安排皇后(Q)，Q数目可随意指定（由于StackOverFlowException，目前只能到8）。

Q1可以放在任何位置；

然后尝试Q2，因为Q1的限制，Q2必须排除第二列与Q1行数插值大于2的位置；

依次尝试Qm... 如果Qm上没有剩余可用位置，则返回Qm-1，同时使Qm-1 放弃刚才使用位置；

当到达结尾Qn时，成功放置，则存储所有位置，作为一种解法；

当Q1尝试过首列所有位置后，算法结束。

结果统计并罗列所有解法。

堆栈修改：

“editbin /stack:4048000 D:\\aa\\ConsoleApplication2.exe”

代码：

using System;

using System.Collections.Generic;

classMainClass

{

staticvoid Main()

{

int queens = int.Parse(Console.ReadLine());

List<Position> allPositions = GetAllPositions(queens);

int column = 0;

List<List<Position>> solutions = newList<List<Position>>();

EightQueens(queens, allPositions, column, newStack(), solutions);

for (int i = 0; i < solutions.Count; i++)

{

DisplayPositions(solutions[i]);

}

Console.WriteLine(solutions.Count);

Console.Read();

}

#region EightQueens

classStack

{

publicList<Position> CurrentPositions = newList<Position>();

List<KeyValuePair<int, List<Position>>> stack = newList<KeyValuePair<int, List<Position>>>();

publicvoid push(int i, List<Position> p )

{

stack.Add(newKeyValuePair<int, List<Position>>(i, p));

}

publicKeyValuePair<int, List<Position>> pop()

{

KeyValuePair<int, List<Position>> p = stack[stack.Count - 1];

stack.RemoveAt(stack.Count - 1);

return p;

}

publicvoid ClearFromKey(int key)

{

int idx = stack.FindIndex(a=>a.Key == key);

if (idx > -1)

{

stack.RemoveRange(idx, stack.Count - idx);

}

}

publicList<KeyValuePair<int, List<Position>>> StackList

{

get

{

returnthis.stack;

}

}

}

classPosition

{

publicint left;

publicint right;

public Position(int left, int right)

{

this.left = left;

this.right = right;

}

publicint LeftDistence(Position p)

{

returnMath.Abs(this.left - p.left);

}

publicint RightDistence(Position p)

{

returnMath.Abs(this.right - p.right);

}

publicint QueenNumber = -1;

publicbool HasQueen

{

get

{

return QueenNumber != -1;

}

}

}

staticKeyValuePair<bool, int> EightQueens(int queens, List<Position> allPositions, int column, Stack stack, List<List<Position>> solutions)

{

if (column == queens)

{

List<Position> newLst = newList<Position>();

if(solutions.Count > 0)

{

for(int i = 0 ; i < solutions[solutions.Count - 1].Count -1 ; i++)

{

newLst.Add(solutions[solutions.Count - 1][i]);

}

}

solutions.Add(newLst);

return EightQueens(queens, allPositions, column -1, stack, solutions);

}

if (column == 0)

{

stack.ClearFromKey(1);

if (solutions.Count > 0 && solutions[solutions.Count - 1].Count != queens)

{

solutions.RemoveAt(solutions.Count - 1);

}

solutions.Add(newList<Position>());

}

List<Position> results;

if (solutions.Count > 0)

{

results = solutions[solutions.Count - 1];

}

else

{

results = newList<Position>();

}

List<Position> newPositions = newList<Position>();

if (stack.StackList.Exists(a => a.Key == column))

{

newPositions = stack.StackList.Find(a => a.Key == column).Value;

if (newPositions.Count > 0)

{

newPositions.RemoveAt(0);

}

}

else

{

newPositions = allPositions.FindAll(a => a.left == column);

newPositions = FilterPositions(newPositions, results);

stack.push(column, newPositions);

}

if (newPositions.Count > 0)

{

newPositions[0].QueenNumber = column;

results.Add(newPositions[0]);

column = column + 1;

return EightQueens(queens, allPositions, column, stack, solutions);

}

else

{

stack.ClearFromKey(column);

if (stack.StackList.Count > 0 && stack.StackList.Find(a => a.Key == 0).Value.Count > 0)

{

if (results.Count > 0)

{

results.RemoveAt(results.Count - 1);

}

return EightQueens(queens, allPositions, column - 1, stack, solutions);

}

else

{

if (solutions.Count > 0)

{

solutions.RemoveAt(solutions.Count - 1);

}

returnnewKeyValuePair<bool, int>(true, 0);

}

}

}

staticList<Position> GetAllPositions(int queens)

{

List<Position> positions = newList<Position>();

for (int i = 0; i < queens; i++)

{

for (int j = 0; j < queens; j++)

{

positions.Add(newPosition(i, j));

}

}

return positions;

}

staticList<Position> FilterPositions(List<Position> original, Position newPosition)

{

return original.FindAll(a => CheckPosition(a, newPosition));

}

staticList<Position> FilterPositions(List<Position> original, List<Position> newPositions)

{

if (newPositions == null || newPositions.Count == 0)

{

return original;

}

List<Position> ps = newList<Position>();

foreach(Position p in newPositions)

{

original.RemoveAll(a => ! CheckPosition(a, p));

}

foreach (Position p in original)

{

ps.Add(p);

}

return ps;

}

staticBoolean CheckPosition(Position newPosition, Position targetPosition)

{

int left = newPosition.LeftDistence(targetPosition);

int right = newPosition.RightDistence(targetPosition);

if (left < 1 || right < 1 || left == right)

{

returnfalse;

}

returntrue;

}

staticvoid DisplayPositions(List<Position> positions)

{

for (int i = 0; i < positions.Count; i++)

{

Console.Write(positions[i].left);

Console.Write(positions[i].right + ",");

}

Console.WriteLine();

}

#endregion

}

C++实现

这里介绍一个编程复杂度小，思路清晰的代码

#include

using namespace std;

int width=8,lim=(1<　void queen(int col,int ld,int rd) //分别是列,正斜线,反斜线,

{//col的二进制位中的1代表该行不能放的地方,ld,rd同理

if(col==lim){ans++;return;} //递归终止条件:col的二进制位在width（棋盘宽度）内都是1(放满了)

int pos=lim&~(col|ld|rd); //col,ld,rd都是0的位可以放皇后,pos该位置1

while(pos)

{

int t=pos&-pos; //取pos最右边的1位放皇后

pos-=t;

queen(col|t,(ld|t)<<1,(rd|t)>>1); //往棋盘的下一行递归,左斜线的限制往左，右斜线往右，可以画图看看

}

}

int main()

{

queen(0,0,0); //

cout<　return 0;

}

C++另外一种方法：

#include<iostream>

using namespace std;

int a[8]; int b[8]; int c=0;

bool flag(int pos) {

int i;

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

if(a[i]==a[pos]) {return false;}

if(a[i]==a[pos]-(pos-i)||a[i]==a[pos+(pos-i)) {return false;}

}

return true;

}

void start(int pos) {

int i;

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

a[pos]=i; if(flag(pos)) {

if(pos==7) {c++;}

else {start(pos+1);}

}}

return;}

int main() { int i,j;

for(i=0;i<n;i++) a[i]=-1;

start(0);

cout<<c<<"种方法";

system("pause");

return 0;

}

Python实现

from itertools import permutations

n = 8

cols = range(n)

for vec in permutations(cols):

if (n == len(set(vec[i]+i for i in cols))

== len(set(vec[i]-i for i in cols))):

print vec

PASCAL实现

program bahuanghou;

var ans:array[1..8] of integer; //记录答案的数组，记录在第1到第8行皇后所在的列；

lie:array[1..8] of boolean; //记录1到8中某列是否已经被另一个皇后占用；

zx:array[2..16] of boolean; //正斜线（左下向右上）数组，该斜线特点为：斜线上每一格的行加列的和一定，和为从2到16.。故可用2到16来表示这15条正斜线，于是该数组记录了2到16中某条正斜线是否已经被另一个皇后占用；

fx:array[-7..7] of boolean; //反斜线（左上向右下）数组，该斜线特点为：斜线上每一格的行减列的差一定，差为从-7到7。故可用-7到7来表示这15条正斜线，于是该数组记录了2到16中某条正斜线是否已经被另一个皇后占用；

temp:integer; //记录总方案数；

procedure print; //该子程序负责输出方案；

var i:integer;

begin

write('zuobiao');

for i:=1 to 8 do write(' (',i,',',ans[i],')'); //i代表行，ans[i]代表列；

writeln;

end;

procedure search(i:integer); //i为行，即表示放到了第几个皇后（因为一行有且只有1个皇后);

var j:integer

begin

if i=9 then //递归出口，当搜索到第九行时，便得到一种方案；

begin

print; //输出该方案；

inc(temp); //每输出（得到）一种方案，总方案数变加1；

exit; //退出；

end;

for j:=1 to 8 do if not lie[j] and not zx[i+j] and not fx[i-j] then //当前位置，该列，正斜线，反斜线上均未被另一个皇后占用，即可以摆放一个皇后；

begin

lie[j]:=true; //设置标志，该行

zx[i+j]:=true; // 该正斜线

fx[i-j]:=true; // 该反斜线上已被皇后占用，不可再放皇后；

ans[i]:=j; //记录答案（第i行皇后所在列j）；

search(i+1); //实行下一层递归；

lie[j]:=false; //恢复标志（回溯）；

zx[i+j]:=false;

fx[i-j]:=false;

end;

end;

begin //主程序；

temp:=0; //给总方案数设初值为“0”；

fillchar(lie,sizeof(lie),0); //分别给列

fillchar(zx,sizeof(zx),0); // 正斜线

fillchar(fx,sizeof(fx),0); // 反斜线数组设初值为“假”

search(1); //从第一行开始进行搜索；

writeln(temp); //再输出总方案数；

end.

SHELL实现

作者: kkng09 时间: 2003-9-5 17:53

#/bin/bash

canSet() { # 检查是否可放下皇后的子程序.

for ((n=0;n<y;n++)) ;do

((P[$n] == x)) && return 1 # 检查是否同一行, 如果是返回1 false

((P[$n] == x - n + y )) && return 1 #检查斜行.

((P[$n] == x + n - y )) && return 1 #检查另一方向斜行.

done

return 0 # 返回成功.

}

# init

y=0 # y 是行,

for((i=0;i<8;i++)) ;do

P[$i]=-1 # p 是座位array , -1是不在棋盘上.

done

while (((y<8)&&(y>=0)));do #如果y>=8, 即找到结果, 如果y<0, 即找不到结果, 退出回卷

# echo ${P[*]}; # 打开这一注解,可看script 运行过程

f=0 # 设flag = 0, 用它检查否一整能不能放下皇后

s=${P[$y]}+1 # 每一行皇后放下的列位罝+1

for ((x=s;x<8;x++)); do #其他shell 用 for x in seq $s 7

if canSet ;then #如果可放下, 则

P[$y]=$x #记下皇后位罝

((y++)) # 行位罝加1, 如用其他shell, 用 y=`expr $y + 1`代替

f=1 #设flag=1,即可效皇后.

break #处理下一个皇后

fi

done

if [ $f -eq 0 ];then # 如果整行都不能放下皇后.则

P[$y]=-1 #将皇后由棋盘上拿下.

((y--)) #行位罝-1.

fi

done

echo ${P[*]}; 打印数据

独立解

在92个解中，很多解在棋盘上有对称关系，每一个棋子都有8个对称位置，如果一个解和另外一个解所有的棋子都呈同一种对称，那么这两个解之间就是对称关系。例如右边两个解实际上沿着垂直轴翻转，就是一个，因此不是独立的。相互间没有对称关系的解是独立解。虽然一个解可以有8个对称位置，但是有些解经过对称操作后和没有操作前是一样的。

在一个标准的8x8的棋盘中，92个解当中有12个解是独立的。8x8棋盘的独立解如图所示。

如果把棋盘从8X8变成NxN, 八皇后问题就变成了N皇后问题。N从4以上都有解，并分别有相应的独立解。

下面是皇后的数目于解数目的关系

皇后数： 4 5 6 7 8 9 10 11 12 13 14

独立解： 1 2 1 6 12 46 92 341 1787 9233 45752

全部解： 2 10 4 40 92 352 724 2680 14200 73712 365596

皇后数　4　5　6　7　8　9　10　11　12　13　14

独立解　1　2　1　6　12　46　92　341　1787　9233　45752

全部解　2　10　4　40　92　352　724　2680　14200　73712　365596比较特殊的是，皇后6x6棋盘的解比5x5少，其余解的数目随着皇后数目增加。但似乎无数学表达式可以描述。

VB实现?

?'主要利用递推思想 挨个判断是否可放置皇后 若是 继续放置下一个 否则寻找其余位置

'所需控件 一个 list控件 list1

'一个按钮 command1

Dim int1 As Integer

Private Sub command1_click()

List1.Clear

int1 = 0

Dim i As Single, j As Single

i = 1

j = 1

Dim p As Integer, b As Boolean

Dim a(1 To 8, 1 To 8) As Boolean

Dim ii(1 To 8) As Single

Dim jj(1 To 8) As Single

a(i, j) = True

ii(1) = i

jj(1) = j

Do

Do While i < 8

i = i + 1

If i = 0 Then Exit Sub

j = 1

If b = True Then

a(i,jj(i)) = False

b = False

j = jj(i)+ 1

End If

Do

If j > 8 Then i =i - 2: b = True: Exit Do

For p = 1 To i - 1

Ifj = jj(p) Or Abs(i - ii(p)) = Abs(j - jj(p)) Then Exit For

Next

If p = i Then Exit Do

j = j + 1

Loop

If b = False Then

ii(i) = i: jj(i) = j

a(i, j) = True

End If

Loop

Dim p1 As Integer, p2 As Integer, str1 As String

For p1 = 1 To 8

str1 = ""

For p2 = 1 To 8

If a(p1,p2) = False Then

str1= str1 & "+ "

Else: str1= str1 & "@ "

End If

Next

List1.AddItem str1

Next

int1 = int1 + 1

Caption = int1

i = i - 1: b = True

List1.AddItem " "& Str(int1)

List1.AddItem vbCrLf

Loop

End Sub