八皇后问题讲解

算法——⼋皇后问题（eightqueenpuzzle）之回溯法求解⼋皇后谜题是经典的⼀个问题，其解法⼀共有92种！其定义：1. ⾸先定义⼀个8*8的棋盘2. 我们有⼋个皇后在⼿⾥，⽬的是把⼋个都放在棋盘中3. 位于皇后的⽔平和垂直⽅向的棋格不能有其他皇后4. 位于皇后的斜对⾓线上的棋格不能有其他皇后5. 解出能将⼋个皇后都放在棋盘中的摆法这个问题通常使⽤两种⽅法来求解：1. 穷举法2. 回溯法（递归）本⽂章通过回溯法来求解，回溯法对⽐穷举法⾼效许多，让我们学习如何实现吧！实现思想：1. 我们先在棋盘的第0⾏第1个棋格放下第⼀个皇后2. 下⼀⾏寻找⼀个不冲突的棋格放下下⼀个皇后3. 循环第2步4. 如果到某⼀⾏全部8个格⼦都⽆法放下皇后，回溯到前⼀⾏，继续寻找下⼀个不冲突的棋格5. 把8个皇后都放在棋盘之后，输出或存储摆法，结束实现（Java）算法：定义棋盘我们通过⼀个⼆维整型数组表⽰⼀个棋盘数组内为1是放下了的皇后，0则是空⽩的棋格我们下下⾯定义⼀个⽅法：通过检查棋格是否为1来知道是不是有皇后1// 定义⼀个棋盘2static int chessboard[][] = new int[8][8];检查冲突这个⽅法⽤来检查冲突：在⽔平垂直⽅向、斜⾓上的棋格有⽆其他皇后，传⼊的（x,y）是需要检查的棋格，如检查棋格（1,0）即棋盘的第2⾏第1个，是否能放下皇后。

1// 检查是否符合规则2private static boolean checked(int x,int y){3for(int i = 0;i<y;i++){4// 检查⽔平垂直⽅向5if(chessboard[x][i]==1)return false;6// 检测左斜⾓7if((x-y+i>=0)&&chessboard[x-y+i][i]==1)return false;8// 检查右斜⾓9if((x+y-i<=7)&&chessboard[x+y-i][i]==1)return false;10 }11return true;12 }放下皇后我们在每⼀⾏都执⾏以下步骤，通过从第1个棋格到第8个遍历寻找可以放下皇后的棋格如果放下了皇后，我们就可以继续放下下⼀个了，将⾏数+1，我们递归调⽤这个⽅法1public static boolean solve(int y){2// 将⼀⾏的8种情况都扫描⼀次3for(int i = 0;i<8;i++){4// 每次检测前都将当前⾏清空,避免脏数据5for(int k = 0;k<8;k++)chessboard[k][y]=0;6if(checked(i, y)){7 chessboard[i][y] = 1;8// 当前⼀⾏已经获得解法,进⼊下⼀⾏9 solve(y+1);10 }11 }12return false;13 }算法边界当我们放下了所有8个皇后后，需要⼀个终⽌条件，我们在⾏数y=8时，结束算法同时你可以输出⼀个棋盘摆法了！恭喜你已经把这个经典问题解决了！1// 当y=8时,已经找到⼀种解决⽅法2if(y == 8){3return true;4 }以下是完整的算法1public class EightQueen{2// 定义⼀个棋盘3static int chessboard[][] = new int[8][8];4// 计数器5static int count = 0;67// 解题⽅法8public static boolean solve(int y){9// 当y=8时,已经找到⼀种解决⽅法,计数器加⼀并输⼊摆法10if(y == 8){11 System.out.println("solved!");12 show();13 count++;14return true;15 }16// 将⼀⾏的8种情况都扫描⼀次17for(int i = 0;i<8;i++){18// 每次检测前都将当前⾏清空,避免脏数据19for(int k = 0;k<8;k++)chessboard[k][y]=0;20if(checked(i, y)){21 chessboard[i][y] = 1;22// 当前⼀⾏已经获得解法,进⼊下⼀⾏23 solve(y+1);24 }25 }26return false;27 }28// 检查是否符合规则29private static boolean checked(int x,int y){30for(int i = 0;i<y;i++){31// 检查垂直⽅向32if(chessboard[x][i]==1)return false;33// 检测左斜⾓34if((x-y+i>=0)&&chessboard[x-y+i][i]==1)return false;35// 检查右斜⾓36if((x+y-i<=7)&&chessboard[x+y-i][i]==1)return false;37 }38return true;39 }40// 输出棋盘摆法41public static void show(){42for(int i = 0;i<8;i++){43for(int j = 0;j<8;j++){44 System.out.print(chessboard[j][i]+" ");45 }46 System.out.println("");47 }48 }49 }在执⾏这个算法后：have 92 ways to sovle it!我们获得了92种棋盘摆法！。

