八皇后问题地解决完整文档

⼋皇后问题（经典算法-回溯法）问题描述：⼋皇后问题（eight queens problem）是⼗九世纪著名的数学家⾼斯于1850年提出的。

问题是：在8×8的棋盘上摆放⼋个皇后，使其不能互相攻击。

即任意两个皇后都不能处于同⼀⾏、同⼀列或同⼀斜线上。

可以把⼋皇后问题扩展到n皇后问题，即在n×n的棋盘上摆放n个皇后，使任意两个皇后都不能互相攻击。

思路：使⽤回溯法依次假设皇后的位置，当第⼀个皇后确定后，寻找下⼀⾏的皇后位置，当满⾜左上、右上和正上⽅向⽆皇后，即矩阵中对应位置都为0，则可以确定皇后位置，依次判断下⼀⾏的皇后位置。

当到达第8⾏时，说明⼋个皇后安置完毕。

代码如下：#include<iostream>using namespace std;#define N 8int a[N][N];int count=0;//判断是否可放bool search(int r,int c){int i,j;//左上+正上for(i=r,j=c; i>=0 && j>=0; i--,j--){if(a[i][j] || a[i][c]){return false;}}//右上for(i=r,j=c; i>=0 && j<N; i--,j++){if(a[i][j]){return false;}}return true;}//输出void print(){for(int i=0;i<N;i++){for(int j=0;j<N;j++){cout<<a[i][j]<<" ";}cout<<endl;}}//回溯法查找适合的放法void queen(int r){if(r == 8){count++;cout<<"第"<<count<<"种放法\n";print();cout<<endl;return;}int i;for(i=0; i<N; i++){if(search(r,i)){a[r][i] = 1;queen(r+1);a[r][i] = 0;}}}//⼊⼝int main(){queen(0);cout<<"⼀共有"<<count<<"放法\n"; return 0;}。

算法⼊门经典-第七章例题7-2⼋皇后问题原本利⽤回溯思想解决的经典⼋皇后问题，其实也是可以⽤递归解决的~⼋皇后的递归解决思路：从第⼀⾏开始，依次判断0~8列的哪⼀列可以放置Queen，这样就确定了该⾏的Queen的位置，然后⾏数递增，继⽽递归实现下⼀⾏的判断，依次类推直到⾏数增加到8（⾏数从0开始的），此时为递归-----归的条件，即表⽰⼀种⼋皇后的解决⽅法完成，打印结果；之后进⾏下⼀种解决⽅法的寻找，⼤致思路个⼈理解是这样noDanger(row,j,(*chess)[8])函数是判断第row⾏第j列是否可以放置Queen#include<stdio.h>int count=0;//参数row：起始⾏//参数n:表⽰列数//参数(*chess)[8]表⽰指向棋盘每⼀⾏的指针int NotDanger(int row,int j,int (*chess)[8])//⽐较不同⾏同列上是否有其他皇后{int i,k,flag1=0,flag2=0,flag3=0,flag4=0,flag5=0;//判断列⽅向for(i=0;i<8;i++){if(*(*(chess+i)+j)!=0) //在这之前列上有其他皇后{flag1=1;break;}}for(i=row,k=j;i>=0&&k>=0;i--,k--){if(*(*(chess+i)+k)!=0) //左上⽅{flag2=1;break;}}for(i=row,k=j;i<8&&k<8;i++,k++){if(*(*(chess+i)+k)!=0) //右下⽅{flag3=1;break;}}for(i=row,k=j;i>=0&&k<8;i--,k++){if(*(*(chess+i)+k)!=0) //右上⽅{flag4=1;break;}}for(i=row,k=j;i<8&&k>=0;i++,k--){if(*(*(chess+i)+k)!=0) //左下⽅{flag5=1;break;}}if(flag1||flag2||flag3||flag4||flag5){return0;//如果有⼀个位置被占有危险}else return1;} /*int noDanger(int row,int j,int (*chess)[8]){int flag1=0,flag2=0,flag3=0,flag4=0,flag5=0;int i,k;//判断列for(i=0;i<8;i++){if(*(*(chess+i)+j)!=0){flag1=1;break;}}//判断左上⽅for(i=row,k=j;i>=0&&k>=0;i--,k--){if(*(*(chess+i)+k)!=0){flag2=1;break;}}//判断右下⽅for(i=row,k=j;i<8&&k<8;i++,k++){if(*(*(chess+i)+k)!=0){flag3=1;break;}}//判断左下⽅for(i=row,k=j;i<8&&k>=0;k--,i++){if(*(*(chess+i)+k)!=0){flag4=1;break;}}//判断右上⽅for(i=row,k=j;i>=0&&k<8;k++,i--){if(*(*(chess+i)+k)!=0){flag5=1;break;}}if(flag1||flag2||flag3||flag4||flag5){return 0;}else{return 1;}} */EightQueen(int row,int n,int (*chess)[8]){int chess2[8][8];int i,j;for(i=0;i<8;i++){for(j=0;j<8;j++){chess2[i][j]=chess[i][j];}}if(8==row){printf("第%d 种\n",count+1);for(i=0;i<8;i++){for(j=0;j<8;j++)printf("%3d ",*(*(chess2+i)+j));printf("\n");}count++;}else{//判断这个位置是否危险 j<列for(j=0;j<n;j++){if(NotDanger(row,j,chess2))//尝试每⼀列是否危险 {for(i=0;i<8;i++){//整⾏所有列的位置赋值为0*(*(chess2+row)+i)= 0;}*(*(chess2+row)+j)=1;//皇后的位置赋值为1EightQueen(row+1,n,chess2);//继续往下⼀⾏递归 }}}}int main(){int chess[8][8],i,j;for(i=0;i<8;i++){for(j=0;j<8;j++)chess[i][j]=0;}EightQueen(0,8,chess);printf("总共有%d种解决⽅法",count);return0;}。

