Java编程思想—八皇后问题（数组法、堆栈法）

实验题目：回溯法实验(八皇后问题)
实验目的：
实验要求：
实验内容：

（1）问题描述
（2）实验步骤：

数组法：
堆栈法：

算法伪代码：
实验结果：
实验代码：
出现的问题：

问题一：条件检查
问题二：数组法跳出循环情况分析

实验心得：

实验题目：回溯法实验(八皇后问题)

实验目的：

（1）掌握回溯法求解问题的思想

（2）学会利用其原理求解相关问题

实验要求：

	使用贪心法求出给定图各点的最短路径，并计算算法的执行时间，分析算法的有效性。利用回溯法解决八皇后问题，检验结果，并计算算法的执行时间，分析算法的有效性。

	测试数据可以通过手工寻找三组满足需要的值，测试数组（M，N），其中 M 代表皇后所在的行，N 代表皇后所在的列。

例如，第一组测试数据：

（1，4）、（2，7）、（3，3）、（4、8）、（5，2）、（6，5）、（7，1）、（8，6）；

第二组测试数据

（1，5）、（2，2）、（3，4）、（4，7）、（5，3）、（6，8）、（7，6）、（8，1）；

第三组测试数据

（1，4）、（2，2）、（3，7）、（4，3）、（5，6）、（6，8）、（7，5）、（8，1）。

最后与编程求得的结果进行比较。如果这三组数据在最后编程求得的结果中，说明程序的编写基本没有什么问题。

实验内容：

（1）问题描述

八皇后问题是一个以国际象棋为背景的问题：如何能够在 8×8 的国际象棋棋盘上放置八个皇后，使得任何一个皇后都无法直接吃掉其他的皇后。为了达到此目的，任两个皇后都不能处于同一条横行、纵行或斜线上。

（2）实验步骤：

数组法：

① 根据 8 皇后问题，可以把其设想为一个数组；

② 根据 8 皇后的规则，可以设想为数组上同一直线，横线，斜线的数字都不能相同，由此可以得出判断条件；

③ 根据判断条件之后，建立回溯点，即可解决问题。

堆栈法：

① 检索当前行是否可以放置一个皇后；

② 利用检索过程，通过递归的方式，来确定每个皇后的位置———回溯的思想。

算法伪代码：

实验结果：

实验代码：

public class EightQueensOfBacktracking {

	int count = 0;

	//棋盘初始化 清空操作

	void initialChessBoard(int chessBoard[][]){

		for(int i = 0; i < 8 ; i++){

			for(int j = 0; j < 8; j++){

				chessBoard[i][j] = 0;

			}

		}

	}

	//打印皇后位置

	void showLocation(int chessBoard[][]){

		System.out.println("————————————");

		System.out.println("皇后的坐标为：");

		for(int i = 0; i < 8 ; i++){

			for(int j = 0; j < 8; j++){

				if(chessBoard[i][j] != 0){

					System.out.print(" ( " + (i+1) + " , " + (j+1) + " ) ");

				}

			}

		}

		System.out.println();

		System.out.println("棋盘如下：");

		for(int i = 0; i < 8 ; i++){

			for(int j = 0; j < 8; j++){

				System.out.print(chessBoard[i][j] + " ");

			}

			System.out.println();

		}

	}

	//行列检查 斜线检查

	boolean checkAll(int i, int j, int chessBoard[][]){

		int tempI = i;

		int tempJ = j;

		if((i>7)||(j>7)) return false;

		//check column

		for(int k = 0; k <= j; k++){

			if(chessBoard[i][k] != 0){

				return false;

			}

		}

		//check row

		for(int k = 0; k <= i; k++){

			if(chessBoard[k][j] != 0){

				return false;

			}

		}

		//左上斜线检查

		while(true){

			if(chessBoard[i][j] != 0)

				return false;

			if((i == 0)||(j == 0)) break;

			i--;

			j--;

		}

		//右上斜线检查

		i = tempI;

		j = tempJ;

		while(true){

			if(chessBoard[i][j] != 0)

				return false;

			if((i == 0)||(j == 7)) break;

			i--;

			j++;

		}

		return true;

	}

	//堆栈方法

	public void findQueen(int i, int chessBoard[][], EightQueensOfBacktracking eightQueens){

		if(i>7){

			eightQueens.count++;

			eightQueens.showLocation(chessBoard);

		}

		//回溯法

		boolean judge;

		for(int m = 0; m<8; m++){

			judge = eightQueens.checkAll(i, m, chessBoard);

			if(judge){

				chessBoard[i][m] = 1;

				eightQueens.findQueen(i+1, chessBoard, eightQueens);

				chessBoard[i][m] = 0;

			}

		}

	}

