利用递归解决八皇后问题
- 2020 年 3 月 9 日
- 笔记
1.什么是八皇后问题？
游戏的一种，感兴趣的小伙伴可以去玩一下。规则如下： 在 8 * 8 的棋盘上，任何两个皇后都不能处于同一行同一列或同一个斜线上。
2.什么是递归？ 关于递归的简单描述
3.解决方式
package xmht.datastructuresandalgorithms.datastructure; /** * @author shengjk1 * @date 2020/3/4 */ /* 8皇后问题，在 8 * 8 的棋盘上，任何两个皇后都不能处于同一行同一列或同一个斜线上。 1.第一个皇后先放第一行第一列 2.第二个皇后放在第二行第一列，然后判断是否ok，如果不 ok，继续放在第二列、第三列，依次把所有列都放完，找到一个合适的 3.继续第三个皇后，还是第一列、第二列......直到第8个皇后也能放在一个不冲突的位置，算是找到了一个正确的解。 4.当得到第一个正确解时，在栈回退到上一个栈时，就会开始回溯，即将第一个皇后，放到第一列的所有正确解全部找到。 5.然后回头继续第一个皇后放第二列，后面继续循环执行1234步骤。 理论上应该创建一个二维数组来表示棋盘，但是实际上可以通过算法，用一个一维数组即可解决问题。arr[8]={0,1,2,3,4,5,6,7} 对应的 arr 下标 表示第几行，即第几个皇后，arr[i]=val,val表示第i+1个皇后，放在第i+1行的第val+1列。 */ public class Queue8 { //定义一个有多少个皇后 int max = 8; //定义数组 arrya,保存皇后存放位置的结果。 int[] array = new int[max]; // int[] array = {-1, -1, -1, -1, -1, -1, -1, -1}; static int count = 0; public static void main(String[] args) { Queue8 queue8 = new Queue8(); // 从第 0 行开始 queue8.check(0); System.out.println(count); } //这一块会有递归会有回溯，其实还是挺巧妙的，很值得细细体会。 private void check(int n) { //相当于该放第 9 个皇后了 if (n == max) { count++; print(); return; } //依次放入皇后，并判断是否冲突 //这个的max 其实是列数 for (int i = 0; i < max; i++) { //先把皇后 n 放到该行的第一列 array[n] = i; //判断当放置第 n 个皇后置第 i列时，是否与之前的n-1个皇后冲突 if (judge(n)) { //不冲突，就接着放下一个皇后。 check(n + 1); } } } /* 1.arrya[i]==arrya[n]表示判断第n个皇后是否与前面 n-1 个皇后在同一列 2.Math.abs(n - i) == Math.abs(array[n] - array[i])表示判断第 n 个皇后是否与第 i 个皇后在同一个斜线上。(列差等于行差，肯定在同一个斜线上) 3.没有必要判断是否在同一行，因为 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])) { return false; } } return true; } //输出皇后的位置 private void print() { for (int i = 0; i < array.length; i++) { System.out.print(array[i] + " "); } System.out.println(); } }
4.其他 现在有点体会到，递归解决迷宫问题的巧妙之处了。