⼋皇后问题（经典算法-回溯法）问题描述：⼋皇后问题（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;}。

八皇后问题有多少解八皇后问题有92解。

皇后可以在横、竖、斜线上不限步数地吃掉其他棋子。

如何将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 的皇后串//输入样例//2//1//92//输出样例//15863724//84136275解题思路一因为要求出92种不同摆放方法中的任意一种，所以我们不妨把92种不同的摆放方法一次性求出来，存放在一个数组里。

为求解这道题我们需要有一个矩阵仿真棋盘，每次试放一个棋子时只能放在尚未被控制的格子上，一旦放置了一个新棋子，就在它所能控制的所有位置上设置标记，如此下去把八个棋子放好。

当完成一种摆放时，就要尝试下一种。

若要按照字典序将可行的摆放方法记录下来，就要按照一定的顺序进行尝试。

也就是将第一个棋子按照从小到大的顺序尝试；对于第一个棋子的每一个位置，将第二个棋子从可行的位置从小到大的顺序尝试；在第一第二个棋子固定的情况下，将第三个棋子从可行的位置从小到大的顺序尝试；依次类推。

首先，我们有一个8*8的矩阵仿真棋盘标识当前已经摆放好的棋子所控制的区域。

用一个有92行每行8个元素的二维数组记录可行的摆放方法。

用一个递归程序来实现尝试摆放的过程。

基本思想是假设我们将第一个棋子摆好，并设置了它所控制的区域，则这个问题变成了一个7皇后问题，用与8皇后同样的方法可以获得问题的解。

八皇后问题是一个古老而著名的问题，是回溯算法的典型例题。

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

高斯认为有76种方案。

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

现代教学中，把八皇后问题当成一个经典递归算法例题。

——引用自百度百科首先，可归纳问题的条件为，8皇后之间需满足：1.不在同一行上2.不在同一列上3.不在同一斜线上4.不在同一反斜线上这为我们提供一种遍历的思路，我们可以逐行或者逐列来进行可行摆放方案的遍历，每一行（或列）遍历出一个符合条件的位置，接着就到下一行或列遍历下一个棋子的合适位置，这种遍历思路可以保证我们遍历过程中有一个条件是绝对符合的——就是下一个棋子的摆放位置与前面的棋子不在同一行（或列）。

接下来，我们只要判断当前位置是否还符合其他条件，如果符合，就遍历下一行（或列）所有位置，看看是否继续有符合条件的位置，以此类推，如果某一个行（或列）的所有位置都不合适，就返回上一行（或列）继续该行（或列）的其他位置遍历，当我们顺利遍历到最后一行（或列），且有符合条件的位置时，就是一个可行的8皇后摆放方案，累加一次八皇后可行方案的个数，然后继续遍历该行其他位置是否有合适的，如果没有，则返回上一行，遍历该行其他位置，依此下去。