数据结构实验报告实验名称：实验2 利用栈结构实现八皇后问题学生姓名：廖宁班级：2009211114班内序号：18学号：09210411日期：2010年11月18日1．实验要求八皇后问题是19世纪著名的数学家高斯于1850年提出的。

他的问题是：在8*8的棋盘上放置8个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列、同一斜线上。

请设计算法打印所有可能的摆放方法。

提示：（1）可以使用递归或非递归两种方法实现。

（2）实现一个关键算法，判断任意两个皇后是否在同一行、同一列和同一斜线上。

2. 程序分析程序工程包含一个模板类函数实现定义的源文件forthelove.cpp和测试源文件sbsuowang.cpp。

2.1 存储结构存储结构为栈。

2.2 关键算法分析(1)判断在第row行第column列摆放皇后是否非法,采取定行不定列的方法，列相等的算法为position[i]=colume，对角线相等有两种情况：一是position在上则row-i=colume-position[i];二是position在下，row-i=position[i]-colume.加入能放皇后，列和对角线上值都不能相等。

具体代码如下：int IsIllegal(int row, int column, const int* position){/int i;for (i=1; i < row; ++i){if ((position[i] == column)|| (row - i == column - position[i])|| (row - i == position[i] - column)){return TRUE;}}return FALSE;}（2）我采用定行尝试列的方法来遍历，记录皇后位置的数组可以和栈数组合二为一，而栈顶指针也可以和行坐标合二为一，这样一来栈帧只要一个列坐标就可以了。

