《八皇后问题》& Java数据结构 & JavaProject & JavaOJ题集
n皇后的力扣链接
这里我优化了展现形式，放在oj上要去掉
N叉树问题（二叉树扩展）
技巧：画图分析---->判断是哪种数据结构
打印每组解
1. 八皇后问题定义 & 知识背景
八皇后问题（英文：Eight queens），是由国际象棋棋手马克斯·贝瑟尔于1848年提出的问题，是回溯算法的典型案例。
问题表述为：在8×8格的国际象棋上摆放8个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。高斯认为有76种方案。1854年在柏林的象棋杂志上不同的作者发表了40种不同的解，后来有人用图论的方法解出92种结果。如果经过±90度、±180度旋转，和对角线对称变换的摆法看成一类，共有42类。计算机发明后，有多种计算机语言可以编程解决此问题。
后来衍生为《n皇后问题》，即n*n棋盘能放n个皇后
回溯算法即—时间倒流
可用递归实现（本章重点）
可用Stack栈实现
我们想象一个场景：如果我们每一次走错都能回溯上一步，那么不就可以解决问题了。
待我们走完，不就可以记录下来次数了吗？
重要思想：
每一行只能有一个Queen，那么我们就可以每一行各选一个进行判断
八个攻击方向以及组合起来的攻击范围的判断
即一个棋盘的元素多个属性，一般不会用个类代表棋盘元素，而是用 【双生棋盘】
我们可以创建两个棋盘 —> 左盘记录攻击范围，右盘记录实时Queen位置
就拿简单的四皇后来看，棋盘每一行选一个位置放皇后，遇到不能放的就回溯
如图可知，四叉树数据结构—>递归实现
重点在于如何设计递归----并不是每一次都进入四次递归（并且是N叉树问题），可能0次or1次······
2. 棋盘设计
在以上理论基础下，我们开始设计吧！
这里我用的是二维顺序表，看起来麻烦了点，但也是对这一数据结构的练习！
完全可以用二维数组代替！
List<List<Character>> queenBoard = new ArrayList<>();
List<List<Character>> attack = new ArrayList<>();
//初始化 for(int i = 0; i < N; i++) { queenBoard.add( new ArrayList<Character>() { //区域一 } ); } for(int i = 0; i < N; i++) { attack.add( new ArrayList<Character>() { //区域二 } ); } //区域1 { for(int i = 0; i < N; i++) { add(' '); } } //区域2 { for(int i = 0; i < N; i++) { add(' '); } }
这里我用到一个技巧—> ArrayList<类型不能省略>() + { 语句 }; 的组合，
注意：语句应该也被代码块包裹！
可以在这个对象没名字的时候，就实现调用其中的方法，并且外界变量并不会被其捕获，并且this就是这个匿名对象
本质上，就是匿名内部类的内置（实例代码块），在构造方法调用前就已经调用完毕。
可想而知，匿名内部类功能很大！不仅能重写，还能【添加文本】！
但是，实例化一个有名字对象也就够了！这里是为了拓展知识点！
以上就是初始化效果！（左边皇后盘，右边攻击盘）
以下是打印技巧
for(int i = 0; i < queenBoard.size(); i++) { System.out.print(queenBoard.get(i)); System.out.print(" "); System.out.println(attack.get(i)); }
3. 放置皇后
public static final int N = 4; //N皇后的【N常量】
以四皇后为例子！
主要是要让attack棋盘的数值发生变化！
public static void putOn(List<List<Character>> qB, List<List<Character>> aT , int row, int col) { //以下两步是必然发生的 qB.get(row).set(col, 'Q'); aT.get(row).set(col, '1'); //技巧：方向数组 //区域1 //攻击 //区域2 for (int i = 1; i <= aT.size(); i++) {//保证覆盖整个整个棋盘 for (int j = 0; j < 8; j++) { int iX = col + i * pointX[j]; int iY = row + i * pointY[j]; if(iX < aT.size() && iX >= 0 && iY < aT.size() && iY >= 0) { aT.get(iY).set(iX, '1'); } } } }
3.1 区域1： 方向数组！
这里两个数组对应下标必须匹配好~
这样就可以通过遍历，就可以实现(i - 1, i + 1) … (i + 1, i - 1) …(i + 2, i - 1)…,等坐标的表示
这里，Y对应行，X对应列！
不过这里没关系，反正是中心对称的攻击范围
//方向数组： final int[] pointX = {-1, 1, 0, 1, -1, 0, 1, -1}; final int[] pointY = {0, 0, 1, 1, 1, -1, -1, -1};
3.2 区域2：对attack盘进行标记
其实本身皇后的攻击范围就是这么大，只不过棋盘就这么大
另一方面，这样写可读性高，减少很多判断语句
可以写递归，也可以写多重判断，这里我选择以下方法
加上刚才的方向数组，大大增加可读性!
for (int i = 1; i <= aT.size(); i++) { //保证覆盖整个整个棋盘 for (int j = 0; j < 8; j++) { int iX = col + i * pointX[j]; int iY = row + i * pointY[j]; //棋盘内即可改为‘1’ if(iX < aT.size() && iX >= 0 && iY < aT.size() && iY >= 0) { aT.get(iY).set(iX, '1'); } } }
3.3 测试
这里我提供里一个正解来测试，四条语句依次取消注释进行
putOn(queenBoard, attack, 0, 1); putOn(queenBoard, attack, 1, 3); putOn(queenBoard, attack, 2, 0); putOn(queenBoard, attack, 3, 2); for(int i = 0; i < queenBoard.size(); i++) { System.out.print(queenBoard.get(i)); System.out.print(" "); System.out.println(attack.get(i)); }
我改以下数据，扩大棋盘，效果更明显：
public static final int N = 8; putOn(queenBoard, attack, 4, 4); for(int i = 0; i < queenBoard.size(); i++) { System.out.print(queenBoard.get(i)); System.out.print(" "); System.out.println(attack.get(i)); }
4. 递归设计
public static void research(List<List<Character>> qB, List<List<Character>> aT , int row) { //区域一：递归出口1 //区域二： }
两个棋盘是必须的，存放数值嘛
重点参数row，只要能达到 N，就说明N个皇后已经放好！
row代表行，一行一行的测
测到第N行，（为棋盘外）
public static List<List<List<Character>>> history = new ArrayList<>();
全局性质的一个记录顺序表（三维的）
4.1 区域一：成功的递归出口
if(row == N) { List<List<Character>> tmp = new ArrayList<>(); for (List<Character> list : qB) { tmp.add(new ArrayList<>(list)); } history.add(tmp); return; }
这个递归出口是正解的递归出口
4.1.1 深拷贝
与二维数组一样，二维顺序表的拷贝也有讲究
这里我用的是顺序表的构造方法来拷贝
List<Character>，拷贝每一个这类型的引用，指向同一个对象
而我们应该拷贝对象的对象！
也就是如下代码的含义
List<List<Character>> tmp = new ArrayList<>(); for (List<Character> list : qB) { tmp.add(new ArrayList<>(list)); }
4.2 区域二：一次递归所需要经历的
循环语句加判断语句，对当前行每一列进行判断，符合就可以放置
对攻击盘，进行备份，以便回溯的时候能够恢复状态
放置
进入下一行
回归，复原
for (int i = 0; i < N ;i++) { if (aT.get(row).get(i) == '0' && row < N) { //浅拷贝了 // List<List<Character>> tmp = new ArrayList<>(aT);//备份 //深拷贝备份 List<List<Character>> tmp = new ArrayList<>(); for (List<Character> list : aT) { tmp.add(new ArrayList<>(list)); } //放置 putOn(qB, aT,row, i); //进入下一行 research(qB, aT, row + 1); //回归，复原 aT = tmp; qB.get(row).set(i, ' '); } }
4.3 测试
这里我在放置以及复原时就打印一次，用的也是刚才的打印方法
就这样继续下去~ ~ ~
5. 大测试
research(queenBoard, attack,0); for (int i = 0; i < history.size(); i++) { System.out.println("第" + (i + 1) + "解："); for (int j = 0; j < N; j++) { System.out.println(history.get(i).get(j)); } }
改以下数值： public static final int N = 8;
测试成功
接下来是力扣，需要修改哦！
List<String>,做一个可以将我们的二维顺序表转化为这个类型的方法（空格变为 . )
原本是char[] 类型有优势，因为可以直接构造字符串【我到这里很后悔！对不起xdm】
虽然有toArray方法，但是不能是基本数据类型的数组！
public static List<String> change(List<List<Character>> queenBoard) { List<String> list = new ArrayList<>(); for (int i = 0; i < N; i++) { StringBuilder stringBuilder = new StringBuilder(); for (int j = 0; j < N; j++) { stringBuilder.append(queenBoard.get(i).get(j)); } list.add(stringBuilder.toString()); } return list; }
下面是提交力扣代码
不好意思，我没考虑到这个问题，导致转化花了特别多时间，所有代码运行速率慢
可以再用char[ ] [ ] 数组做一遍哦，效率更快！思路一致
class Solution { public List<List<String>> solveNQueens(int n) { N = n; List<List<Character>> queenBoard = new ArrayList<>(); List<List<Character>> attack = new ArrayList<>(); //初始化 for(int i = 0; i < N; i++) { queenBoard.add( new ArrayList<Character>() { { for(int i = 0; i < N; i++) { add('.'); } } } ); } for(int i = 0; i < N; i++) { attack.add( new ArrayList<Character>() { { for(int i = 0; i < N; i++) { add('0'); } } } ); } research(queenBoard, attack,0); return history; } public int N = 8; public List<List<String>> history = new ArrayList<>(); public void putOn(List<List<Character>> qB, List<List<Character>> aT , int row, int col) { qB.get(row).set(col, 'Q'); aT.get(row).set(col, '1'); final int[] pointX = {-1, 1, 0, 1, -1, 0, 1, -1}; final int[] pointY = {0, 0, 1, 1, 1, -1, -1, -1}; for (int i = 1; i <= aT.size(); i++) { for (int j = 0; j < 8; j++) { int iX = col + i * pointX[j]; int iY = row + i * pointY[j]; if(iX < aT.size() && iX >= 0 && iY < aT.size() && iY >= 0) { aT.get(iY).set(iX, '1'); } } } } public void research(List<List<Character>> qB, List<List<Character>> aT , int row) { if(row == N) { List<String> ret = change(qB); history.add(ret); return; } for (int i = 0; i < N ;i++) { if (aT.get(row).get(i) == '0' && row < N) { List<List<Character>> tmp = new ArrayList<>(); for (List<Character> list : aT) { tmp.add(new ArrayList<>(list)); } putOn(qB, aT,row, i); research(qB, aT, row + 1); aT = tmp; qB.get(row).set(i, '.'); } } } public List<String> change(List<List<Character>> queenBoard) { List<String> list = new ArrayList<>(); for (int i = 0; i < N; i++) { StringBuilder stringBuilder = new StringBuilder(); for (int j = 0; j < N; j++) { stringBuilder.append(queenBoard.get(i).get(j)); } list.add(stringBuilder.toString()); } return list; } }
文章到此结束！谢谢观看
可以叫我 小马，我可能写的不好或者有错误，但是一起加油鸭🦆！
这是我的代码仓库！（在马拉圈的23.2里）代码仓库
八皇后问题 · 具体代码位置
邮箱：2040484356@qq.com
