递归解决八皇后以及汉诺塔迷宫源码

八皇后问题c语言代码讲解八皇后问题是一个经典的回溯算法问题，要求在一个8x8的棋盘上放置8个皇后，使得它们互不攻击，即任意两个皇后都不能在同一行、同一列或同一对角线上。

下面是一个使用C语言实现八皇后问题的代码示例：c.#include <stdio.h>。

#define N 8。

int board[N][N];// 检查当前位置是否安全。

int isSafe(int row, int col) {。

int i, j;// 检查当前列是否有皇后。

for (i = 0; i < row; i++) {。

if (board[i][col] == 1) {。

return 0;}。

}。

// 检查左上对角线是否有皇后。

for (i = row, j = col; i >= 0 && j >= 0; i--, j--) {。

if (board[i][j] == 1) {。

return 0;}。

}。

// 检查右上对角线是否有皇后。

for (i = row, j = col; i >= 0 && j < N; i--, j++) {。

if (board[i][j] == 1) {。

return 0;}。

}。

return 1;}。

// 在当前行放置皇后。

int solve(int row) {。

int col;// 所有行都放置完毕，打印结果。

if (row == N) {。

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

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

printf("%d ", board[i][j]); }。

printf("\n");}。

printf("\n");return 1;}。

// 逐列尝试放置皇后。