1.伪代码：while(栈不空）{if ( 行(即栈顶) <= n && 列<= n ){if ( 当前位置不能放皇后){列++;}else{列入栈(隐含着"行++");列= 1;}}else{if ( 行(即栈顶) > n ){输出位置数组(即栈数组);}列退栈(隐含着"行--");列++;}}//end while具体实现代码：void Queens(int n, void (* Visit)(const int* position)) {//position[n]数组:position[0]为棋盘大小，即n//position[1]~position[n]：下标为行坐标，值为列坐标int* stack = NULL; //栈int top; //栈顶int column; //列stack = (int*)malloc((n + 1) * sizeof(int));stack[0] = n;top = column = 1;while(top > 0){if ((top <= n) && (column <= n)){if (IsIllegal(top, column, stack)){++column;}else{stack[top++] = column;column = 1;}}else{if (top > n){(* Visit)(stack);}column = stack[--top];++column;}}//end whilefree(stack);return;}3. 程序运行结果程序实现八皇后问题：经过测试，程序运行良好，无明显错误。

⼋皇后以及N皇后问题分析⼋皇后是⼀个经典问题，在8*8的棋盘上放置8个皇后，每⼀⾏不能互相攻击。

因此拓展出 N皇后问题。

下⾯慢慢了解解决这些问题的⽅法：回溯法：回溯算法也叫试探法，它是⼀种系统地搜索问题的解的⽅法。

回溯算法的基本思想是：从⼀条路往前⾛，能进则进，不能进则退回来，换⼀条路再试。

在现实中，有很多问题往往需要我们把其所有可能穷举出来，然后从中找出满⾜某种要求的可能或最优的情况，从⽽得到整个问题的解。

回溯算法就是解决这种问题的“通⽤算法”，有“万能算法”之称。

N皇后问题在N增⼤时就是这样⼀个解空间很⼤的问题，所以⽐较适合⽤这种⽅法求解。

这也是N皇后问题的传统解法，很经典。

算法描述：1. 算法开始，清空棋盘。

当前⾏设为第⼀⾏，当前列设为第⼀列。

2. 在当前⾏，当前列的判断放置皇后是否安全，若不安全，则跳到第四步。

3. 在当前位置上满⾜条件的情况： 在当前位置放⼀个皇后，若当前⾏是最后⼀⾏，记录⼀个解； 若当前⾏不是最后⼀⾏，当前⾏设为下⼀⾏，当前列设为当前⾏的第⼀个待测位置； 若当前⾏是最后⼀⾏，当前列不是最后⼀列，当前列设为下⼀列； 若当前⾏是最后⼀⾏，当前列是最后⼀列，回溯，即清空当前⾏以及以下各⾏的棋盘，然后当前⾏设为上⼀⾏，当前列设为当前⾏的下⼀个待测位置； 以上返回第⼆步。

4.在当前位置上不满⾜条件： 若当前列不是最后⼀列，当前列设为下⼀列，返回到第⼆步； 若当前列是最后⼀列，回溯，即，若当前⾏已经是第⼀⾏了，算法退出，否则，清空当前⾏以及以下各⾏的棋盘，然后，当前⾏设为上⼀⾏，当前列设为当前⾏的下⼀个待测位置，返回第⼆步。

如何判断是否安全：把棋盘存储为⼀个N维数组a[N]，数组中第i个元素的值代表第i⾏的皇后位置，这样便可以把问题的空间规模压缩为⼀维O(N)，在判断是否冲突时也很简单， ⾸先每⾏只有⼀个皇后，且在数组中只占据⼀个元素的位置，⾏冲突就不存在了， 其次是列冲突，判断⼀下是否有a[i]与当前要放置皇后的列j相等即可。

C++实现八皇后问题及其扩展N皇后问题(经典回溯算法)八皇后问题是一个古老而著名的问题，是回溯算法的典型例题。

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

高斯认为有76种方案。

1854年在柏林的象棋杂志上不同的作者发表了40种不同的解，后来有人用八皇后问题是一个古老而著名的问题，是回溯算法的典型例题。

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

高斯认为有76种方案。

1854年在柏林的象棋杂志上不同的作者发表了40种不同的解，后来有人用图论的方法解出92种结果。

事实上就是有92种解法。

了解了基本的原理后,我们开始分析:1.我们需要一个数据存放已经放置皇后的位置,用指针表示的一维数据*position,长度为N(N为放置的皇后总数),可能有人会问为什么不用二维数组,用下票i,j准备定位,事实是这样的,因为该问题是每行,每列,每组对角线只可能出现一个皇后,所以用一维数据position+i中的i则能代码第几行,而值*(position+i)则表示该行中的列值,其实质与二维数组无异.2.判断每行可放置皇后,假设要判断第n行,则从position中从0到n-1每一个已放皇后的位置判断(列,对角线)具体算法如下:#include <iostream>#include <math.h>#include <malloc.h>using namespace std;int *position; //放置的位置int queen; //皇后数目int count; //第N种可能性//判断第n行是否放置皇后bool SignPoint(int n){for (int i=0;i<n;i++){if (*(position+i) == *(position+n)) //该列已经放置过皇后了return false;if (abs(*(position+i) - *(position+n)) == n-i) //对角线已经放置过了return false;}return true;}//设置皇后void SetQueen(int n=0){if (queen==n){//该处可以改成自己想要的显示方式printf("NO.%d: ",++count);printf("\n");for (int i=0;i<queen;i++){for (int j=0;j<queen;j++){if (j == position[i]){printf("* ");}else{printf("0 ");}}printf("\n");}printf("\n");return;}else{for (int i=0;i<queen;i++){position[n] = i;if(SignPoint(n))//如果该位置放置皇后正确的话,则到下一行{SetQueen(n+1);}}}}int main(int argc, char * argv[]){cout<<"请输入皇后的总数:"<<endl;cin>>queen;position = (int*)malloc(sizeof(int));SetQueen();cout<<"摆放完毕"<<endl;cin.get();cin.get();return 0;}。

该算法的大概描述：
1.置当前行 当前列均为1 2.While当前行号(<=8) 3.检查 当前行，从当前列起逐列试探，寻找安全列号 4.If（找到安全号） 5.放置皇后，将列号记入栈中，并将下一行置成当前行，第一列置为当前列 6.否则回溯到上一行，移去该行已经放置的皇后，以该皇后所在列的下一列作为当 前列， 8结束程序。
八皇后问题
八数学家高斯1850年提出：在 8X8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任 意两个皇后都不能处于同一行、同一列或同一斜线上，问有 多少种摆法？八皇后在棋盘上分布的各种可能的数目非常大。 但是可以将一些明显不满足问题要求的格局排除掉，由于任 意两个皇后不可能同行，即每一行只能放置一个皇后，因此 将第i个皇后放置在第i行上。这样 在放置第i个皇后时，只要 考虑它与前i-1个皇后处于不同列和不同对角线位置上即可。
一般算法
用 数组a、b、c分别用来标记冲突，a数组代表列冲突，从a[0]~a[7]代表第0列到第 7列，如果某列上已经有皇后，则为1，否则为0； 数组b代表主对角线冲突，为b[i-j+7]，即从b[0]~b[14]，如果某条主对角线上已经 有皇后，则为1，否则为0； 数组c代表从对角线冲突，为c[i+j]，即从c[0]~c[14]，如果某条从对角线上已经有皇 后，则为1，否则为0； 从第一行起 逐个放置皇后，每放置一个皇后依次对第1，2......8列进行试探，若当 前 试探的列位置是安全的，则将该行的列位置保存在栈中，然后继续在下一行寻 找安全位置，若当前试探的列位置不安全，则用下一列进行试探，当8列的位置试 探完毕都未能找到安全位置时，就退栈回溯到上一行，修改栈顶保存的皇后位置， 然后继续试探。

1213：⼋皇后问题【题⽬描述】在国际象棋棋盘上放置⼋个皇后，要求每两个皇后之间不能直接吃掉对⽅。

【输⼊】(⽆)【输出】按给定顺序和格式输出所有⼋皇后问题的解（见样例）。

【输⼊样例】（⽆）【输出样例】No. 11 0 0 0 0 0 0 00 0 0 0 0 0 1 00 0 0 0 1 0 0 00 0 0 0 0 0 0 10 1 0 0 0 0 0 00 0 0 1 0 0 0 00 0 0 0 0 1 0 00 0 1 0 0 0 0 0No. 21 0 0 0 0 0 0 00 0 0 0 0 0 1 00 0 0 1 0 0 0 00 0 0 0 0 1 0 00 0 0 0 0 0 0 10 1 0 0 0 0 0 00 0 0 0 1 0 0 00 0 1 0 0 0 0 0...以下省略解题分析：关键在于斜线还有是否访问过，正斜与反斜⾓的特点#include<bits/stdc++.h>using namespace std;int a[10001],b[10001],w[10001],m[10001],tot=0;int print(){tot++;cout<<"No. "<<tot<<endl;for(int j=1;j<=8;++j){for(int i=1;i<=8;++i)if(j==a[i])cout<<1<<" ";else cout<<0<<" ";cout<<endl;}}int search(int j){for(int i=1 ;i<=8;++i){if(b[i]==0&&w[i-j+7]==0&&m[i+j]==0){a[j]=i;b[i]=1;w[i-j+7]=1;m[i+j]=1;if(j==8) print();else search(j+1);b[i]=0;w[i-j+7]=0;m[i+j]=0;}}}int main(){search(1);return 0;}记住限制条件是该列有没访问过，还有斜⾓两个⽅向。

算法设计与分析实验报告实验名称：用回溯法解决八皇后问题姓名：学号：江苏科技大学一、实验名称：回溯法求解8皇后问题二、学习知识：回溯算法的基本思想是：从一条路往前走，能进则进，不能进则退回来，换一条路再试。

回溯法是一个既带有系统性又带有跳跃性的搜索算法。

它在包含问题的所有解的解空间树中，按照深度优先的策略，从根结点出发搜索解的空间树。

算法搜索至解的空间树的任一结点时，总是先判断该结点是否肯定不包含问题的解。

如果肯定不包含，则跳过对以该结点为根的子树的系统搜索，逐层向其祖先结点回溯。

否则，进入该子树，继续按深度优先的策略进行搜索。

回溯法在用来求问题的所有解时，要回溯到根，且根结点的所有子树都已被搜索遍才结束。

而回溯法在用来求问题的任一解时，只要搜索到问题的一个解就可以结束。

这种以深度优先的方式系统地搜索问题的解的算法称为回溯法，它适用于解一些组合数较大的问题。

三、问题描述（1）使用回溯法解决八皇后问题。

8皇后问题：在8*8格的棋盘上放置彼此不受攻击的8个皇后。

按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。

8后问题等价于在8*8格的棋盘上放置8个皇后，任何2个皇后不放在同一行或同一列或同一斜线上。

（2）用高级程序设计语言实现四、求解思路Procedure PLACE(k)//如果一个皇后能放在第k行和X(k)列，则返回true，否则返回false。

X是一个全程数组，进入此过程时已置入了k个值。

ABS(r)过程返回r的绝对值//global X(1:k); integer i,k;i←1while i<k doif X(i)=X(k) or ABS(X(i)-X(k))=ABS(i-k) thenreturn (false)end ifi←i+1repeatreturn (true)End PLACEProcedure NQUEENS(n)//此过程使用回溯法求出一个n*n棋盘上放置n个皇后，使其不能互相攻击的所有可能位置//integer k,n,X(1:n)X(1)←0 ; k←1 // k是当前行；X(k)是当前列 //while k>0 do // 对所有的行，执行以下语句 //X(k)←X(k)+1 //移到下一列//while X(k)<=n and Not PLACE(k) do //此处能放这个皇后吗//X(k)←X(k)+1 //不能放则转到下一列//repeatif X(k)<=n then //找到一个位置//if k=n then print (X) //是一个完整的解则打印这个数组// else k←k+1;X(k)←0 //否则转到下一行//end ifelse k←k-1 //回溯//end ifrepeatEnd NQUEENS五、算法实现本实验程序是使用C#编写，算法实现如下：1.queen类—实现8皇后问题的计算，将结果存入数组。

回溯法（8皇后问题）1.1算法原理回溯算法实际是一个类似枚举的搜索尝试方法，其基本思想是在搜索尝试中找问题的解，采用了一种“走不通就掉头”的思想，作为其控制结构。

从一条路往前走，能进则进，不能进则退回来，换一条路再试。

八皇后问题就是回溯算法的典型，第一步按照顺序放一个皇后，然后第二步符合要求放第2个皇后，如果没有符合条件的位置符合要求，那么就要改变第一个皇后的位置，重新放第2个皇后的位置，直到找到符合条件的位置就可以了。

回溯在迷宫搜索中使用很常见，就是这条路走不通，然后返回前一个路口，继续下一条路。

回溯算法说白了就是穷举法。

不过回溯算法使用剪枝函数，剪去一些不可能到达最终状态（即答案状态）的节点，从而减少状态空间树节点的生成。

回溯法是一个既带有系统性又带有跳跃性的的搜索算法。

它在包含问题的所有解的解空间树中，按照深度优先的策略，从根结点出发搜索解空间树。

算法搜索至解空间树的任一结点时，总是先判断该结点是否肯定不包含问题的解。

如果肯定不包含，则跳过对以该结点为根的子树的系统搜索，逐层向其祖先结点回溯。

否则，进入该子树，继续按深度优先的策略进行搜索。

回溯法在用来求问题的所有解时，要回溯到根，且根结点的所有子树都已被搜索遍才结束。

而回溯法在用来求问题的任一解时，只要搜索到问题的一个解就可以结束。

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

其一是用约束函数在扩展结点处剪去不满足约束的子树；其二是用限界函数剪去不能得到最优解的子树。

1.2算法适用性它适用于解一些组合数较大的问题，有条件限制的枚举，即优化的枚举.1.3算法描述8皇后回溯算法1.设Column[8]数组依次存储第一行到第八行的列位置，QUEEN_NUM=8，皇后个数2.从第一行第一列开始放置，开始放置下一行的皇后（当且仅当前行的皇后位置正确时）3.判断放置位置是否合理：Column[i]==Column[n]，判断是否在同一列，abs(Column[i]-Column[n])==(n-i))，判断时候在斜线上。

