知识导航

• 一、回溯思想概述
• 二、八皇后问题引入
• • 八皇后问题的解决思路
  • • (1)思路一：暴力出奇迹
    • (2）思路二：根据题意减小暴力程度
    • (3）思路三：回溯法+剪枝
• 三、四皇后问题
• • 八皇后问题
• 四、N皇后的实现
• • 1.实现方法一：利用数组下标和元素形成行，列对应关系
  • 2.实现方法二：利用布尔数组及进行优化
  • 3.实现方法三：位运算进行进一步优化（仅针对N皇后）

一、回溯思想概述

🥳🥳 回溯可以理解为：通过选择不同的岔路口来通往目的地（找到想要的结果）
1.每一步都选择一条路出发，能进则进，不能进则退回上一步（回溯），换一条路再试
2. 树、图的深度优先搜索（DFS）、八皇后、走迷宫都是典型的回溯应用

二、八皇后问题引入

◼ 八皇后问题是一个古老而著名的问题
1.在8x8格的国际象棋上摆放八个皇后，使其不能互相攻击：任意两个皇后都不能处于同一行、同一列、同一斜线上
2.请问有多少种摆法？

八皇后问题的解决思路

(1)思路一：暴力出奇迹

(2）思路二：根据题意减小暴力程度

(3）思路三：回溯法+剪枝

我们可以用回溯法和剪枝思想解决8皇后问题乃至N皇后问题。我们由简单到复杂，先对4皇后进行一个思想梳理，请看下文👇👇

三、四皇后问题

四皇后问题的回溯示意图

由图中不难看出 3 5 都发生了回溯，那么什么是剪枝思想呢？

如果第一次选的是0下标节点，那么和这个节点的斜对角节点1，和这个节点的同一列的节点0都不会再被选中，因为是按一行一行进行选择的所以行的限制不做考虑。这种越过一部分的节点不做选择的操作称为剪枝操作。

八皇后问题

由上面的四皇后我们可以推及到8皇后问题的操作

和四皇后的方法一样一行一行进行选择，如果发现能放的节点数不够存储剩下皇后则回溯到上一个操作，重新选择节点（上面的图并不是完整的回溯过程。可以自己试着自己推一下）。

四、N皇后的实现

1.实现方法一：利用数组下标和元素形成行，列对应关系

成员变量

 /*** 第几行的第几列存放皇后* 下标为行号，存储的为列号*/private int []cols;private int ways;

放置皇后

//n->有多少皇后public void placeQueues(int n){if(n<1)return;//至少得有一个皇后cols=new int [n];place(0);System.out.println(n+"皇后共有"+ways+"种摆放方法");}/*** 从第几行存放皇后* @param row*/public void place(int row){//一种情况已经放完if(row==cols.length){ways++;printf();return;}//行号已经确定row，遍历列好for (int col = 0; col //isValid()实际是进行了剪枝操作if(isValid(row,col)){cols[row]=col;//放置下一行place(row+1);}}}

放置皇后的可行性判断

 public boolean isValid(int row,int col){for(int i=0;i//行是一行一行往下的，所以这里不用进行的行的判断//判断列，相等说明同一列已经放了元素if (cols[i] == col) return false;//row-i/col-cols[i]==1//row-i必是正数，斜率if (row-i==Math.abs(col-cols[i])) return false;}return true;}

打印操作

public void printf(){for (int row = 0; row < cols.length; row++) {for (int col = 0; col < cols.length; col++) {if (cols[row] == col) {System.out.print("1 ");} else {System.out.print("0 ");}}System.out.println();}System.out.println("------------------------------");}

2.实现方法二：利用布尔数组及进行优化

//N皇后问题-->成员变量优化
//在第一种写法时有一个缺点在进行isValid()每次都要进行for循环，效率很差
//这种写法的缺点是：不适用于太多皇后的安排，因为额外开辟了三个数组空间
public class NQueens1 {//下标是行号，元素是列号：保留这个数组-->方便显示（打印）皇后的具体位置private int [] queens;/*** 标记某一列是否有皇后* 下标为行号，存储的为列号* 左上--->右下:指的是对角线的指向*/private boolean []cols;private boolean []leftTop;//标记一个方向的斜线是否有皇后（左上--->右下）private boolean []rightTop;//标记一个方向的斜线是否有皇后（右上--->左下）private int ways;//n->有多少皇后public void placeQueues(int n){if(n<1)return;//至少得有一个皇后queens=new int[n];cols=new boolean[n];leftTop=new boolean[(n<<1)-1];//同一个方向有2*n-1个斜线rightTop=new boolean[leftTop.length];place(0);System.out.println(n+"皇后共有"+ways+"种摆放方法");}/*** 从第几行存放皇后* @param row*/public void place(int row){//一种情况已经放完if(row==cols.length){ways++;show();return;}//行号已经确定row，遍历列好for (int col = 0; col if(cols[col])continue;//剪枝：这一列已经有皇后了int ltIndex=row-col+cols.length-1;if(leftTop[ltIndex])continue;int rtIndex=row+col;if(rightTop[rtIndex])continue;queens[row] = col;cols[col]=true;//放置下一行leftTop[ltIndex]=true;rightTop[rtIndex]=true;place(row+1);//到这里说明row+1行没有可以放的位置，药要进行回溯；重置//之前没有改是因为，新的设置会覆盖掉原来的设置cols[col]=false;//放置下一行leftTop[ltIndex]=false;rightTop[rtIndex]=false;}}void show() {for (int row = 0; row < cols.length; row++) {for (int col = 0; col < cols.length; col++) {if (queens[row] == col) {System.out.print("1 ");} else {System.out.print("0 ");}}System.out.println();}System.out.println("------------------------------");}
}

3.实现方法三：位运算进行进一步优化（仅针对N皇后）

package Test02;/*** 什么情况适用于位运算优化？* 1、存在布尔数组* 2.数组的长度不是很长（最好能用现有数据结构来表示）*/public class eightQueens {//下标是行号，元素是列号：保留这个数组-->方便显示（打印）皇后的具体位置private int [] queens;/*** cols：将boolean类型用 0 1表示。通过转化成二进制位压缩为byte(8个比特位)类型* [true  false  false true.....]--->[1 0 0 1......]* leftTop rightTop有十五个元素，所以用short存储就足够了**/byte cols;short leftTop;//标记一个方向的斜线是否有皇后（左上--->右下）short rightTop;//标记一个方向的斜线是否有皇后（右上--->左下）private int ways;//n->有多少皇后public void placeQueues(){queens=new int[8];place(0);System.out.println(8+"皇后共有"+ways+"种摆放方法");}/*** 从第几行存放皇后* @param row*/public void place(int row){//一种情况已经放完if(row==8){ways++;show();return;}//行号已经确定row，遍历列好for (int col = 0; col < 8; col++) {int cv = 1 << col;if ((cols & cv) != 0) continue;int lv = 1 << (row - col + 7);if ((leftTop & lv) != 0) continue;int rv = 1 << (row + col);if ((rightTop & rv) != 0) continue;queens[row] = col;cols |= cv;leftTop |= lv;rightTop |= rv;place(row + 1);cols &= ~cv;leftTop &= ~lv;rightTop &= ~rv;}}void show() {for (int row = 0; row < 8; row++) {for (int col = 0; col < 8; col++) {if (queens[row] == col) {System.out.print("1 ");} else {System.out.print("0 ");}}System.out.println();}System.out.println("------------------------------");}}