这样一个过程下来，我们就可以得出所有符合条件的8皇后摆放方案了。

这是一个深度优先遍历的过程，同时也是经典的递归思路。

接下来，我们以逐列遍历，具体到代码，进一步说明。

首先，从第一列开始找第一颗棋子的合适位置，我们知道，此时第一列的任何一个位置都是合适的，当棋子找到第一个合适的位置后，就开始到下一列考虑下一个合适的位置，此时，第二列的第一行及第二行显然就不能放第二颗棋子了，因为其与第一个棋子一个同在一行，一个同在一条斜线上。

一．八皇后问题八皇后背景知识国际象棋中皇后威力很大，它可以象“车”一样沿直线上下或左右移动；也可以如同“象”那样沿着斜线移动。

双方的皇后是不能在同一行或同一列或同一斜线上对持的。

那么，在一张空白的国际象棋盘上最多可以放上几个皇后并且不让它们互相攻击呢？这个问题是伟大数学家高斯在十九世纪中期提出来的，并作了部分解答。

高斯在棋盘上放下了八个互不攻击的皇后，他还认为可能有76种不同的放法，这就是有名的“八皇后”问题。

现在我们已经知道八皇后问题有92个解答。

那么你能试着找出几种方法吗？如果你动手试试，就一定会发现开头几颗皇后很容易放置，越到后来就越困难。

由于我们的记忆有限，很可能在某个位置放过子后来证明不行取消了，但是以后又重新放上子去试探，这样就会不断地走弯路，花费大量的精力。

因此，必须找到一个简易有效、有条不紊的法则才行。

1.1分析1.1.1问题描述：八皇后问题是想把八个皇后放在一个棋盘上，并且她们之间不会相互攻击。

按照国家象棋的规则，皇后可以吃掉任何一个和她处在同一行、同一列、或同一斜线（包括两条对角线）上的其他棋子。

如图下所示，皇后所在的行、列及对角线（如图中斜线所示）对其他棋子都是不安全的，而其他地方的棋子则不会受到皇后的威胁。

因此，一个皇后放好以后，它所在的列、行、两条对角线上的地方都不能放其他棋子。

根据这个规则，我们可以利用一个函数来判断某个位置是否安全，安全的位置说明它所在的同一行、同一列或两条线上都没有放置过皇后，因此不会出现皇后互相攻击的情况；否则该位置不安全。

其具体实现过程是找出所有放置的皇后，将他们的位置与该位置进行比较判断。

又注意到同一行只能放一个皇后，因此，只需要对前面的各行逐行扫描皇后，就可以找出所有皇后的位置。

下图是其中一种摆放皇后的方法：1.1.2基本要求：编写实现八皇后问题的非递归解法，输出八皇后问题的中所有摆放皇后的方法，使它可以满足条件。

1.2课程设计目的：深入理解数据结构的基本理论，掌握数据存储结构的设计方法，掌握基于数据结构的各种操作的实现方法，训练对基础知识和基本方法的综合运用能力，增强对算法的理解能力，提高软件设计能力。

递归算法——八皇后问题1、背景问题描述八皇后问题是一个古老而著名的问题，该问题的目标是在8×8的国际象棋棋盘上放置八个皇后，使得任意两个皇后都不在同一行，或同一列或同一对角线上。

如图1所示就是八皇后问题的一个解。

图1 八皇后问题的一个解1854年在柏林的象棋杂志上不同的作者发表了40种不同的解。

大数学家高斯认为有76种不同的方案。

后来有人用图论的方法算出92种不同的解。

能否利用程序算出所有满足条件的解的数目呢？2、抽象表示及存储对于这种矩形排列的棋盘而言，用二维数组存储棋盘的状况是最容易想到的方法。

可以设置一个8*8的二维数组，令有棋子的位置为1，无棋子的部分为0。

事实上，由于8个皇后中任意两个皇后都不在同一行，因此8个皇后只能各自占据一行。

