Money is not everything. There's MasterCard.
金钱不是万能的, 有时还需要信用卡.
背景
大话西游之月光宝盒这部电影已经刷了 N 遍了. 每一次看都有每一次的感悟. 如果时光可以到倒流, 我当初就不应该... 悔不当初, 悔不当初.
虽然世界上没有后悔药, 但是算法界却是有后悔药的, 呢就是 --- 回溯算法. 人生不能时光倒流, 呢我让我的算法时光倒流.
八皇后问题最早是由国际象棋棋手马克斯. 贝瑟尔于 1848 年提出的, 现在都 21 世纪了, 八皇后怎么能满足我, 我决定实现一个 N 皇后, 我想要几个皇后就要几个皇后.
所有源码均已上传至 GitHub: 链接 https://github.com/chaoaiqi/study
N 皇后
思考
家家有本难念的经, 一个皇后已经了不得了. 这 N 皇后嘛, 可得好好处理, 不能让她们打架. 可以先声明一个大小为 N 的一维数组, 来存储我的这 N 位皇后. 然后分成 N 个阶段.
第一个阶段随便选一个位置.
第二个阶段需要判断一下我的横排, 竖排, 左对角线, 右对角线 (只需要和第一阶段和本身相比即可) 有没有皇后. 如果没有, 则继续往下走.
第三个阶段以此类推, 发现有皇后, 不慌, 没关系, 时光倒流, 到第二阶段, 重新摆放.
第 N 阶段.... 直到摆出让每一位皇后满意的位置.
大概思路就是这样.
初始化
- /**
- * 皇后数组
- */
- private int[] queens;
- /**
- * n 皇后
- */
- private int n;
- /**
- * 摆法数量
- */
- private int count;
- /**
- * 基于 8 皇后而衍生的 N 皇后
- *
- * @param n 皇后的数量
- */
- private SolveNQueens(int n) {
- queens = new int[n];
- this.n = n;
- count = 0;
}
递归
虽然代码很精简, 但是关键就在于这个递归不好理解. 循环里套递归, 很巧妙. 需要一步一步跟一下就知道了.
一维数组存储的值是皇后的位置(0,n-1).
默认是要从头开始的, 需要这么调用该方法 calNQueens(0)
- private void calNQueens(int row) {
- if (row == n) {
- printQueens(queens);
- return;
- }
- for (int col = 0; col <n; col++) {
- if (isSatisfy(row, col)) {
- queens[row] = col;
- calNQueens(row + 1);
- }
- }
}
是否满足条件
该方法需要判断自己的横竖排, 左右对角线是否有皇后.
这里为了便于理解, 所以循环里放着三个 if.
- private boolean isSatisfy(int row, int col) {
- // System.out.println("(" + row + "," + col + ")");
- int leftUp = col - 1;
- int rightUp = col + 1;
- for (int i = row - 1; i>= 0; --i) {
- if (queens[i] == col) return false;
- if (leftUp>= 0 && queens[i] == leftUp) return false;
- if (rightUp < n && queens[i] == rightUp) return false;
- --leftUp;
- ++rightUp;
- }
- return true;
}
打印
- private void printQueens(int[] queens) {
- for (int row = 0; row < n; row++) {
- for (int col = 0; col < n; col++) {
- if (queens[row] == col) System.out.print("1");
- else System.out.print("0");
- }
- System.out.println();
- }
- System.out.println();
- ++count;
}
测试代码
- public static void main(String[] args) {
- int n = 8;
- SolveNQueens solveNQueens = new SolveNQueens(n);
- solveNQueens.calNQueens(0);
- System.out.println("共计" + solveNQueens.count + "种摆法.");
}
测试结果
4 皇后
八皇后(这里是包含了旋转和对称的解的解, 否则是 12 种摆法)
end
您的点赞和关注是对我最大的支持, 谢谢!
来源: https://juejin.im/post/5c9b444b5188251d497ac498