递归-八皇后问题(回溯算法)
递归-八皇后问题(回溯算法)
八皇后问题的介绍
八皇后问题，是一个古老而著名的问题，是回溯算法的典型案例。该问题是国际西洋棋棋手马克斯·贝瑟尔于1848年提出：在8×8格的国际象棋上摆放八个皇后，使其不能互相攻击，即：任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。(92)
八皇后问题算法思路分析
- 第一个皇后先放第一行第一列
- 第二个皇后放在第二行第一列、然后判断是否OK， 如果不OK，继续放在第二列、第三列、依次把所有列都 放完，找到一个合适
- 继续第三个皇后，还是第一列、第二列……直到第 8 个皇后也能放在一个不冲突的位置，算是找到了一个正确解
- 当得到一个正确解时，在栈回退到上一个栈时，就会开始回溯，即将第一个皇后，放到第一列的所有正确解， 全部得到.
- 然后回头继续第一个皇后放第二列，后面继续循环执行 1,2,3,4 的步骤
- 示意图:
说明： 理论上应该创建一个二维数组来表示棋盘，但是实际上可以通过算法，用一个一维数组即可解决问题. arr[8] ={0 , 4, 7, 5, 2, 6, 1, 3} //对应 arr 下标 表示第几行，即第几个皇后，arr[i] = val , val 表示第 i+1 个皇后，放在第 i+1 行的第 val+1 列
八皇后问题算法代码实现
package com.iflytek.recursion;public class Queue8 { //定义一个max 表示共有多少个皇后 int max = 8; //定义数组 array, 保存皇后放置位置的结果,比如 arr = {0 , 4, 7, 5, 2, 6, 1, 3}表示第几行皇后放在第几列的位置 int[] array = new int[max]; static int count = 0; static int judgeCount = 0; //编写一个方法，放置第 n 个皇后 // 特别注意： check 是 每一次递归时，进入到 check 中都有 for(int i = 0; i < max; i++)，因此会有回溯 public void check(int n) { if (n == 8) {//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);//接着放 n+1 个皇后,即开始递归 } //如果冲突，就继续执行 array[n] = i; 即将第 n 个皇后，放置在本行的后移的一个位置 } } / * 查看当我们放置第 n 个皇后, 就去检测该皇后是否和前面已经摆放的皇后冲突 * @param n 表示第 n 个皇后 * @return */ public boolean judge(int n) { judgeCount++; for (int i = 0; i < n; i++) { // 说明 // 1. array[i] == array[n] 表示判断 第 n 个皇后是否和前面的 n-1 个皇后在同一列 // 2. Math.abs(n-i) == Math.abs(array[n] - array[i]) 表示判断第 n 个皇后是否和第 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 // 3. 判断是否在同一行, 没有必要，n 每次都在递增 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(); } public static void main(String[] args) { //测试一把 ， 8 皇后是否正确 Queue8 queue8 = new Queue8(); queue8.check(0); System.out.printf("一共有%d 解法", count); System.out.printf("一共判断冲突的次数%d 次", judgeCount); // 1.5w }}八皇后其他算法
package com.iflytek.recursion;public class Queue82 { //棋盘格子的范围，以及皇后的数量（应该分开定义，这里偷懒了） static final int MAX_NUM = 8; //二维数组作为棋盘 static int[][] chessBoard = new int[MAX_NUM][MAX_NUM]; public static boolean check(int x, int y) { for (int i = 0; i < y; i++) { //检查纵向 if (chessBoard[x][i] == 1) { return false; } //检查左侧斜向 if (x - 1 - i >= 0 && chessBoard[x - 1 - i][y - 1 - i] == 1) { return false; } //检查右侧斜向 if (x + 1 + i < MAX_NUM && chessBoard[x + 1 + i][y - 1 - i] == 1) { return false; } } return true; } public boolean selectQueue(int y) { //行数超过8，说明已近找出答案 if (y == MAX_NUM) { return true; } for (int i = 0; i < MAX_NUM; i++) { //为当前行清0，以免回溯的时候出现脏数据// for (int j = 0; j < MAX_NUM; j++) {// chessBoard[j][y] = 0;// } //检查是否符合规则，如果符合，更改元素值并进一步递归 if (check(i, y)) { chessBoard[i][y] = 1; //递归如果返回true，说明下层已近找到解决，无须继续循环 if (selectQueue(y + 1)) { return true; }else { chessBoard[i][y]=0; } } } return false; } public static void print() { for (int i = 0; i < MAX_NUM; i++) { for (int j = 0; j < MAX_NUM; j++) { System.out.print(chessBoard[i][j] + " "); } System.out.println(); } } public static void main(String[] args) { Queue82 queue82 = new Queue82(); queue82.selectQueue(0); queue82.print(); }}
