n皇后算法

㈠ 八皇后问题是什么问题呀

这就是着名的八皇后问题。八个皇后在排列时不能同在一行、一列或一条斜
线上。在8!=40320种排列中共有92种解决方案。

“八皇后”动态图形的实现

八皇后问题是一个古老而着名的问题，是回溯算法的典型例题。该问题是十九世纪着名的数学家高斯1850年提出：在8X8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。
高斯认为有76种方案。1854年在柏林的象棋杂志上不同的作者发表了40种不同的解，后来有人用图论的方法解出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,)将位图置于屏幕上以（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);
}
}
}
//历遍完成就停止

㈡ 用回溯法解定和子集问题、0/1背包问题和n皇后问题的算法比较

我只写了一个n皇后的解法，其它的没写，不知道什么意思。程序如下：
#include <iostream>
using namespace std;
#define MAX 5 //数组维数
static int total=0; //算法总数
int array[MAX][MAX]; //定义数组
void SetArray() //数组置零
{
int i,j;
for(i=0;i<MAX;i++)
for(j=0;j<MAX;j++)
array[i][j]=0;
}
bool IsTrue(int a,int b) //合法性判断
{
int i,j,len;
for (i=0;i<MAX;i++)
if(array[a][i]==1||array[i][b]==1)
return false;
len=(a<b?a:b);
for(i=a-len,j=b-len;i<MAX&&j<MAX;i++,j++)
if(array[i][j]==1)
return false;
for(i=a,j=b;i<MAX&&j>=0;i++,j--)
if(array[i][j]==1)
return false;
for(i=a,j=b;i>=0&&j<MAX;i--,j++)
if(array[i][j]==1)
return false;
return true;
}
void show() //显示结果
{
int i,j;
cout<<"第"<<++total<<"种结果为："<<endl;
for (i=0;i<MAX;i++)
{
for(j=0;j<MAX;j++)
cout<<array[i][j]<<" ";
cout<<endl;
}

}
bool Queen(int i) //皇后算法
{
int j;
for(j=0;j<MAX;j++)
{
if(IsTrue(i,j))
{
array[i][j]=1;
if(i==MAX-1)
{
show();
array[i][j]=0;
continue;
}
else if(!Queen(i+1))
{
array[i][j]=0;
continue;
}
}
}
return false;
}
void main()
{
int i;
for(i=0;i<MAX;i++)
{
SetArray();
array[0][i]=1;
Queen(1);
}
}
不明白的可以来问我。。

㈢ 算法的n 皇后问题是否必然有解，理由是什么 研究好久到处爬文还是搞不太懂QAQ 谢谢！！

N皇后问题是一个经典的问题，在一个N*N的棋盘上放置N个皇后，每行一个并使其不能互相攻击（同一行、同一列、同一斜线上的皇后都会自动攻击）。

一、 求解N皇后问题是算法中回溯法应用的一个经典案例
回溯算法也叫试探法，它是一种系统地搜索问题的解的方法。回溯算法的基本思想是：从一条路往前走，能进则进，不能进则退回来，换一条路再试。
在现实中，有很多问题往往需要我们把其所有可能穷举出来，然后从中找出满足某种要求的可能或最优的情况，从而得到整个问题的解。回溯算法就是解决这种问题的“通用算法”，有“万能算法”之称。N皇后问题在N增大时就是这样一个解空间很大的问题，所以比较适合用这种方法求解。这也是N皇后问题的传统解法，很经典。