不妨认为8个皇后编号为0、1、……、7，它们各自占据棋盘的第1行、第2行、……、第8行。

从而可以使用长度为8一维数组表示棋盘状态，数组元素的下标表示棋子所在行，数组元素的值表示各个棋子所在的列。

使用的存储方式不同，其采用的算法已有很大区别。

3、问题分析及算法设计假定用二维数组A存储棋盘的情况，可以考虑下面两种思路。

思路一：不考虑任何限制的穷举法。

用8×8的二维数组存储棋盘，若在(i,j)处有子，则令A[i][j]=1，否则A[i][j]=0。

于是8个棋子第1个有64种摆放方法，第2个有63种放法，……，第8个有57种放法，则所有摆放方法有64×63×62×…×57种。

可以列举每一种摆法，而后考察每种方法是否符合条件。

这个计算量非常大。

思路二：考虑经过优化的穷举法(二维数组方案)。

若8个棋子位于8行8列的棋盘中，要求任意两个不同行、不同列，则任一解必然是各行、各列只包含一个棋子，其它情况必然不是解。

于是可以做个8重循环，把每个皇后安排在每行的每个位置都试一遍。

算法如下：将整个棋盘数组赋值为0；for(1号皇后从1行1列到1行8列){将1号皇后能控制的线路(横向、竖线、斜线)全部设为1；for(2号皇后从2行1列到2行8列){if(2号皇后控制的线路全部为0){将2号皇后能控制的线路(横向、竖线、斜线)全部设为2；for(3号皇后从3行1列到3行8列){if(3号皇后控制的线路全部为0){将3号皇后能控制的线路全部设为3；……for(8号皇后从8行1列到8行8列){if(8号皇后控制的线路全部为0){将8号皇后能控制的线路全部设为8；记录该棋盘为一个解；}将8号皇后控制的线路全部恢复为0；}……}将3号皇后控制的线路全部恢复为0；}}将2号皇后控制的线路全部恢复为0；}将1号皇后控制的线路全部恢复为0}上述算法中的多重循环虽易于理解，但程序嵌套结构较为复杂，形式死板，不易扩展。

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

该问题是国际西洋棋棋⼿马克斯·贝瑟尔于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;}};。

八皇后问题1、问题描述八皇后问题是一个古老而著名的问题，该问题是由十九世纪著名的数学家高斯1850年提出的。

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

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

2、设计思路1）解决行、列、斜线的冲突行：当第i行被某个皇后占领后，则同一行上的所有空格都不能再放皇后，还要把以i为下标的位置标记为已占领列：规定每一列放置一个皇后，保证不会造成列上的冲突对角线：对角线有正对角线和反对角线两个方向。

当第i个皇后占领了第j列后，要同时把以(i+j)、(i-j)为下标的位置标记为已占领2）数据结构的实现数组a[i]：a[i]表示第i个皇后放置的列(1<=i<=8)对角线数组：b[j](正对角线),c[j](反对角线)，根据程序决定正反对角线是否放入皇后3、数据结构设计int Count=0;/*记录解的序号*/int Site[QUEENS]; /*记录皇后放置在各行的位置*/void Queen(int n);/*递归求解函数*/{ int i;if(n==QUEENS){ Output();return;}}void Output();/*输出一个解法*/{ int i;for(i=0;i<QUEENS;i++)/*依次输出各行上皇后的位置*/}int IsValid(int n); /*判断第n个皇后放后，是否有冲突*/ { int i;for(i=0;i<n;i++) /*将第n个皇后和前面n－1个皇后比较*/ { if(Site[i]==Site[n])/*两个皇后在同一列上，返回0*/return 0;if(abs(Site[i]-Site[n])==(n-i))/*两个皇后在同一对角线上，返回0*/return 0;}return 1; /*没有冲突，返回1*/}4、功能函数设计1）求解函数void Queen(int n):递归放置第n个皇后，判断第n个皇后放上去之后，是否无冲突。

