Money is not everything. There's MasterCard.
金钱不是万能的, 有时还需要信用卡。
背景
大话西游之月光宝盒这部电影已经刷了N遍了。每一次看都有每一次的感悟。如果时光可以到倒流,我当初就不应该。。。 悔不当初,悔不当初。
虽然世界上没有后悔药,但是算法界却是有后悔药的,呢就是---回溯算法。人生不能时光倒流,呢我让我的算法时光倒流。
八皇后问题最早是由国际象棋棋手马克斯·贝瑟尔于1848年提出的,现在都21世纪了,八皇后怎么能满足我,我决定实现一个N皇后,我想要几个皇后就要几个皇后。
所有源码均已上传至github:链接
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
您的点赞和关注是对我最大的支持,谢谢!