下面是算法的高级伪码描述，这里用一个N*N的矩阵来存储棋盘：
1) 算法开始, 清空棋盘，当前行设为第一行，当前列设为第一列
2) 在当前行，当前列的位置上判断是否满足条件(即保证经过这一点的行,列与斜线上都没有两个皇后)，若不满足，跳到第4步
3) 在当前位置上满足条件的情形：
在当前位置放一个皇后，若当前行是最后一行，记录一个解；
若当前行不是最后一行，当前行设为下一行, 当前列设为当前行的第一个待测位置；
若当前行是最后一行，当前列不是最后一列，当前列设为下一列；
若当前行是最后一行，当前列是最后一列，回溯，即清空当前行及以下各行的棋盘，然后，当前行设为上一行，当前列设为当前行的下一个待测位置；
以上返回到第2步
4) 在当前位置上不满足条件的情形：
若当前列不是最后一列，当前列设为下一列，返回到第2步;
若当前列是最后一列了，回溯，即，若当前行已经是第一行了，算法退出，否则，清空当前行及以下各行的棋盘，然后，当前行设为上一行，当前列设为当前行的下一个待测位置，返回到第2步;
算法的基本原理是上面这个样子，但不同的是用的数据结构不同，检查某个位置是否满足条件的方法也不同。为了提高效率，有各种优化策略，如多线程，多分配内存表示棋盘等。
在具体解决该问题时，可以将其拆分为几个小问题。首先就是在棋盘上如何判断两个皇后是否能够相互攻击，在最初接触这个问题时，首先想到的方法就是把棋盘存储为一个二维数组，然后在需要在第i行第j列放置皇后时，根据问题的描述，首先判断是在第i行是否有皇后，由于每行只有一个皇后，这个判断也可以省略，然后判断第j列是否有皇后，这个也很简单，最后需要判断在同一斜线上是否有皇后，按照该方法需要判断两次，正对角线方向和负对角线方向，总体来说也不难。但是写完之后，总感觉很笨，因为在N皇后问题中这个函数的使用次数太多了，而这样做效率较差，个人感觉很不爽。上网查看了别人的实现之后大吃一惊，大牛们都是使用一个一维数组来存储棋盘，在某个位置上是否有皇后可以相互攻击的判断也很简单。具体细节如下：

把棋盘存储为一个N维数组a[N]，数组中第i个元素的值代表第i行的皇后位置，这样便可以把问题的空间规模压缩为一维O(N)，在判断是否冲突时也很简单，首先每行只有一个皇后，且在数组中只占据一个元素的位置，行冲突就不存在了，其次是列冲突，判断一下是否有a[i]与当前要放置皇后的列j相等即可。至于斜线冲突，通过观察可以发现所有在斜线上冲突的皇后的位置都有规律即它们所在的行列互减的绝对值相等，即| row – i | = | col – a[i] | 。这样某个位置是否可以放置皇后的问题已经解决。

㈣ 常见算法思想6：回溯法

回溯法也叫试探法，试探的处事方式比较委婉，它先暂时放弃关于问题规模大小的限制，并将问题的候选解按某种顺序逐一进行枚举和检验。当发现当前候选解不可能是正确的解时，就选择下一个候选解。如果当前候选解除了不满足问题规模要求外能够满足所有其他要求时，则继续扩大当前候选解的规模，并继续试探。如果当前候选解满足包括问题规模在内的所有要求时，该候选解就是问题的一个解。在试探算法中，放弃当前候选解，并继续寻找下一个候选解的过程称为回溯。扩大当前候选解的规模，以继续试探的过程称为向前试探。

（1）针对所给问题，定义问题的解空间。
（2）确定易于搜索的解空间结构。
（3）以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。

回溯法为了求得问题的正确解，会先委婉地试探某一种可能的情况。在进行试探的过程中，一旦发现原来选择的假设情况是不正确的，马上会自觉地退回一步重新选择，然后继续向前试探，如此这般反复进行，直至得到解或证明无解时才死心。

下面是回溯的3个要素。
（1）解空间：表示要解决问题的范围，不知道范围的搜索是不可能找到结果的。
（2）约束条件：包括隐性的和显性的，题目中的要求以及题目描述隐含的约束条件，是搜索有解的保证。
（3）状态树：是构造深搜过程的依据，整个搜索以此树展开。

下面是影响算法效率的因素：

回溯法搜索解空间时，通常采用两种策略避免无效搜索，提高回溯的搜索效率:

为缩小规模，我们用显示的国际象棋8*8的八皇后来分析。按照国际象棋的规则，皇后的攻击方式是横，竖和斜向。
皇后可以攻击到同一列所有其它棋子，因此可推导出每1列只能存在1个皇后，即每个皇后分别占据一列。棋盘一共8列，刚好放置8个皇后。

为了摆放出满足条件的8个皇后的布局，可以按如下方式逐步操作：

把规模放大到N行N列也一样，下面用回溯法解决N皇后问题：

执行：