for (col = 0; col < N; col++) {。

java递归求⼋皇后问题解法⼋皇后问题⼋皇后问题，是⼀个古⽼⽽著名的问题，是回溯算法的典型案例。

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

⾼斯认为有76种⽅案。

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

⽹上有很多⼋皇后的⼩游戏，不清楚规则的可以体验⼀把。

递归理解由于我们使⽤经典的递归回溯算法，所以要先理解递归的调⽤过程，在使⽤递归前我们先看下普通⽅法的调⽤过程在JVM中如何体现。

⾸先我们来看下jvm中五个重要的空间，如下图所⽰这⾥我们主要关注栈区，当调⽤某个⽅法时会在栈区为每个线程分配独⽴的栈空间,⽽每个⽅法都会以栈帧的形式压⼊栈中，即每个⽅法从进⼊到退出都对应着⼀个栈帧的压栈和出栈。

如下图所⽰在每个栈帧中都会有⽅法独⽴的局部变量表，操作数栈，动态连接，返回地址等信息。

如下图所⽰理解了jvm程序栈的结构后，下⾯我们以图解的⽅式先讲解⼀下普通⽅法(理解普通⽅法调⽤过程后，再讲解递归的调⽤过程)的调⽤过程。

假设程序main⽅法⾸先调⽤了method1，在method1中调⽤了method2，在method2中调⽤method3。

代码如下1public static void main(String []args){2 method1();3 }5private static void method1(){6 System.out.println("method1调⽤开始");7 method2();8 System.out.println("method1调⽤结束");9 }1011private static void method2(){12 System.out.println("method2调⽤开始");13 method3();14 System.out.println("method2调⽤结束");15 }16private static void method3(){17 System.out.println("method3调⽤开始");18 System.out.println("method3调⽤结束");19 } 当执⾏main⽅法时，会执⾏以下步骤 1）⾸先将main⽅法压⼊栈中，在main⽅法中调⽤method1，⽅法mehod1会压⼊栈中，并执⾏打印“method1调⽤开始” 2）执⾏到第7⾏时，将method2压⼊栈中，执⾏method2⽅法的代码打印出“method2调⽤开始” 3）执⾏到第13⾏时调⽤method3⽅法，将method3⽅法压⼊栈中，执⾏method3⽅法打印“method3调⽤开始”，⽅法压⼊栈中的过程图解，如下图所⽰ 当执⾏到图4中的method3⽅法打印出“method3调⽤开始”后会执⾏以下步骤 1）method3执⾏打印“method3调⽤结束”后method3⽅法体已全部执⾏完毕，method3⽅法会出栈，并根据栈帧中程序计数器记录的调⽤者调⽤本⽅法的所在⾏返回。

⼋皇后问题的相关C++代码解答⽰例⼋皇后问题即指在⼀个8*8的棋盘上放置8个皇后，不允许任何两个皇后在棋盘的同⼀⾏、同⼀列和同⼀对⾓线上。

关键字：递归、上溯.通⽤技巧：经观察发现，对8 x 8的⼆维数组上的某点a[i][j](0<=i,j<=7)其主对⾓线（即左上⾄右下）上的每个点的i-j+7的值（范围在(0,14)）均相等；其从对⾓线（即右上⾄左下）上的每个点的i+j的值（范围在(0,14)）均相等；且每个主对⾓线之间的i-j+7的值均不同，每个从对⾓线之间的i-j+7的值亦不同；如a[3][4]:主：3-4+7=6从：3+4=7因此可设两个数组b[15],c[15]分别表⽰主、从对⾓线是否安全（为1表⽰有皇后，不安全；为0表⽰安全）每⾏有且仅有⼀个皇后：每i个皇后放在每i⾏(0<=i<=7)void eightQueens( int line );题⽬描述：会下国际象棋的⼈都很清楚：皇后可以在横、竖、斜线上不限步数地吃掉其他棋⼦。

如何将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的皇后串。

样例输⼊：2192样例输出：1586372484136275思路先贴出⼀个可以ac的摆放位置出来，防⽌⼤家连国际象棋棋盘的样⼦都不清楚。

由于⼋个皇后不能处在同⼀⾏，那么可以肯定每个皇后占据⼀⾏。

c语言递归函数实现汉诺塔汉诺塔问题是一个经典的递归问题，它可以用来展示递归的思想和实现。

在这个问题中，我们有三根柱子和一些圆盘，圆盘在柱子上，每个圆盘的大小不同，较小的在较大的上面。

目标是将所有的圆盘从一个柱子移动到另一个柱子上，同时遵守以下几个规则：1.每次只能移动一个圆盘；2.每次移动时，圆盘都必须放置在更大的圆盘上；3.圆盘只能从最上面移动；4.可以利用剩余的柱子作为辅助。

这个问题可以使用递归算法来解决，下面我们来看一下如何在C语言中实现。

首先，我们需要定义一个递归函数来解决汉诺塔问题。

这个函数将接受四个参数：圆盘数量n，起始柱子源(source)，辅助柱子auxiliary和目标柱子destination。

函数的目标是将n个圆盘从源柱子移动到目标柱子上。

```cvoid hanoi(int n, char source, char auxiliary, char destination) {//终止条件：当只有一个圆盘时，直接将它从源柱子移到目标柱子上if (n == 1) {printf("将圆盘从%c移动到%c\n", source, destination);return;}//递归步骤：将n-1个圆盘从源柱子移动到辅助柱子上hanoi(n-1, source, destination, auxiliary);//将第n个圆盘从源柱子移动到目标柱子上printf("将圆盘从%c移动到%c\n", source, destination);//将n-1个圆盘从辅助柱子移动到目标柱子上hanoi(n-1, auxiliary, source, destination);```在这个递归函数中，当n等于1时，表示只剩下一个圆盘，此时直接将其从源柱子移动到目标柱子上。

否则，我们首先递归地将n-1个圆盘从源柱子移动到辅助柱子上，然后将第n个圆盘从源柱子移动到目标柱子上，最后再将n-1个圆盘从辅助柱子移动到目标柱子上。

python八皇后问题递归算法Python八皇后问题递归算法是一种经典的算法，用于解决八皇后问题。

八皇后问题是一个典型的回溯算法问题，其目标是在一个8x8 的棋盘上放置 8 个皇后，使得每个皇后都不会攻击到其他的皇后。

在这个问题中，皇后可以攻击到同一行、同一列和同一对角线上的其他皇后。

因此，要解决这个问题，我们需要找到一种方法，使得每个皇后都能够在不攻击其他皇后的情况下放置在棋盘上。

递归算法是解决八皇后问题的一种常用方法。

在这种算法中，我们首先将皇后放置在第一行中的每个位置上，并递归地放置下一行的皇后，直到我们找到一种方案，其中每个皇后都不会攻击到其他皇后。

如果我们无法找到这样的方案，我们将回溯到前一行，并将前一行中的皇后移动到下一个位置上，继续递归寻找方案。

Python语言提供了丰富的库函数和语法特性，使得编写八皇后问题递归算法变得非常容易。

我们可以使用Python中的列表和循环语句来表示棋盘和皇后的位置，并使用递归函数来实现放置皇后和检查皇后位置的功能。

在编写递归函数时，我们需要注意以下几点：1. 递归函数的参数应该包括皇后的位置和当前行数。

2. 在放置皇后时，我们应该从左到右遍历每一列，并在每一列中检查皇后是否会攻击到其他皇后。

3. 如果当前行数达到8，说明我们已经找到了一种合法的方案，我们应该将其保存下来，并返回True，表示我们已经找到了一种方案。

4. 如果我们无法找到合法的方案，我们应该返回False，表示我们需要回溯到前一行。

最后，我们可以通过调用递归函数来解决八皇后问题，并输出所有合法的方案。

通过使用Python八皇后问题递归算法，我们可以更好地理解回溯算法和递归算法的工作原理，并提高我们的编程能力。

八皇后的递归和非递归的解法（C++）八皇后的递归和非递归的解法(C++)//描述：用递归和非递归模拟n皇后问题//输入：问题的规模:n//输出：皇后放置的方法排列和总数#include<iostream>#include<iomanip>#include<cmath>#include<stack>using namespace std;//利用递归求解皇后问题 x[i]表示皇后放在第i行第x[i]列static int count;//判断如果皇后放在第i行，第j列是否与前面的皇后冲突bool place(int i,int j,int* path)//path存放路径{int row;for(row=0;row<i;row++){if(abs(row-i)==abs(path[row]-j))//在同一条斜线上return false;if(j==path[row])//在同一列return false;}return true;}//利用递归来求解，而且当row==0时，即求解全局的解//path[n]用来存放路径void queen(int row,int* path,int n)if(row==n){//输出结果，并将办法数加1for(int i=0;i<n;i++){cout<<setw(5)<<left<<path[i];}cout<<endl;count++;}else{int j;//表示当前列是否可行for(j=0;j<n;j++){//如果可行，则放置并且递归调用处理下一行if(place(row,j,path)){path[row]=j;//这里相当于入栈的过程queen(row+1,path,n);}}}}//利用迭代来求解void queen_another(int n,int* path) {int i=0;for(i=0;i<n;i++){int j=0;for(;j<n;j++){if(place(i,j,path)){path[i]=j;cout<<"row "<<i<<"col "<<j<<endl; break;}}//没有合适的位置，所以要回溯到上一个最合适的节点if(j==n){i--;while(i>=0){int k=path[i]+1;while(k<n&&!(place(i,k,path)))k++;if(k==n)i--;else{path[i]=k;break;}if(i<0){cout<<"there is no way "<<endl;return;}}}if(i==n)for(int j=0;j<n;j++){cout<<setw(5)<<left<<path[j];path[j]=-1000;}}//利用栈来模拟递归，在某个扩展节点出处，将所有符合条件的节点加入到里面struct pos{int row;int col;};//找到当前最合适的节点,如果没有找到则返回-1int find_col(int row,int col,int* path,int n){int j;for(j=col;j<n;j++){if(place(row,j,path))return j;if(j==n)return -1;}//利用栈来模拟八皇后问题void stack_stimu(int n,int* path){stack<struct pos> s;int currow=0;int flag=0;//主要结构分为两部分，第一按照正常顺序寻找节点//然后找出回溯的情况：在八皇后问题中主要有两中：1.到达结尾找出路径 2.当前行没有满足条件的位置while(true){if(currow<n){int col=find_col(currow,0,path,n);if(col!=-1){pos node;node.row=currow;node.col=col;s.push(node);path[currow]=col;currow++;}elseflag=1;}else{for(int i=0;i<n;i++)cout<<setw(5)<<left<<path[i];cout<<endl;count++;flag=1;}// 进行回溯if(flag==1){//描述了回溯的过程while(!s.empty()){pos temp=s.top();if(temp.col!=7){//查找当前最适合的节点，并入栈int j=find_col(temp.row,temp.col+1,path,n); if(j!=-1){pos node;node.row=temp.row;node.col=j;s.pop();s.push(node);path[temp.row]=j;currow=temp.row+1;flag=0;break;}elses.pop();}elses.pop();}if(s.empty())return;//函数的出口处}}//end for while(true)}int main(){cout<<"Queen Place Problem:"<<endl; cout<<"Input the value of n"<<endl; int n;cout<<" n>";cin>>n;int* path=new int[n];//初始化for(int i=0;i<n;i++)path[i]=-1000;//queen_another(n,path);//queen(0,path,n);stack_stimu(n,path);cout<<"the count is: "<<count<<endl; getchar();getchar(); return 0; }。

目录一需求分析 (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等语句，并通过不断的判断，去推出答案，而且这种非递归的思想，大大的增加了程序的时间复杂度。

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

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

八皇后问题代码实现/*代码解析*//* Code by Slyar */ #include &lt;stdio.h&gt;#include&lt;stdlib.h&gt; #define max 8 int queen[max], sum=0; /* max为棋盘最大坐标*/ void show() /* 输出所有皇后的坐标*/{ int i; for(i = 0; i &lt; max; i++){ printf("(%d,%d) ", i, queen[i]); }printf("\n"); sum++;} int check(int n) /* 检查当前列能否放置皇后*/{ int i; for(i = 0; i &lt; n; i++) /* 检查横排和对角线上是否可以放置皇后*/ { /* ///题目的要求是所有皇后不在同一横排、竖排、对角线上。

1、queen[n]值为竖排号，可看为Y轴上值。

n值为横排号，可看为X轴上值。

2、(1)先从横坐标第n点排开始放皇后，再放第n+1，所有不会同一横坐标点即同一竖排。

(2)queen[i] == queen[n]时即y坐标相等，即在同一横排，此时判断不合规则点。

(3)abs(queen[i] - queen[n]) == (n - i)，可变形为(queen[n] - queen[i]) /(n - i)==tan45°或tan135° 由公式可得出，点(n,queen[n])与点(i,quuen[i])在同一条左斜线135°或右斜45°，即国际象棋上的每个格子的两条斜角线。

3、由2即可得出当前格式是否能放置一个皇后。

*/ if(queen[i] == queen[n] || abs(queen[i] - queen[n]) == (n - i)) { return1; } } return 0;} void put(int n) /* 回溯尝试皇后位置,n为横坐标*/{ int i; for(i = 0; i &lt; max;i++) { queen[n] = i; /* 将皇后摆到当前循环到的位置*/ if(!check(n)){ if(n == max - 1){ show(); /* 如果全部摆好，则输出所有皇后的坐标*/ } else { put(n + 1); /* 否则继续摆放下一个皇后*/ } } }} int main(){ put(0); /*从横坐标为0开始依次尝试*/ printf("TTTTTT----%d\n", sum); //system("pause"); //while(1); return 0;}/*算法系列---回溯算法引言寻找问题的解的一种可靠的方法是首先列出所有候选解，然后依次检查每一个，在检查完所有或部分候选解后，即可找到所需要的解。

汉诺塔代码java实现汉诺塔（Tower of Hanoi）是一种经典的数学问题和递归算法示例。

这个问题的目标是将一堆盘子从一个柱子上移动到另一个柱子上，同时遵守以下规则：只能移动一个盘子，移动过程中不能将较大的盘子放在较小的盘子上。

以下是使用Java语言实现汉诺塔问题的代码示例：```javapublic class HanoiTower {public static void move(int n, char source, char target, char auxiliary) {if (n == 1) {System.out.println("Move disk 1 from " + source + " to " + target);return;}move(n - 1, source, auxiliary, target);System.out.println("Move disk " + n + " from " + source + " to " + target);move(n - 1, auxiliary, target, source);}public static void main(String[] args) {int n = 3; // 盘子的个数move(n, 'A', 'C', 'B');}}```在上述代码中，我们定义了一个名为`move`的递归函数，该函数接受四个参数：盘子的数量`n`、源柱子`source`、目标柱子`target`和辅助柱子`auxiliary`。

递归函数的作用是将`n`个盘子从源柱子移动到目标柱子。

当`n`等于1时，表示只有一个盘子需要移动，此时直接将该盘子从源柱子移动到目标柱子即可。

当`n`大于1时，我们需要先将`n-1`个盘子从源柱子移动到辅助柱子，然后将第`n`个盘子从源柱子移动到目标柱子，最后再将`n-1`个盘子从辅助柱子移动到目标柱子。