八皇后问题的解决完整 Standardization of sany group #QS8QHH-HHGX8Q8-GNHHJ8-HHMHGN#淮阴工学院数据结构课程设计报告设计题目：八皇后2008 年 6 月 25 日设计任务书摘要：八皇后问题要求在一个８＊８的棋盘上放上８个皇后，使得每一个皇后既攻击不到另外七个皇后，也不被另外七个皇后所攻击．按照国际象棋的规则，一个皇后可以攻击与之处在同一行或同一列或同一斜线上的其他任何棋子．因此，八皇后问题等于要求八个皇后中的任意两个不能被放在同一行或同一列或同一斜线上。

而本课程设计本人的目的也是通过用c++语言平台将一个８＊８的棋盘上放上８个皇后，使得每一个皇后既攻击不到另外七个皇后，也不被另外七个皇后所攻击的92种结构予以实现．使用递归方法最终将其问题变得一目了然，更加易懂。

关键词：八皇后 ; c++ ; 递归法目录.1. 课题综述1. 1课题的来源及意义八皇后问题是一个古老而着名的问题，该问题是十九世纪着名的数学家高斯1850年提出的。

在国际象棋中，皇后是最有权利的一个棋子；只要别的棋子在它的同一行或同一列或同一斜线（正斜线或反斜线）上时，它就能把对方棋子吃掉。