	public static void main(String[] args) {

		// TODO Auto-generated method stub

		//函数调用

		EightQueensOfBacktracking eightQueens = new EightQueensOfBacktracking();

		//摆法的数量

		int count = 0;

		int k = 0;//临时变量

		int i = 0, j= 0;//i 行 ；j 列

		boolean judge = true;//检查结果

		//8个皇后，1-8表示

		int queens = 1;

		//棋盘 8*8

		int chessBoard[][] = new int [8][8];

		//每次找到解后清盘，即初始化

		eightQueens.initialChessBoard(chessBoard);

		long startTime2 = System.nanoTime();

		//堆栈方法：

		eightQueens.findQueen(0, chessBoard, eightQueens);

		long endTime2 = System.nanoTime();

		//数组方法

		//失败1：在当前行非末尾：列+1；

		//失败2：在当前行的末尾：判断行，如果是0行，则所有情况已遍历，结束；

//													如果不是，回到上一行，遍历，查找到上一行的棋子，记录位置，找到下一位置，则结束查找上一个位置；

//															如果上一行也遍历完，列的位置为7，上一个位置处没有下一位置，则再找上上一行的位置，进行上面的循环；

//																	如果上一行是0行，则也结束遍历，flag为0，结束上一位置的查找；

		//成功：标记位置，如果位置标记是8，则为一种方案，输出，方法计数加一，标记减1，queens表示下一个要放的棋子；

//					行加1，列归0，通过失败1和失败2再找到上一个棋子的的位置

		long startTime1 = System.nanoTime();

		int flag = 1;

		while(true){

			judge = eightQueens.checkAll(i, j, chessBoard);

			//这一行未检查完，检查这一行下一个位置

			if((judge == false)&&(j != 7)){

				j++;

				continue;

			}

			else if((judge == false)&&(j == 7)){

				if(i == 0) break;//表示所有的情况已经遍历，结束循环

				i--;//回到上一行

				k = 0;//查找，用来遍历

				while(true){

					if(chessBoard[i][k] != 0){//找到上一行棋子的位置

						queens = chessBoard[i][k];//表示这个棋子放到棋盒中

						chessBoard[i][k] = 0;//把棋子取走

						j = k + 1;//找到下一个位置，准备下一次循环

						if(j > 7){//如果上一行也遍历完，找到上上一行

							if(i == 0){

								flag = 0;

								break;//如果上一行是0，那么没有上上一行，结束

							}

							i--;

							k =0;

							continue;//重新开始查找棋子

						}

						break;

					}

					k++;

				}

				if(flag == 0){

					break;

				}

				continue;

			}

			//检查通过，放下棋子，到下一行

			chessBoard[i][j] = queens;

			if(queens == 8){//找到一种方法

				eightQueens.showLocation(chessBoard);

				count++;

				queens--;

				//输出后，假装这个摆法不行，继续查找

			}

			queens++;//queens的值表示下一个要放的棋子

			i++;

			j = 0;

		}

		long endTime1 = System.nanoTime();

		System.out.println("数组方法共有" + count + "种摆法");

		System.out.println("堆栈递归方法共有" + eightQueens.count + "种摆法");

		System.out.println("数组程序运行时间：" + (endTime1 - startTime1) + "ns");

		System.out.println("堆栈递归程序运行时间：" + (endTime2 - startTime2) + "ns");

	}

}

出现的问题：

问题一：条件检查

实验时，排序的结果出现问题，斜线的情况不能检查出来。

于是我仔细检查了判断部分的代码，发现是变量的重复使用，导致无法正常判断。i和j的值被重复使用。我通过临时变量进行存储，在上一次使用后进行重新赋值，解决了问题，如红圈。

问题二：数组法跳出循环情况分析

一开始不知道递归方法，想用情况分析，循环查找，但是发现在查找时，只能查找到第一个棋子在1，1位置的情况。

我猜测是跳出循环的判断出了问题，于是在我的检查下，发现下图第一个圈是要跳出循环，结束整个查找，由于是双重循环，所以我直接在第二个圈设置如果i= =0，则结束循环，共两次跳出。

但是我忽略了限制条件，即在i = = 0的时候，并不是都是要结束的，只有圈1的那一种情况才跳出，所以我设置flag变量进行传递，纠正了程序的错误。更正的代码见 实验代码 部分。

实验心得：

本次实验体现的是回溯法。经过本次实验，发现自己对回溯的理解并不全面，不会应用。初次做这个题，想的只是遍历，在循环中，进行人工的回溯。后来发现回溯时的情况分析十分复杂，并不能很好的发现并且处理所有情况，只求出4种结果。经过学习后了解到，对于回溯，本题不需要自己考虑情况，只需给出限制条件进行筛选，在满足条件的情况下进行重复调用自身函数，在完成函数后，进行自身位置的值的清空，为之后回溯进行准备即可。让我明白递归是回溯的一种很好的实现方式。

在使用java的过程中，为了解决遇到的问题还进行了调试，让我对debug和调试有了进一步的掌握。

说明：递归法是调用系统堆栈进行操作，所以属于堆栈法。

递归堆栈方法可以参考链接：八皇后递归堆栈方法

巴特西

Java编程思想—八皇后问题（数组法、堆栈法）

Java编程思想—八皇后问题（数组法、堆栈法）

实验题目：回溯法实验(八皇后问题)

实验目的：

实验要求：

实验内容：

（1）问题描述

（2）实验步骤：

数组法：

堆栈法：

算法伪代码：

实验结果：

实验代码：

出现的问题：

问题一：条件检查

问题二：数组法跳出循环情况分析

实验心得：

最新文章

热门文章

巴特西

Java编程思想—八皇后问题（数组法、堆栈法）

Java编程思想—八皇后问题（数组法、堆栈法）

实验题目：回溯法实验(八皇后问题)

实验目的：

实验要求：

实验内容：

（1）问题描述

（2）实验步骤：

数组法：

堆栈法：

算法伪代码：

实验结果：

实验代码：

出现的问题：

问题一：条件检查

问题二：数组法 跳出循环情况分析

实验心得：

最新文章

热门文章

问题二：数组法跳出循环情况分析