目录一需求分析 (1)1.1程序的功能： (1)1.2程序的输入输出要求： (1)二概要设计 (3)2.1程序的主要模块： (3)2.2程序涉及： (3)三详细设计 (3)3.1相关代码及算法 (4)3.1.1 定义相关的数据类型如下：....................... 错误!未定义书签。

3.1.2 主模块类C码算法： (4)3.1.3 画棋盘模块类C码算法 (5)3.1.4 画皇后模块类C码算法： (5)3.1.5 八皇后摆法模块（递归法）： (6)3.1.6 初始化模块 (7)3.1.7 输出摆放好的八皇后图形（动态演示）： (7)3.2相关流程图 (9)四调试分析 (12)五设计体会 (13)六附录 (13)七参考文献 (17)一需求分析1.1 程序功能：八皇后问题是一个古老而著名的问题。

该问题是十九世纪著名的数学家高斯1850年提出的。

八皇后问题要求在一个８＊８的棋盘上放上８个皇后，使得每一个皇后既攻击不到另外七个皇后，也不被另外七个皇后所攻击．按照国际象棋的规则，一个皇后可以攻击与之处在同一行或同一列或同一斜线上的其他任何棋子，问有多少种不同的摆法？并找出所有的摆法。

因此，八皇后问题等于要求八个皇后中的任意两个不能被放在同一行或同一列或同一斜线上。

本程序通过对子函数void qu(int i)的调用，将八皇后的问题关键通过数据结构的思想予以了实现。

虽然题目以及演算看起来都比较复杂，繁琐，但在实际中，只要当一只皇后放入棋盘后，在横与列、斜线上没有另外一只皇后与其冲突，再对皇后的定位进行相关的判断。

即可完成。

如果在这个程序中，我们运用的是非递归的思想，那么将大量使用if等语句，并通过不断的判断，去推出答案，而且这种非递归的思想，大大的增加了程序的时间复杂度。

如果我们使用了数据结构中的算法后，那么程序的时间复杂度，以及相关的代码简化都能取得不错的改进。

这个程序，我运用到了数据结构中的栈、数组，以及树和回溯的方法。

八皇后问题一、问题描述八皇后问题是一个古老而著名的问题，是回溯算法的典型例题。

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

二、问题分析在一个８×８的棋盘里放置８个皇后，要求每个皇后两两之间不相"冲"（在每一横列竖列斜列只有一个皇后）。

1、冲突。

包括行、列、两条对角线：（1）列：规定每一列放一个皇后，不会造成列上的冲突；（2）行：当第I行被某个皇后占领后，则同一行上的所有空格都不能再放皇后，要把以I为下标的标记置为被占领状态；（3）对角线：对角线有两个方向。

在同一对角线上的所有点（设下标为(i,j)），要么(i+j)是常数，要么(i-j)是常数。

因此，当第I个皇后占领了第J列后，要同时把以(i+j)、(i-j)为下标的标记置为被占领状态。

三、基本解决思路八皇后问题主要靠回溯的方法实现, 与迷宫的实现相似, 但又困难了一些. 如迷宫的路径不因为上一步而改变, 八皇后的每一步都受约束于以前的步数, 并且, 迷宫只要找出一条路径就行,但八皇后则有很多的解法.基本思想是从n列开始摆放第n个皇后（因为这样便可以符合每一竖列一个皇后的要求），先测试当前位置(n,m)是否等于０（未被占领）:如果是，摆放第n个皇后，并宣布占领(记得要横列竖列斜列一起来哦)，接着进行递归；如果不是，测试下一个位置(n,m+1)，但是如果当n<=8,m=8时，却发现此时已经无法摆放时，便要进行回溯。

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) ;返回存储区域所需字节数。

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

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

⾼斯认为有76种⽅案。

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

计算机发明后，有多种⽅法可以解决此问题。