所以高斯提出了一个问题：在8*8的格的国际象棋上摆放八个皇后，使其不能相互攻击，即任意两个皇后都不能处于同一列、同一行、或同一条斜线上面，问共有多少种解法。

到了现代，随着计算机技术的飞速发展，这一古老而有趣的数学游戏问题也自然而然的被搬到了计算机上。

运用所学计算机知识来试着解决这个问题是个锻炼和提高我自己编程能力和独立解决问题能力的好机会，可以使我增强信心，为我以后的编程开个好头，故我选择了这个有趣的课题。

1. 2 面对的问题1）解决冲突问题：这个问题包括了行，列，两条对角线；列：规定每一列放一个皇后，不会造成列上的冲突；行：当第I行被某个皇后占领后，则同一行上的所有空格都不能再放皇后，要把以I为下标的标记置为被占领状态；2）使用数据结构的知识，用递归法解决问题。

算法总结
3
解决八皇后问题常用算法
3.1
枚举法解决八皇后问题
3.2
非递归回溯法解决八皇后问题
3.3
递归回溯法解决八皇后问题
3.0
八皇后问题约束条件
a( i ) 1 2 3 4 5 6 7 8 a( 1) 2 0 -1 3 -2 4 -3 5 -4 6 -5 7 -6 8 -7 9
a( 2 ) a( 3 ) a( 4) a( 5 ) a( 6) a( 7 ) a( 8)
9 3 10 2 11 1 12 0 13 -1 14 -2
9 5 10 4 11 3 12 2 13 1 14 0 15 -1
9 7 10 6 11 5 12 4 13 3 14 2 15 1 16 0
3.0
八皇后问题约束条件
a( i ) =j 第i行j列放置皇后
判断不同列 a（i）≠a（j） 判断不同对角线 i-a（i）≠j-a（j） 判断不同反对角线 i+a（i）≠j+a（j）
取下一个………………
取下一个q (1)
用语言编程
For q1 = 1 To 8 For q2 = 1 To 8 For q3 = 1 To 8 For q4 = 1 To 8 For q5 = 1 To 8 For q6 = 1 To 8 For q7 = 1 To 8 For q8 = 1 To 8 q(q1) = q1 : q(q2) = q2 : q(q3) = q3 : q(q4) = q4 q(q5) = q5 : q(q6) = q6 : q(q7) = q7 : q(q8) = q8 If putdown(q)=1 Then printstr(q) Next q8 Next q7 Next q6 Next q5 Next q4 Next q3 Next q2 Next q1

for(a[7]=1;a[7]<=8;a[7]++} )
for(a[8]=1;a[8]<=8;a[8]++){
if (check(a,8)=0) continue;
else
for(i=1;i<=8;i++)print(a[i]);
}
10
}
1 回溯法
有“通用的解题法”之称。 回溯法的基本做法是搜索，或是一种组织得井井有条
枚举得有个顺序，否则 轻则有漏的、重复的； 重则无法循环表示。
6
1.按什么顺序去查找所有的解 a.盲目的枚举算法
void main() {
int x[100]; for (x[1]=1;x[1]<=10;x[1]++) for (x[2]=1;x[2]<=10;x[2]++)
for (x[3]=1;x[3]<=10;x[3]++) for (x[4]=1;x[4]<=10;x[4]++) for (x[5]=1;x[5]<=10;x[5]++) for (x[6]=1;x[6]<=10;x[6]++) for (x[7]=1;x[7]<=10;x[7]++) for (x[8]=1;x[8]<=10;x[8]++) if (check(x)==0) { printf(x); }
}
该如何解决冲突的问题呢？
1.行；我们是按照行枚举的，保证了一行一个皇后； 2.列：判断是否存在x[i]=x[j] 3.对角线：主对角线的i-j与从对角线的i+j存在特殊关系，如 图：

