08-递归-回溯-8皇后问题
2022-07-05 本文已影响0人
紫荆秋雪_文
铭记:
源码下载
一、场景
- 八皇后问题：在一个8X8的棋盘上，放置8个棋子
- 要求：任意两个棋子不能处于同一行、同一列、同一斜线。问有多少摆法？
二、思路
- 1、在二维数组中，从第一行的第一列开始一个一个放置，直到第八列
- 2、从第二行的第一列开始一个一个放置，直到第八列
- 3、不断的执行1、2步骤，判断是否可以放置皇后
- 4、这里会涉及到回溯的问题：
- 4.1、回溯的第一种情况：当某一行（第5行）都不适合放置皇后，那么就需要回溯到第4行，并且说明第4行当前位置放置的皇后是错误的，需要撤销并且把皇后放置到下一列再试尝试1，2步骤。
- 4.2、回溯的第二种情况：完成一次放置（如：7 2 0 5 1 4 6 3）需要逐层回退（在1-5位置不变的情况下）移动第6行的皇后到下一列，然后再继续1，2步骤
- 回溯：表示我们之前的走法是行不通或者是行得通但是要尝试另一条路，例如步骤4中的回溯情况。例如回溯情况4.2，由于已经把第6、7、8行都已经走过，所以需要把回溯行到最后一行重新恢复原样（防止判断错误）
三、Queen8
package com.raven.alg.s5recursion;
/**
* 8 皇后问题
* 思路：
* 首先放置第一个皇后
* 固定在第一行，从第一列开始
* (0, 1)，(0, 2)，(0, 3)，(0, 4)，(0, 5)，(0, 6)，(0, 7)
*/
public class Queen8 {
// 已使用，需要跳过
private final static Integer SUCCESS = 1;
private final static Integer FAIL = 2;
private final static Integer HS = 3;
private static Boolean isHS = false;
private static Boolean isFinish = false;
private static Integer count = 0;
public static void run(Integer size) {
if (size < 1) {
throw new RuntimeException("棋盘不能小于0");
}
// 1、创建棋盘
int[][] mg = initMigong(size);
// 棋盘
for (int i = 0; i < size; i++) {
for (int j = 0; j < size; j++) {
System.out.print(mg[i][j] + " " + " ");
}
System.out.println();
}
// 第一个皇后的位置
go(mg, 0);
System.out.println("Count = " + count);
}
private static void go(int[][] mg, int startX) {
// 已放满
if (startX == mg.length) {
count++;
System.out.println("已完成第 " + count + " 次");
print2(mg);
print(mg);
isFinish = true;
System.out.println();
return;
}
// 从 0 ~ 7
for (int i = 0; i < mg.length; i++) {
// 处理回溯
if (isHS || isFinish) {
isHS = false;
recall(mg, startX);
}
// 完成时进行下一遍是需要把当前回溯
if (isFinish) {
isFinish = false;
recall(mg, startX);
}
mg[startX][i] = 1;
if (SUCCESS == check(mg, startX, i)) {
go(mg, startX + 1);
} else {
mg[startX][i] = 2;
}
}
}
/**
* 校验当前位置的皇后是否与已经存在的皇后冲突
* <p>
* 冲突：不能在同一列、同一行、一条斜线上
*
* @param mg
* @param startX
* @param startY
* @return
*/
private static Integer check(int[][] mg, int startX, int startY) {
for (int i = 0; i < startX; i++) {
for (int j = 0; j < mg.length; j++) {
int hh = mg[i][j];
boolean isX = i == startX;
boolean isY = j == startY;
Boolean isXX = Math.abs(i - startX) == Math.abs(j - startY);
if (hh == SUCCESS && (isX || isY || isXX)) {
// 需要回溯
if (mg.length - 1 == startY) {
isHS = true;
}
return FAIL;
}
}
}
return SUCCESS;
}
/**
* 回溯
*
* @param mg
* @param startX
* @return
*/
private static void recall(int[][] mg, int startX) {
for (int i = startX; i < mg.length; i++) {
for (int j = 0; j < mg.length; j++) {
if (1 == mg[i][j]) {
mg[i][j] = HS;
}
}
}
}
/**
* 打印
*
* @param mg
*/
private static void print2(int[][] mg) {
for (int i = 0; i < mg.length; i++) {
for (int j = 0; j < mg.length; j++) {
if (1 == mg[i][j]) {
System.out.print(j + " ");
}
}
}
System.out.println();
}
/**
* 打印
*
* @param mg
*/
private static void print(int[][] mg) {
System.out.println("已完成第 " + count + " 次8皇后图：");
for (int i = 0; i < mg.length; i++) {
for (int j = 0; j < mg.length; j++) {
System.out.print(mg[i][j] + " ");
}
System.out.println();
}
}
/**
* 初始化棋盘
*
* @param size
* @return
*/
private static int[][] initMigong(Integer size) {
if (size < SUCCESS) {
throw new RuntimeException("迷宫不能小于0");
}
// 创建迷宫
int[][] mg = new int[size][size];
return mg;
}
}
四、这种方法更加取巧
这个方法比较取巧，但是思路一样，定义一个一维数组arr = {0 , 4, 7, 5, 2, 6, 1, 3}，arr的下标代表第几行的皇后，arr的值表示皇后所在的列。
package com.raven.alg.s5recursion;
public class Queue82 {
//数组大小
int max = 8;
// arr = {0 , 4, 7, 5, 2, 6, 1, 3}
int[] array = new int[max];
static int count = 0;
static int judgeCount = 0;
public static void main(String[] args) {
Queue82 queue8 = new Queue82();
queue8.check(0);
System.out.printf("共有%d种ⷨ", count);
System.out.printf("共回溯%d次", judgeCount); // 1.5w
System.out.println();
}
private void check(int n) {
if(n == max) { //n = 8 代表防止成功
print();
return;
}
//表示每个皇后都是从0列开始
for(int i = 0; i < max; i++) {
//第n+1个皇后防止在第i+1列表
array[n] = i;
//判断是否可以放置皇后在n+1位置
if(judge(n)) {
// 防止下一行
check(n+1);
}
}
}
/**
* 判断是否可以放置皇后
* @param n
* @return
*/
private boolean judge(int n) {
judgeCount++;
for(int i = 0; i < n; i++) {
//1. array[i] == array[n] 表示在同一列
//2. Math.abs(n-i) == Math.abs(array[n] - array[i]) 表示在一个斜线上
// n = 1 ���õ� 2�� 1 n = 1 array[1] = 1
// Math.abs(1-0) == 1 Math.abs(array[n] - array[i]) = Math.abs(1-0) = 1
if(array[i] == array[n] || Math.abs(n-i) == Math.abs(array[n] - array[i]) ) {
return false;
}
}
return true;
}
//输出
private void print() {
count++;
for (int i = 0; i < array.length; i++) {
System.out.print(array[i] + " ");
}
System.out.println();
}
}
