public class MiGong { public static void main(String[] args) { /*创建二维数组模拟迷宫 * 地图*/ int[][] map =new int[8][7]; /*1：墙2： * 上下置为1*/ for (int i = 0; i < 7; i++) { map[0][i] = 1; map[7][i] = 1; } /*左右置为1*/ for (int i = 0; i <8 ; i++) { map[i][0]=1; map[i][6]=1; } map[3][1]=1; map[3][2]=1; //输出地图 System.out.println("地图情况====="); for (int i = 0; i <8 ; i++) { for (int j = 0; j <7 ; j++) { System.out.print(map[i][j]+" "); } System.out.println(); } //使用递归回溯给小球找路 setWay(map,1,1); //输出新地图，小球走过并标识的路 System.out.println("小球走过并标识的路====="); for (int i = 0; i <8 ; i++) { for (int j = 0; j <7 ; j++) { System.out.print(map[i][j]+" "); } System.out.println(); } } /*使用递归回溯来给小球找路 * 1.起始位置：(1,1) * 如果找到map[6][5],说明通路找到 * 2.约定：0：该点没有找过1：表示墙，2：通路可以走3：该点已经走过但是不能走通 断路不能走 * 3.策略：行进方向（）下--》右--》上--》左，走不通进行回溯*/ /** * * @description:使用递归回溯来给小球找路 * @params:1：地图 起始位置 2：行3：列 * @return: 找到通路为真，否则为假 * @author: 苏兴旺 * @time: 2020/3/12 11:54 */ public static boolean setWay(int[][]map,int i ,int j){ if (map[6][5]==2){//通路找到 return true; }else { if (map[i][j]==0){//如果当前点没有走过 /*按照策略下--》右--》上--》左走*/ map[i][j] = 2;//假定该点可以走 if (setWay(map, i+1, j)){//向下走 return true; }else if (setWay(map, i, j+1)){//向右走 return true; }else if (setWay(map, i-1, j)){//向上 return true; }else if (setWay(map, i, j-1)){//向左 return true; }else { map[i][j] = 3;//死路走不通 return false; } }else {//map[i][j]!=0 /*1: 2: 3:*/ return false; } } } }
八皇后问题，一个古老而著名的问题，是回溯算法的典型案例。该问题由国际西洋棋棋手马克斯·贝瑟尔于 1848 年提出：在 8×8 格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。高斯认为有 76 种方案。1854 年在柏林的象棋杂志上不同的作者发表了 40 种不同的解，后来有人用图论的方法解出 92 种结果。计算机发明后，有多种计算机语言可以编程解决此问题。八皇后问题如果用穷举法需要尝试 88 =16,777,216 种情况。每一列放一个皇后，可以放在第 1 行，第 2 行，……，直到第 8 行。穷举的时候从所有皇后都放在第 1 行的方案开始，检验皇后之间是否会相互攻击。如果会，把列 H 的皇后挪一格，验证下一个方案。移到底了就 “进位” 到列 G 的皇后挪一格，列 H 的皇后重新试过全部的 8 行。如图 1 所示，这种方法无疑是非常低效率的，因为它并不是哪里有冲突就调整哪里，而是盲目地按既定顺序枚举所有的可能方案。
public class Queue8 { public static void main(String[] args) { Queue8 queue8 = new Queue8(); queue8.check(0); System.out.printf("一共有%d中解法",count); } /*定义一个max：多少个皇后*/ int max = 8; static int count=0; /*定义一个数组放置位置的结果*/ int[] array = new int[max]; /*将皇后摆放的位置输出*/ private void print(){ count++; for (int i = 0; i < array.length; i++) { System.out.print(array[i]+" "); } System.out.println(); } /*放置第n个皇后*/ private void check(int n){ if (n ==max){//n=8 其实8个皇后已经放好 print(); return; } //依次放入皇后判断是否冲突 for (int i = 0; i <max ; i++) { //先把当前皇后n放到该行的第1列 array[n]=i; /*判断放置第n个皇后到i列时是否冲突*/ if (judge(n)){//不冲突接着放下一个皇后开始递归 check(n+1); } /*如果冲突，就继续arry[n]=i即将第n个皇后放置在本行的后一个位置*/ } } /*查看当我们放置第n个皇后时：判断检查该皇后是否和之前摆放的皇后冲突*/ private boolean judge(int n){ for (int i = 0; i < n; i++) { if (array[i]==array[n] ||Math.abs(n-i)==Math.abs(array[n]-array[i])){//1.同一列2.通一斜线 return false; } } return true; } }
原文：https://www.cnblogs.com/sxw123/p/12806112.html