⼋皇后问题—经典回溯算法⼋皇后问题⼋皇后问题，是⼀个古⽼⽽著名的问题，是回溯算法的典型案例。

该问题是国际西洋棋棋⼿马克斯·贝瑟尔于1848年提出：在8×8格的国际象棋上摆放⼋个皇后，使其不能互相攻击，即任意两个皇后都不能处于同⼀⾏、同⼀列或同⼀斜线上，问有多少种摆法。

⾼斯认为有76种⽅案。

1854年在柏林的象棋杂志上不同的作者发表了40种不同的解，后来有⼈⽤图论的⽅法解出92种结果。

回溯算法思想回溯算法的基本思想是：从⼀条路往前⾛，能进则进，不能进则退回来，换⼀条路再试。

⼋皇后问题就是回溯算法的典型，第⼀步按照顺序放⼀个皇后，然后第⼆步符合要求放第2个皇后，如果没有位置符合要求，那么就要改变第⼀个皇后的位置，重新放第2个皇后的位置，直到找到符合条件的位置就可以了。

回溯在迷宫搜索中使⽤很常见，就是这条路⾛不通，然后返回前⼀个路⼝，继续下⼀条路。

回溯算法说⽩了就是穷举法。

不过回溯算法使⽤剪枝函数，剪去⼀些不可能到达最终状态（即答案状态）的节点，从⽽减少状态空间树节点的⽣成。

回溯法是⼀个既带有系统性⼜带有跳跃性的的搜索算法。

它在包含问题的所有解的解空间树中，按照深度优先的策略，从根结点出发搜索解空间树。

算法搜索⾄解空间树的任⼀结点时，总是先判断该结点是否肯定不包含问题的解。

如果肯定不包含，则跳过对以该结点为根的⼦树的系统搜索，逐层向其祖先结点回溯。

否则，进⼊该⼦树，继续按深度优先的策略进⾏搜索。

回溯法在⽤来求问题的所有解时，要回溯到根，且根结点的所有⼦树都已被搜索遍才结束。

⽽回溯法在⽤来求问题的任⼀解时，只要搜索到问题的⼀个解就可以结束。

这种以深度优先的⽅式系统地搜索问题的解的算法称为回溯法，它适⽤于解⼀些组合数较⼤的问题。

⼋皇后实现⼆以下实现是极客时间王争的解法，⾮常巧妙，思路也⾮常清晰，如果理解了⼋皇后问题的本质后建议采⽤该⽅法，代码实现如下：#include <iostream>int queenPlace[8] = { 8 }; //全局变量，下标表⽰⾏，值表⽰queen存储在那⼀列int count = 0; //计数器void printQueen() { //打印⼀个⼆维数组for (int i = 0; i < 8; ++i) {for (int j = 0; j < 8; ++j) {if (queenPlace[i] == j) {printf("Q ");} else {printf("* ");}}printf("\n");}printf("----count:%d-----\n", ++count);}bool isOk(int row, int col) { //判断row⾏col列放置是否合适int leftUp = col - 1; //左上对⾓线int rightUp = col + 1; //右上对⾓线for (int i = row - 1; i >= 0; --i) {if (queenPlace[i] == col) return false; //同列上的格⼦有皇后if (leftUp >= 0) {if (queenPlace[i] == leftUp) return false; //左上对⾓线有皇后}if (rightUp < 8) {if (queenPlace[i] == rightUp) return false; //右上对⾓线有皇后}--leftUp; ++rightUp;}return true;}void eightQueen(int row) {if (row == 8) { //8个皇后都放置好，打印，⽆法递归返回printQueen();return;}for (int col = 0; col < 8; ++col) { //每⼀⾏都有8种⽅法if (isOk(row, col)) { //满⾜要求queenPlace[row] = col; //第row⾏的皇后放在col列eightQueen(row+1); //考察下⼀⾏}}}int main() {eightQueen(0);return0;class Solution {public:vector<vector<string>> res;vector<int> n_queen;vector<vector<string>> solveNQueens(int n) {n_queen.resize(n);backtrack(0);return res;}void backtrack(int row) {if (row == n_queen.size()) {storeResult();return;}for (int i = 0; i < n_queen.size(); ++i) {if (!isOk(row, i)) continue;n_queen[row] = i;backtrack(row + 1);}}bool isOk(int row, int col) {int left_up = col - 1;int right_up = col + 1;for (int i = row - 1; i >= 0; --i) {if (n_queen[i] == col // 当前列|| n_queen[i] == left_up-- // 左上对⾓，⽆需判断 left_up < 0, 该情况不会成⽴的 || n_queen[i] == right_up++) { // 右上对⾓，⽆需判断 right_up > n_queen.size() return false;}}return true;}void storeResult() {vector<string> result;for (auto i : n_queen) {string s(n_queen.size(), '.');s[i] = 'Q';result.push_back(s);}res.push_back(result);}};解法2：class Solution {public:vector<bool> col;vector<bool> dia1;vector<bool> dia2;vector<vector<string>> result;vector<string> generateQueen(vector<int>& q){vector<string> res;for (int i = 0; i < q.size(); ++i){string s(q.size(), '.');s[q[i]] = 'Q';res.push_back(s);}return res;}void traceBack(int n, int row, vector<int>& q){if (row == n) {result.push_back(generateQueen(q));return;}for (int i = 0; i < n; ++i){if (!col[i] && !dia1[row + i] && !dia2[row - i + n - 1]){q.push_back(i);col[i] = true;dia1[row + i] = true;dia2[row - i + n - 1] = true;traceBack(n, row + 1, q);col[i] = false;dia1[row + i] = false;dia2[row - i + n - 1] = false;q.pop_back();}}vector<vector<string>> solveNQueens(int n) { col = vector<bool>(n, false);dia1 = vector<bool>(2 * n - 1, false);dia2 = vector<bool>(2 * n - 1, false);vector<int> q;traceBack(n, 0, q);return result;}};。

