递归算法解决八皇后问题（用递归函数设计八皇后问题的回溯算法C++代码）

本文目录

• 用递归函数设计八皇后问题的回溯算法C++代码
• 八皇后问题递归算法不理解，求解
• 八皇后问题的C语言代码
• 八皇后递归算法的复杂性
• 八皇后问题求解方法分类
• 数据结构与算法-进阶（十七）回溯
• 八皇后问题
• 急求！！pascal n皇后问题 (递归） 带详细解析
• 如何用C语言编写八皇后问题
• 求教C语言回溯法写出八皇后问题的92种解

用递归函数设计八皇后问题的回溯算法C++代码

解析：递归实现n皇后问题。算法分析：数组a、b、c分别用来标记冲突，a数组代表列冲突，从a代表第0列到第7列。如果某列上已经有皇后，则为1，否则为0。数组b代表主对角线冲突，为b。如果某条主对角线上已经有皇后，则为1，否则为0。数组c代表从对角线冲突，为c。如果某条从对角线上已经有皇后，则为1，否则为0。代码如下：#include 《stdio.h》static char Queen;static int a;static int b;static int c;static int iQueenNum=0; //记录总的棋盘状态数void qu(int i); //参数i代表行int main(){ int iLine,iColumn; //棋盘初始化，空格为*，放置皇后的地方为@ for(iLine=0;iLine《8;iLine++) { a=0; //列标记初始化，表示无列冲突 for(iColumn=0;iColumn《8;iColumn++) Queen=’*’; } //主、从对角线标记初始化，表示没有冲突 for(iLine=0;iLine《15;iLine++) b=0; qu(0); return 0;}void qu(int i){ int iColumn; for(iColumn=0;iColumn《8;iColumn++) { if(a==0) //如果无冲突 { Queen=’@’; //放皇后 a=1; //标记，下一次该列上不能放皇后 b=1; //标记，下一次该主对角线上不能放皇后 c=1; //标记，下一次该从对角线上不能放皇后 if(i《7) qu(i+1); //如果行还没有遍历完，进入下一行 else //否则输出 { //输出棋盘状态 int iLine,iColumn; printf("第%d种状态为：\n",++iQueenNum); for(iLine=0;iLine《8;iLine++) { for(iColumn=0;iColumn《8;iColumn++) printf("%c ",Queen); printf("\n"); } printf("\n\n"); } //如果前次的皇后放置导致后面的放置无论如何都不能满足要求，则回溯，重置 Queen=’*’; a=0; b=0; c=0; } }}

八皇后问题递归算法不理解，求解

layout = i; //尝试在此位置上放上八皇后放上去之后才开始检查是不是合符八皇后的规则，if(isSafe(row, i)) // 结果为true 意思是在此位置上放八皇后是符合规则的lay(row+1) //那么OK，我们可以继续放下一层八皇后是典型的循环里面加递归， 和全排列很类似。在之后你可以看看DFS，深搜就是用这个原理

八皇后问题的C语言代码

#include 《math.h》#include 《stdio.h》#define MAX 8 /* 棋子数及棋盘大小MAXxMAX */int board;/* 印出结果 */void show_result(){ int i; for(i=0;i《MAX;i++)printf("(%d,%d)",i,board); printf("\n");}/* 检查是否在同一直横斜线上有其它棋子 */int check_cross(int n){ int i; for(i=0;i《n;i++){if(board))return 1; } return 0;}/* 放棋子到棋盘上 */void put_chess(int n){ int i; for(i=0;i《MAX;i++){board=i;if(!check_cross(n)){ if(n==MAX-1) show_result();/* 找到其中一种放法了...印出结果 */ else put_chess(n+1);} }}void main(){clrscr();puts("The possible placements are:"); put_chess(0); puts("\n Press any key to quit...");getch(); return;}到底是哪些奇葩老师布置的作业？

八皇后递归算法的复杂性

期盘是8*8的么?八皇后采用回溯的方法,其实就是一种效率比较低下的方法,采用深度优先遍历的方法进行(dfs),如果想问更多欢迎在我blog留言,我天天上的.下面说正事:如果是棋盘的长度n=8的话应该是O(n^16),但事实上应该比这快很多,因为O(n^16)会成一个很小的系数,为什么会这样呢,比如第一个顶点要考虑8*8的情况,在确定第二个顶点的时候就是小于7*7的情况了,但是算法时间复杂度只是处略的估计,不计较系数,而且n也不大.要是还有疑虑可以在hi上给我留言.

八皇后问题求解方法分类

八皇后问题{“八皇后”问题递归法求解(Pascal语言)八皇后问题是一个古老而著名的问题，是回溯算法的典型例题。该问题是十九世纪著名的数学家高斯1850年提出：在8X8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。高斯认为有76种方案。1854年在柏林的象棋杂志上不同的作者发表了40种不同的解，后来有人用图论的方法解出92种结果。现代教学中，把八皇后问题当成一个经典递归算法例题。算法分析：数组a、b、c分别用来标记冲突，a数组代表列冲突，从a代表第0列到第7列，如果某列上已经有皇后，则为1，否则为0；数组b代表主对角线冲突，为b，如果某条主对角线上已经有皇后，则为1，否则为0；数组c代表从对角线冲突，为c，如果某条从对角线上已经有皇后，则为1，否则为0；另优化：第一个皇后在1~4格，最后*2，即为总解数}programqueens;vara:arrayofinteger;b,c,d:arrayofinteger;t,i,j,k:integer;procedureprint;begint:=t+1;write(t,’:’);fork:=1to8dowrite(a,’’);writeln;end;proceduretry(i:integer);varj:integer;beginforj:=1to8do{每个皇后都有8种可能位置}if(b=0)and(c=0)and(d=0)then{判断位置是否冲突}begina:=j;{摆放皇后}b:=1;{宣布占领第J行}c:=1;{占领两个对角线}d:=1;ifi《8thentry(i+1){8个皇后没有摆完，递归摆放下一皇后}elseprint;{完成任务，打印结果}b:=0;{回溯}c:=0;d:=0;end;end;beginfillchar(a,sizeof(a),0);{初始化数组}fillchar(b,sizeof(b),0);fillchar(c,sizeof(c),0);fillchar(d,sizeof(d),0);try(1);{从第1个皇后开始放置}end.“八皇后”问题递归法求解(C语言)＃include"stdio.h"staticcharQueen;staticinta;staticintb;staticintc;staticintiQueenNum=0;//记录总的棋盘状态数voidqu(inti);//参数i代表行intmain(){intiLine,iColumn;//棋盘初始化，空格为*，放置皇后的地方为@for(iLine=0;iLine《8;iLine++){a=0;//列标记初始化，表示无列冲突for(iColumn=0;iColumn《8;iColumn++)Queen=’*’;}//主、从对角线标记初始化，表示没有冲突for(iLine=0;iLine《15;iLine++)b=0;qu(0);return0;}voidqu(inti){intiColumn;for(iColumn=0;iColumn《8;iColumn++){if(a==0)//如果无冲突{Queen=’@’;//放皇后a=1;//标记，下一次该列上不能放皇后b=1;//标记，下一次该主对角线上不能放皇后c=1;//标记，下一次该从对角线上不能放皇后if(i《7)qu(i+1);//如果行还没有遍历完，进入下一行else//否则输出{//输出棋盘状态intiLine,iColumn;printf("第%d种状态为：\n",++iQueenNum);for(iLine=0;iLine《8;iLine++){for(iColumn=0;iColumn《8;iColumn++)printf("%c",Queen);printf("\n"screen.width/2)this.width=screen.width/2"vspace=2border=0》;}printf("\n\n"screen.width/2)this.width=screen.width/2"vspace=2border=0》;}//如果前次的皇后放置导致后面的放置无论如何都不能满足要求，则回溯，重置Queen=’*’;a=0;b=0;c=0;}}}八皇后的c语言解法：#include《stdio.h》#include《conio.h》#include《math.h》intn,k,a,num=0;intattack(intk){intflag=0;inti=1;while((i《k)&&(a-a)!=(k-i)))i++;if(i==k)flag=1;returnflag;}voidplace(intk){//printf("%d",k);inti;if(k==n+1){num=num+1;printf("num=%d:",num);for(i=1;i《n+1;i++)printf("%d",a);printf("\n");}else{for(i=1;i《n+1;i++){a=i;if(attack(k)==1)place(k+1);elsea=0;}}}main(){scanf("%d",&n);k=1;place(k);if(k!=n+1)printf("nosolution!\n");getch();}***隐藏网址***

数据结构与算法-进阶（十七）回溯

回溯可以理解成在岔路口选择不同的道路，直到达到目的地。它的每一步都会选择一条路出发，能前进都前进，不能前进就退到上一步，选择其他的路走，直到走完所有路或者到达目的地为止。 不能前进就退到上一步的过程就是回溯 。

典型的回溯应用有树、图的深度优先搜索、八皇后问题或者走迷宫等等。这里以八皇后的问题为例，来看一下回溯。

八皇后问题是在一个8X8的棋牌中放8个皇后，使其不能相互攻击，也就是任意两个皇后不能在同一行、同一列、同一斜率上。

解决八皇后问题，有这样几种思路，第一种就是暴力破解，从64个格子中选择出任意的8个格子摆放皇后，然后检查摆法是否合适，检查完每一种，需要检查的次数非常的大。

那么，可以根据题意来减少暴力破解的次数，因为 任意两个皇后不能在同一行 ，也就是每一行只能放一个皇后，所以摆放的次数就减少成 8^8^ 次。虽然次数减少了很多，但是次数还是比较多的。

最后一个思路就是用回溯法来处理，每次摆放皇后后，就将不能被摆放的格子给剔除掉，这种操作叫做 剪切 。当到了无法摆放，并且皇后也没有摆放完时，就退回到最初摆放第一个皇后的位置，排除这个位置，从下一个位置开始，这个操作叫做 回溯 。所以这个思路是 回溯+剪切 。

首先创建一个类，并定义数组，保存皇后摆放的位置 cols，cols 数组的索引对应的是第几行，从 0 开始，索引对应的元素是第几列，从 0 开始，也就是存储的数据是第几行中的第几列摆放了皇后，其次还定义一个属性 ways 记录有多少种摆法：

接下来创建摆放八皇后的函数，placeQueens()，函数中传递参数 n，表示摆放多少个皇后，让函数适应更多的同类场景，所以摆放八皇后就是 placeQueens(8)，代码实现如下：

函数中先定义了 cols 数组的大小，有多少个皇后，就创建多少空间的数组。place() 函数执行的是摆放皇后的过程，传递的参数表示从第几行开始摆放，具体代码如下：

函数中可以看到 place(row+1) 这行代码，就是跳到下一行执行。当某行某列已经确定可以摆放皇后后，就暂时结束该行的遍历，跳到下一行执行。这里使用到递归思想， for 循环结束都是回溯的条件，如果没有达到终止条件，那么就会走 for 循环，当走完for 循环仍然没有找到可以摆放的位置时，然后执行 place(row+1) 上一行的代码，这就达到了 路不通，就回到上一步选择另外一条路 。isValid(row, col) 函数就是判断 (row, col) 的格子是否可以摆放皇后，代码如下：

这就是摆放皇后的核心部分。首先判断 col 列是否已经有皇后了，即遍历 cols 数组中是否存在 col 元素。如果不存在，就判断该 i 行的皇后和 (row, col) 区域的格子是否在同一斜率上，这里使用了斜率公式，x1-x2 = y1-y2 就是在同一斜率上，因为摆放的皇后，它的斜率就是 1。

八皇后问题

八皇后问题是一个古老而著名的问题，是回溯算法的典型例题。该问题是十九世纪著名的数学家高斯1850年提出：在8X8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。 高斯认为有76种方案。1854年在柏林的象棋杂志上不同的作者发表了40种不同的解，后来有人用图论的方法解出92种结果。事实上就是有92种解法。对于八皇后问题的实现，如果结合动态的图形演示，则可以使算法的描述更形象、更生动，使教学能产生良好的效果。下面是笔者用Turbo C实现的八皇后问题的图形程序，能够演示全部的92组解。八皇后问题动态图形的实现，主要应解决以下两个问题。 1．回溯算法的实现 （1）为解决这个问题，我们把棋盘的横坐标定为i，纵坐标定为j,i和j的取值范围是从1到8。当某个皇后占了位置(i,j)时，在这个位置的垂直方向、水平方向和斜线方向都不能再放其它皇后了。用语句实现，可定义如下三个整型数组：a。其中： a=1 第j列上无皇后 a=0 第j列上有皇后 b=1 (i,j)的对角线（左上至右下）无皇后 b=0 (i,j)的对角线（左上至右下）有皇后 c=1 (i,j)的对角线（右上至左下）无皇后 c=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={0,0};/*用于记录第几组解*/ int a,i; int h={127,177,227,277,327,377,427,477};/*每个皇后的行坐标*/ int l={252,217,182,147,112,77,42,7};/*每个皇后的列坐标*/ void *arrow; void try(int i) {int j; for (j=1;j《=8;j++) if (a==3) /*如果第i列第j行为空*/ {a=0;/*占用第i列第j行*/ putimage(h,arrow,COPY_PUT);/*显示皇后图形*/ delay(500);/*延时*/ if(i《8) try(i+1); else /*输出一组解*/ {n=0;} bar(260,300,390,340);/*显示第n组解*/ outtextxy(275,300,n); delay(3000); } a=1; putimage(h,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); } 八皇后问题的串行算法 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=column; if (step==8) outputresult( ); /*结束递归打印结果*/ else /*继续递归*/ {for(place=1;place《=8;place++) {for(j=1;j《=step;j++) if(collision(j ,row,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=j; //则不安全的地方是 k行 j位置,j+k-i位置,j-k+i位置 class Queen8{ static final int QueenMax = 8; static int oktimes = 0; static int chess;//每一个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; for(;i《QueenMax;i++) qsave=true; //下面先把安全位数组完成 i=0;//i 是现在要检查的数组值 while (i《num){ qsave=false; int k=num-i; if ( (chess=false; if ( (chess=false; i++; } //下面历遍安全位 for(i=0;i《QueenMax;i++){ if (qsave==false)continue; if (num《QueenMax-1){ chess=i; placequeen(num+1); } else{ //num is last one chess=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); } } } //历遍完成就停止

急求！！pascal n皇后问题 (递归） 带详细解析

〖问题描述〗在一个8×8的棋盘里放置8个皇后，要求每个皇后两两之间不相"冲"（在每一横列竖列斜列只有一个皇后）。〖问题分析〗(聿怀中学吕思博)这道题可以用递归循环来做，分别一一测试每一种摆法，直到得出正确的答案。主要解决以下几个问题：1、冲突。包括行、列、两条对角线：（1）列：规定每一列放一个皇后，不会造成列上的冲突；（2）行：当第I行被某个皇后占领后，则同一行上的所有空格都不能再放皇后，要把以I为下标的标记置为被占领状态；（3）对角线：对角线有两个方向。在同一对角线上的所有点（设下标为(i,j)），要么(i+j)是常数，要么(i-j)是常数。因此，当第I个皇后占领了第J列后，要同时把以(i+j)、(i-j)为下标的标记置为被占领状态。2、数据结构。（1）解数组A。A表示第I个皇后放置的列；范围：1..8（2）行冲突标记数组B。B=1表示第I行被占领；范围：1..8（3）对角线冲突标记数组C、D。C=1表示第（I-J）条对角线被占领；范围：-7..7D=1表示第（I+J）条对角线被占领；范围：2..16〖算法流程〗1、数据初始化。2、从n列开始摆放第n个皇后（因为这样便可以符合每一竖列一个皇后的要求），先测试当前位置(n,m)是否等于0（未被占领）:如果是，摆放第n个皇后，并宣布占领(记得要横列竖列斜列一起来哦)，接着进行递归；如果不是，测试下一个位置(n,m+1)，但是如果当n《=8,m=8时，却发现此时已经无法摆放时，便要进行回溯。3、当n》;8时，便一一打印出结果。〖优点〗逐一测试标准答案，不会有漏网之鱼。〖参考程序〗queen.pas----------------------------------------------------------------------------programtt;vara:arrayofinteger;b,c,d:arrayofinteger;t,i,j,k:integer;procedureprint;begint:=t+1;write(t,’’);fork:=1to8dowrite(a,’’);writeln;end;proceduretry(i:integer);varj:integer;beginforj:=1to8doif(b=0)thenbegina:=j;b:=1;c:=1;d:=1;ifi《8thentry(i+1)elseprint;b:=0;c:=0;d:=0;end;end;beginfork:=-7to16dobeginb:=0;c:=0;d:=0;end;try(1);end.==========================================这是N皇后问题，看看吧： 在N*N的棋盘上，放置N个皇后，要求每一横行每一列，每一对角线上均只能放置一个皇后，问可能的方案及方案数。 const max=8; var i,j:integer; a:array of 0..max; //放皇后数组 b:array of boolean; // ‘/’对角线标志数组} c:array of boolean;// ‘\’对角线标志数组} col:array of boolean; //列标志数组} total:integer; //统计总数} procedure output; //这里是输出过程 var i:integer; begin write(’No.’:4,’’); for i:=1 to max do write(a:3);write(’ ’); if (total+1) mod 2 =0 then writeln; inc(total); end; function ok(i,dep:integer):boolean; //判断第dep行第i列可放否？ begin ok:=false; if ( b=true) and (col=true) then ok:=true end; procedure try(dep:integer); var i,j:integer; begin for i:=1 to max do //每一行均有max种放法，对吧？xixi~~~~ if ok(i,dep) then begin a:=i; b:=false; // ‘/’对角线已放标志 c:=false; // ‘\’对角线已放标志 col:=false; // 列已放标志 if dep=max then output else try(dep+1); // 递归下一层 a:=0; //取走皇后,回溯 b:=true; //恢复标志数组 c:=true; col:=true; end; end; begin for i:=1 to max do begin a:=true;end; for i:=2 to 2*max do b:=true; for i:=-(max-1) to max-1 do c:=true; total:=0; try(1); writeln(’total:’,total); end.方案一（深度优先搜索）：var ans:array of integer; //记录答案的数组，记录在第1到第8行皇后所在的列； lie:array of boolean; //记录1到8中某列是否已经被另一个皇后占用； zx:array of boolean; //正斜线（左下向右上）数组，该斜线特点为：斜线上每一格的行加列的和一定，和为从2到16. 9士捎?到16来表示这15条正斜线，于是该数组记录了2到16中某条正斜线是否已经被另一个皇后占用； fx:array of boolean; //反斜线（左上向右下）数组，该斜线特点为：斜线上每一格的行减列的差一定，差为从-7到7 9士捎?7到7来表示这15条正斜线，于是该数组记录了2到16中某条正斜线是否已经被另一个皇后占用； temp:integer; //记录总方案数；procedure print; //该子程序负责输出方案；var i:integer;begin write(’zuobiao’); for i:=1 to 8 do write(’ (’,i,’,’,ans代表列； 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 then //当前位置，该列，正斜线，反斜线上均未被另一个皇后占用，即可以摆放一个皇后； begin lie:=true; //设置标志，该行 zx:=true; // 该正斜线 fx:=true; // 该反斜线上已被皇后占用，不可再放皇后； ans:=j; //记录答案（第i行皇后所在列j）； search(i+1); //实行下一层递归； lie:=false; //恢复标志（回溯）； zx:=false; fx:=false; end;end;begin //主程序； temp:=0; //给总方案数设初值为0; fillchar(lie,sizeof(lie),0); //分别给列; fillchar(zx,sizeof(zx),0); // 正斜线; fillchar(fx,sizeof(fx),0); // 反斜线数组设初值为False; search(1); //从第一行开始进行搜索； writeln(temp); //再输出总方案数；end.方案二（位运算加速）：var upperlim,sum:integer;procedure test(row,ld,rd:integer);var pos,p:integer;begin if row《》upperlim then begin pos:=upperlim and not (row or ld or rd); while pos《》0 do begin p:=pos and -pos; pos:=pos-p; test(row+p,(ld+p)shl 1,(rd+p)shr 1); end; end else inc(sum);end;begin upperlim:=(1 shl 8)-1; test(0,0,0); writeln(sum);end. 设置一个三维数组，第一个下标是皇后的行坐标，第二个下标是皇后的列坐标，第三个下标是残卷号。相当于有N张叠在一起的8*8棋盘，每张棋盘只在复制前面棋盘及皇后后加放置一个皇后。直到放满8皇后后才是一张完整的8皇后图，称完卷。

如何用C语言编写八皇后问题

#include "stdio.h" \x0d\x0a#include "windows.h" \x0d\x0a#define N 8 /* 定义棋盘大小 */ \x0d\x0aint place(int k); /* 确定某一位置皇后放置与否，放置则返回1，反之返回0 */ \x0d\x0avoid backtrack(int i);/* 主递归函数，搜索解空间中第i层子树 */ \x0d\x0avoid chessboard(); /* 每找到一个解,打印当前棋盘状态 */ \x0d\x0astatic int sum, /* 当前已找到解的个数 */ \x0d\x0ax) printf("@ "); \x0d\x0aelse printf("* "); \x0d\x0aprintf("\n"); \x0d\x0a} \x0d\x0aprintf("\n"); \x0d\x0a}

求教C语言回溯法写出八皇后问题的92种解

(1)全排列

将自然数1~n进行排列，共形成n!中排列方式，叫做全排列。

例如3的全排列是：1/2/3、1/3/2、2/1/3、2/3/1、3/1/2、3/2/1，共3!=6种。

(2)8皇后（或者n皇后）

保证8个皇后不能互相攻击，即保证每一横行、每一竖行、每一斜行最多一个皇后。

我们撇开第三个条件，如果每一横行、每一竖行都只有一个皇后。

将8*8棋盘标上坐标。我们讨论其中的一种解法：

 - - - - - - - Q

 - - - Q - - - -

 Q - - - - - - -

 - - Q - - - - -

 - - - - - Q - -

 - Q - - - - - -

 - - - - - - Q -

 - - - - Q - - -

如果用坐标表示就是：(1,8) (2,4) (3,1) (4,3) (5,6) (6,2) (7,7) (8,5)

将横坐标按次序排列，纵坐标就是8/4/1/3/6/2/7/5。这就是1~8的一个全排列。

我们将1~8的全排列存入输入a)，其中i为0~7。

这样就能保证任意两个不会同一行、同一列了。

置于斜行，你知道的，两个点之间连线的斜率绝对值为1或者-1即为同一斜行，充要条件是|x1-x2|=|y1-y2|（两个点的坐标为（x1,y1）(x2,y2)）。我们在输出的时候进行判断，任意两个点如果满足上述等式，则判为失败，不输出。

下面附上代码：添加必要的注释，其中全排列的实现看看注释应该可以看懂：

#include《stdio.h》#include《math.h》#include《string.h》#include《stdlib.h》int printed;//该函数用于画图，这里为了节约空间则略去//读者只需要将draw(a,k);去掉注释即可画图void draw(int* a,int k){int i,j;for(i=0;i《k;i++){printf("\t");for(j=0;j《k;j++)//有皇后输出Q，否则输出-if(a-1==j) printf("Q "); else printf("- ");printf("\n");}printf("\n");}//递归实现全排列,a是数组，iStep是位置的测试点，k是皇后的个数，一般等于8void Settle(int *a,int iStep,int k){int i,j,l,flag=1;//如果iStep的数字等于a之前的数字，则存在重复，返回for(i=0;i《iStep-1;i++)if(a) return;//如果iStep==k，即递归结束到最后一位，可以验证是否斜行满足if(iStep==k) {//双重循环判断是否斜行满足for(j=0;j《k;j++)for(l=0;l《k&&l!=j;l++)//如果不满足，则flag=0if(fabs(j-l)==fabs(a)) flag=0;//如果flag==1，则通过了斜行的所有测试，输出。if(flag){for(i=0;i《k;i++)printf("(%d,%d) ",i+1,a);printf("\n");//如果去掉这里的注释可以获得画图，由于空间不够，这里略去//draw(a,k);//printed变量计算有多少满足题意的结果，是全局变量printed++;}flag=1;}//如果未测试至最后末尾，则测试下一位（递归）for(i=1;i《=k;i++){a=i;Settle(a,iStep+1,k);}}void main(){int* a;int k;//输入维数，建立数组printf("Enter the size of the square:");scanf("%d",&k);a=(int*)calloc(k,sizeof(int));//清屏，从iStep=0处进入递归system("cls");Settle(a,0,k);//判断最后是否有结果if(! printed) printf("No answers accepted!\n");else printf("%d states available!\n",printed);}附输出结果（输入k=8）：(1,1) (2,5) (3,8) (4,6) (5,3) (6,7) (7,2) (8,4)(1,1) (2,6) (3,8) (4,3) (5,7) (6,4) (7,2) (8,5)(1,1) (2,7) (3,4) (4,6) (5,8) (6,2) (7,5) (8,3)(1,1) (2,7) (3,5) (4,8) (5,2) (6,4) (7,6) (8,3)(1,2) (2,4) (3,6) (4,8) (5,3) (6,1) (7,7) (8,5)(1,2) (2,5) (3,7) (4,1) (5,3) (6,8) (7,6) (8,4)(1,2) (2,5) (3,7) (4,4) (5,1) (6,8) (7,6) (8,3)(1,2) (2,6) (3,1) (4,7) (5,4) (6,8) (7,3) (8,5)(1,2) (2,6) (3,8) (4,3) (5,1) (6,4) (7,7) (8,5)(1,2) (2,7) (3,3) (4,6) (5,8) (6,5) (7,1) (8,4)(1,2) (2,7) (3,5) (4,8) (5,1) (6,4) (7,6) (8,3)(1,2) (2,8) (3,6) (4,1) (5,3) (6,5) (7,7) (8,4)(1,3) (2,1) (3,7) (4,5) (5,8) (6,2) (7,4) (8,6)(1,3) (2,5) (3,2) (4,8) (5,1) (6,7) (7,4) (8,6)(1,3) (2,5) (3,2) (4,8) (5,6) (6,4) (7,7) (8,1)(1,3) (2,5) (3,7) (4,1) (5,4) (6,2) (7,8) (8,6)(1,3) (2,5) (3,8) (4,4) (5,1) (6,7) (7,2) (8,6)(1,3) (2,6) (3,2) (4,5) (5,8) (6,1) (7,7) (8,4)(1,3) (2,6) (3,2) (4,7) (5,1) (6,4) (7,8) (8,5)(1,3) (2,6) (3,2) (4,7) (5,5) (6,1) (7,8) (8,4)(1,3) (2,6) (3,4) (4,1) (5,8) (6,5) (7,7) (8,2)(1,3) (2,6) (3,4) (4,2) (5,8) (6,5) (7,7) (8,1)(1,3) (2,6) (3,8) (4,1) (5,4) (6,7) (7,5) (8,2)(1,3) (2,6) (3,8) (4,1) (5,5) (6,7) (7,2) (8,4)(1,3) (2,6) (3,8) (4,2) (5,4) (6,1) (7,7) (8,5)(1,3) (2,7) (3,2) (4,8) (5,5) (6,1) (7,4) (8,6)(1,3) (2,7) (3,2) (4,8) (5,6) (6,4) (7,1) (8,5)(1,3) (2,8) (3,4) (4,7) (5,1) (6,6) (7,2) (8,5)(1,4) (2,1) (3,5) (4,8) (5,2) (6,7) (7,3) (8,6)(1,4) (2,1) (3,5) (4,8) (5,6) (6,3) (7,7) (8,2)(1,4) (2,2) (3,5) (4,8) (5,6) (6,1) (7,3) (8,7)(1,4) (2,2) (3,7) (4,3) (5,6) (6,8) (7,1) (8,5)(1,4) (2,2) (3,7) (4,3) (5,6) (6,8) (7,5) (8,1)(1,4) (2,2) (3,7) (4,5) (5,1) (6,8) (7,6) (8,3)(1,4) (2,2) (3,8) (4,5) (5,7) (6,1) (7,3) (8,6)(1,4) (2,2) (3,8) (4,6) (5,1) (6,3) (7,5) (8,7)(1,4) (2,6) (3,1) (4,5) (5,2) (6,8) (7,3) (8,7)(1,4) (2,6) (3,8) (4,2) (5,7) (6,1) (7,3) (8,5)(1,4) (2,6) (3,8) (4,3) (5,1) (6,7) (7,5) (8,2)(1,4) (2,7) (3,1) (4,8) (5,5) (6,2) (7,6) (8,3)(1,4) (2,7) (3,3) (4,8) (5,2) (6,5) (7,1) (8,6)(1,4) (2,7) (3,5) (4,2) (5,6) (6,1) (7,3) (8,8)(1,4) (2,7) (3,5) (4,3) (5,1) (6,6) (7,8) (8,2)(1,4) (2,8) (3,1) (4,3) (5,6) (6,2) (7,7) (8,5)(1,4) (2,8) (3,1) (4,5) (5,7) (6,2) (7,6) (8,3)(1,4) (2,8) (3,5) (4,3) (5,1) (6,7) (7,2) (8,6)(1,5) (2,1) (3,4) (4,6) (5,8) (6,2) (7,7) (8,3)(1,5) (2,1) (3,8) (4,4) (5,2) (6,7) (7,3) (8,6)(1,5) (2,1) (3,8) (4,6) (5,3) (6,7) (7,2) (8,4)(1,5) (2,2) (3,4) (4,6) (5,8) (6,3) (7,1) (8,7)(1,5) (2,2) (3,4) (4,7) (5,3) (6,8) (7,6) (8,1)(1,5) (2,2) (3,6) (4,1) (5,7) (6,4) (7,8) (8,3)(1,5) (2,2) (3,8) (4,1) (5,4) (6,7) (7,3) (8,6)(1,5) (2,3) (3,1) (4,6) (5,8) (6,2) (7,4) (8,7)(1,5) (2,3) (3,1) (4,7) (5,2) (6,8) (7,6) (8,4)(1,5) (2,3) (3,8) (4,4) (5,7) (6,1) (7,6) (8,2)(1,5) (2,7) (3,1) (4,3) (5,8) (6,6) (7,4) (8,2)(1,5) (2,7) (3,1) (4,4) (5,2) (6,8) (7,6) (8,3)(1,5) (2,7) (3,2) (4,4) (5,8) (6,1) (7,3) (8,6)(1,5) (2,7) (3,2) (4,6) (5,3) (6,1) (7,4) (8,8)(1,5) (2,7) (3,2) (4,6) (5,3) (6,1) (7,8) (8,4)(1,5) (2,7) (3,4) (4,1) (5,3) (6,8) (7,6) (8,2)(1,5) (2,8) (3,4) (4,1) (5,3) (6,6) (7,2) (8,7)(1,5) (2,8) (3,4) (4,1) (5,7) (6,2) (7,6) (8,3)(1,6) (2,1) (3,5) (4,2) (5,8) (6,3) (7,7) (8,4)(1,6) (2,2) (3,7) (4,1) (5,3) (6,5) (7,8) (8,4)(1,6) (2,2) (3,7) (4,1) (5,4) (6,8) (7,5) (8,3)(1,6) (2,3) (3,1) (4,7) (5,5) (6,8) (7,2) (8,4)(1,6) (2,3) (3,1) (4,8) (5,4) (6,2) (7,7) (8,5)(1,6) (2,3) (3,1) (4,8) (5,5) (6,2) (7,4) (8,7)(1,6) (2,3) (3,5) (4,7) (5,1) (6,4) (7,2) (8,8)(1,6) (2,3) (3,5) (4,8) (5,1) (6,4) (7,2) (8,7)(1,6) (2,3) (3,7) (4,2) (5,4) (6,8) (7,1) (8,5)(1,6) (2,3) (3,7) (4,2) (5,8) (6,5) (7,1) (8,4)(1,6) (2,3) (3,7) (4,4) (5,1) (6,8) (7,2) (8,5)(1,6) (2,4) (3,1) (4,5) (5,8) (6,2) (7,7) (8,3)(1,6) (2,4) (3,2) (4,8) (5,5) (6,7) (7,1) (8,3)(1,6) (2,4) (3,7) (4,1) (5,3) (6,5) (7,2) (8,8)(1,6) (2,4) (3,7) (4,1) (5,8) (6,2) (7,5) (8,3)(1,6) (2,8) (3,2) (4,4) (5,1) (6,7) (7,5) (8,3)(1,7) (2,1) (3,3) (4,8) (5,6) (6,4) (7,2) (8,5)(1,7) (2,2) (3,4) (4,1) (5,8) (6,5) (7,3) (8,6)(1,7) (2,2) (3,6) (4,3) (5,1) (6,4) (7,8) (8,5)(1,7) (2,3) (3,1) (4,6) (5,8) (6,5) (7,2) (8,4)(1,7) (2,3) (3,8) (4,2) (5,5) (6,1) (7,6) (8,4)(1,7) (2,4) (3,2) (4,5) (5,8) (6,1) (7,3) (8,6)(1,7) (2,4) (3,2) (4,8) (5,6) (6,1) (7,3) (8,5)(1,7) (2,5) (3,3) (4,1) (5,6) (6,8) (7,2) (8,4)(1,8) (2,2) (3,4) (4,1) (5,7) (6,5) (7,3) (8,6)(1,8) (2,2) (3,5) (4,3) (5,1) (6,7) (7,4) (8,6)(1,8) (2,3) (3,1) (4,6) (5,2) (6,5) (7,7) (8,4)(1,8) (2,4) (3,1) (4,3) (5,6) (6,2) (7,7) (8,5)92 states available!