摘⾃百度百科解题思路:深度搜索加记忆数组*因为皇后不能处于同⼀⾏,同⼀列,同⼀斜线(即主对⾓线和副对⾓线),所以可以判断出8个皇后分别各占⼀⾏*不妨假设从第⼀⾏开始,⾏数依次加⼀确定每⼀⾏皇后的位置,在下⾯的程序中cur代表⾏号,因为我们依次让*⾏号加⼀,所以不会存在⾏号重叠的现象,接下来只需判断列数和对⾓线没有发⽣重叠即可,这⾥,我们⽤⼀个记*忆状态的数组(vis[][])来存储列和对⾓线的状态,每次确定⼀个皇后的位置,⾸先判断其对应的列和对⾓线是否*染⾊,如果没有染⾊,则该位置有效,并染⾊,这样就不会出现列和对⾓线重叠的问题.下⾯重点讲解⼀下对⾓线,其原理可⽤下图说明：(格⼦(i-j)的值标⽰了主对⾓线)同理读者⾃⾏可以推出(格⼦(i+j)的值标⽰了副对⾓线)⼜因为主对⾓线的值有为负数的情况,所以我们在标记的时候应该加>=7的数,所有值都加了>=7所以标记的效果并没有改变1 #include<iostream>2usingnamespace std;3bool vis[3][30];//记忆数组判断列,主对⾓线,副对⾓线是否被占4int ans=0;5void dfs(int cur)6 {7if(cur==9)//如果当前⾏数超过8(表明⼋个皇后已经放好)则结果加⼀，返回继续递归8 {9 ans++;10return ;11 }12//vis[0][i]判断列,vis[i][cur-i+8]判断主对⾓线,vis[2][cur+i]判断副对⾓线13for(int i=1;i<=8;i++)if(!vis[0][i]&&!vis[1][cur-i+8]&&!vis[2][cur+i])14 {15 vis[0][i]=vis[1][cur-i+8]=vis[2][cur+i]=true;16 dfs(cur+1);//深度搜索17 vis[0][i]=vis[1][cur-i+8]=vis[2][cur+i]=false;18 }19 }20int main()21 {22 dfs(1);//初始化cur为1,即从第⼀⾏开始23 cout<<"有 "<<ans<<" 种结果."<<endl;24 system("pause");25return0;26 }。

1213：⼋皇后问题⾸先可以试图去简化问题，将问题转化为为每⼀列确定⼀个有效的⾏号。

因为同⼀列只能有⼀个皇后，并且需要在⼋列中确定⼋个皇后，即每⼀列都必定有且只有⼀个皇后。

经过简化后，显然，通过⼀个⼀维数组即可以确定⼀组有效解。

关于check：不为同⼀⾏或同⼀列的判定⽐较简单（这⾥省略）（i1，j1）与（i2，j2）在同⼀条斜线上的判定：i1-i2==j1-j2 || i1-i2==j2-j1问题经过这样⼀次抽丝剥茧后，剩余的思路⼤致就是深度搜索、临界输出。

特别重复：a[j]表⽰第j列的皇后所在的⾏数1 #include<iostream>2 #include<cstdio>3using namespace std;45const int N=10;6int ans,a[N];7void print(){8 printf("No. %d\n",++ans);9for(int i=1;i<=8;i++){10for(int j=1;j<=8;j++)11if(a[j]==i)printf("1 ");12else printf("0 ");13 printf("\n");14 }15 }16bool check(int x,int d){17for(int i=1;i<d;i++){18if(a[i]==x||x-a[i]==d-i||x-a[i]==i-d)19return0;20 }21return1;22 }23void solve(int d){24if(d==9){25 print();26return;27 }28for(int i=1;i<=8;i++){29if(check(i,d)){30 a[d]=i;31 solve(d+1);32 }33 }34 }35int main(){36 solve(1);37return0;38 }。