若无法放下皇后则回到上一行; 即回溯
当n行的皇后都已确定后;我们就 找到了一种方案
check2 int a ;int n
queen21例1 b加约束的枚举算法{//i多nt次i; 被调用;只是一重循环
{int a9; for a1=1;a1<=8;a1++ for a2=1;a2<=8;a2++
fori=1;i<=n-1;i++ if absai-an==absi-n or ai==an
}}}}}}}
此算法可读性很好;体 现了“回溯”&但它只 能解决八皇后问题;而 不能解决任意的n皇后 问题&
18
2 回溯法应用-算法说明
八皇后问题中的核心代码： 遍历过程函数； check函数&
解决此类问题的核心内容： 解空间树的搜索算法； 估值/判断函数：判断哪些状态适合继续扩展;或者作为 答案状态&
按什么顺序去搜？ 目标是没有漏网之鱼;尽量速度快&
5
2 问题设计盲目的枚举算法
a 盲目的枚举算法
通过8重循环模拟搜索空间中的88个状态；
按枚举思想;以DFS的方式;从第1个皇后在第1列开始搜 索;枚举出所有的“解状态”：
从中找出满足约束条件的“答案状态”&
约束条件？
枚举得有个顺序;否则轻 则有漏的、重复的；重 则无法循环表示&
9
queen1 盲目的枚举算法
{ int a9;
用a1~a8存储x1~x8
for a1=1;a1<=8;a1++
for a2=1;a2<=8;a2++
for a3=1;a3<=8;a3++

八皇后问题（递归+非递归）Xredman posted @ 2009年6月04日 21:15 in 以前博文 , 442 阅读一．问题描述在8×8格的国际象棋棋盘上放置八个皇后，使得任意两个皇后不能互相攻击，即任何行、列或对角线（与水平轴夹角为45°或135°的斜线）上不得有两个或两个以上的皇后。

这样的一个格局称为问题的一个解。

请用递归与非递归两种方法写出求出八皇后问题的算法。

二．解题思路描述一个正确的解应当是每一列，每一行，每一条斜线上均只有一个皇后。

对于递归算法，本人才有模拟的方式进行，而且，我觉得开辟一个二维数组更显而易见。

首先，从空棋盘开始摆放，保证第m行m个皇后互不攻击，然后摆放第m+1个皇后。

当然对于第m+1个皇后可能有多种摆放方法，由此，我必须一一枚举，采用回溯策略是可行且合乎逻辑的。

而对于非递归算法，我只是借助于书本上一个递归改为非递归的框架，依次搭建而已。

在此过程中，我采用一维数组，一位对于八皇后问题，每一行不可能存在二个及二个以上的皇后，board[i]表示第i行棋盘摆放的位置为第board[i]列。

递归方法借助于系统提供的栈，而我非递归算法的实现，仅仅是自己构造一个栈而已。

递归解法#include <iostream>#include <cstdio>#include <sys/timeb.h>using namespace std;const int MAX_SIZE = 100;enum flag {blank ='X',queen = 1};char Chess[MAX_SIZE][MAX_SIZE];//棋盘图int n;//解决n皇后问题int total;//用于计摆放方式void Init(){//对棋牌进行初始化for(int i = 0; i < n; i++)for(int j = 0; j < n; j++)Chess[i][j] = blank;total = 0;//初始时有零中摆放方式}bool Judge(int r,int c){//判断(r,c)位置是否可放置int i,j;for(i = r + 1; i < n; i++)if(Chess[i][c] == queen)return false;//说明c列上已有一皇后for(i = c + 1; i < n; i++)if(Chess[r][i] == queen)return false;//说明r行上已有一皇后for(i = r + 1, j = c + 1; (i < n) && (j < n); i++, j++)if(Chess[i][j] == queen)return false;//45度斜线上已有一皇后for(i = r + 1, j = c - 1; (i <n) && (j >= 0); i++, j--)if(Chess[i][j] == queen)return false;//135度斜线上已有一皇后return true;//排除四种情况后，说明(r,c)点可放置皇后}void Backtrack(int k,int cnt){//回溯算法主程序if(k < 0 || cnt == n)//棋牌摆放完毕 or 以摆满n后{if(cnt == n){printf("No.%d:\n",++total);for(int i = 0; i < n; i++){for(int j = 0; j < n; j++)printf(" %c ",Chess[i][j]);putchar('\n');}putchar('\n');}}else{int r = k / n, c = k % n;if(Judge(r,c)){//可放置一皇后Chess[r][c] = queen;Backtrack(k-1,cnt+1);Chess[r][c] = blank;}Backtrack(k-1,cnt);}}int main(){//此为主函数timeb t1,t2;long kk;cout<<"输入皇后个数:";while(cin>>n){Init();ftime(&t1);Backtrack(n*n-1,0);ftime(&t2);cout<<"计算"<<n<<"后问题总共可有"<<total<<"种摆法!"<<endl;kk = (t2.time-t1.time)*1000 +litm;cout<<"本次回溯耗时:"<<kk<<"毫秒"<<endl;system("PAUSE");cout<<"输入皇后个数:";}return0;}非递归解法#include <iostream>#include <sys/timeb.h>#define N 100using namespace std;int board[N];int n,sum;void init(){for(int i = 1; i <= n; i++)board[i] = 0;}void display(){int i,j;cout<<"No."<<sum<<endl;for(i = 1; i <= n; i++){for(j = 1; j <= n; j++)if(board[i] == j)cout<<"Q ";elsecout<<"X ";cout<<endl;}cout<<endl;}bool canPut(int k){for(int i = 1; i < k; i++)if((abs(k - i) == abs(board[k] - board[i])) || board[i] == board[k])return false;//1.是否在同一斜线;2.是否位于同一列return true;}void Backtrack(){board[1] = 0;int k = 1;while(k > 0){board[k]++;while((board[k] <= n) && !(canPut(k)))board[k] += 1;if(board[k] <= n)if(k == n){sum++;display();}else{k++;board[k] = 0;}elsek--;}}int main(){timeb t1,t2;long kk;cout<<"输入皇后个数:";while(cin>>n){init();sum = 0;ftime(&t1);Backtrack();ftime(&t2);cout<<"总共排列方式为:"<<sum<<endl;kk = (t2.time-t1.time)*1000 + litm; cout<<"本次回溯耗时:"<<kk<<"毫秒"<<endl;system("PAUSE");cout<<"输入皇后个数:";}return0;}。

枚举得有个顺序，否则 轻则有漏的、重复的； 重则无法循环表示。
6
1.按什么顺序去查找所有的解 a.盲目的枚举算法
void main() {
int x[100]; for (x[1]=1;x[1]<=10;x[1]++)
for (x[2]=1;x[2]<=10;x[2]++) for (x[3]=1;x[3]<=10;x[3]++) for (x[4]=1;x[4]<=10;x[4]++) for (x[5]=1;x[5]<=10;x[5]++) for (x[6]=1;x[6]<=10;x[6]++) for (x[7]=1;x[7]<=10;x[7]++) for (x[8]=1;x[8]<=10;x[8]++) if (check(x)==0) { printf(x); }
}
10
1 回溯法
有“通用的解题法”之称。 回溯法的基本做法是搜索，或是一种组织得井井有条
的，能避免不必要搜索的穷举式搜索法。这种方法适 用于解一些组合数相当大的问题。 回溯法在问题的解空间树中，按深度优先策略，从根 结点出发搜索解空间树。算法搜索至解空间树的任意 一点时，先判断该结点是否包含问题的解。如果肯定 不包含，则跳过对该结点为根的子树的搜索，逐层向 其祖先结点回溯；否则，进入该子树，继续按深度优 先策略搜索。
按什么顺序去搜？ 目标是没有漏网之鱼，尽量速度快。
5
2 【问题设计】盲目的枚举算法
a 盲目的枚举算法 通过8重循环模拟搜索空间中的88个状态； 按枚举思想，以DFS的方式，从第1个皇后在第1列开始 搜索，枚举出所有的“解状态”：

八皇后问题
1
1八皇后问题背景 2盲目的枚举算法 3加约束的枚举算法 4回溯法及基本思想 5 回溯法应用 6八皇后问题的递归回溯算法 7八皇后问题的非递归回溯算法
2
【背景】 八皇后问题是一个以国际象棋为背
景的问题： 如何能够在 8×8 的国际象棋棋盘上
放置八个皇后，使得任何一个皇后都 无法直接吃掉其他的皇后？为了达到 此目的，任两个皇后都不能处于同一 条横行、纵行或斜线上。
}
}
23
20
2 回溯法应用-算法框架-递归算法框架
int a[n]; Queens(int k) { if (k>n) 即表示最后一个皇后摆放完毕，输出结果;
else for(i=下界 ; i<=上界; i++) //枚举K个皇后所有可能的路径 {依次从列顶端开始搜索，一直到列底端，直到找到合适位置,如
果未找到，自动返回上层递归
的，能避免不必要搜索的穷举式搜索法。这种方法适 用于解一些组合数相当大的问题。 回溯法在问题的解空间树中，按深度优先策略，从根 结点出发搜索解空间树。算法搜索至解空间树的任意 一点时，先判断该结点是否包含问题的解。如果肯定 不包含，则跳过对该结点为根的子树的搜索，逐层向 其祖先结点回溯；否则，进入该子树，继续按深度优 先策略搜索。
for(a[8]=1;a[8]<=8;a[8]++) 此算法可读性很好，
{if (check(a,8)==0)continue; 体现了“回溯”。但
else for(i=1;i<=8;i++) 它只能解决八皇后问
print(a[i]); }
题，而不能解决任意
}}}}}}}