八皇后问题百度解法的缓存没弄明白
我在百度上面看到八皇后的java 解法, 发现这种解法使用了位置缓存, 判断一个皇后位置的合理性的时候, 使用rup[],lup[] 数组判断一个皇后的斜线是否有皇后, 但是没有明白backtrack 方法里面的rup[i + j] = lup[i - j + maxCount] , 为什么这里的i +j, 能够表示右上至左下是否有皇后? [i - j + maxCount] 能够表示左上至右下是否有皇后 ? 同时rup[]和lup[] 数组的大小还是2倍maxCount? 有同学能够详细说说这个解法吗?
代码如下:
public class Queener {
private int[] column; //同栏是否有皇后,1表示有
// 是否在一条斜线
private int[] rup; //右上至左下是否有皇后
private int[] lup; //左上至右下是否有皇后
private int[] queen; //解答
private int num; //解答编号(第几种答案)
private static final int maxCount = 8;
public Queener() {
column = new int[maxCount ];
queen = new int[maxCount];
rup = new int[2 *maxCount ];
lup = new int[2 * maxCount];
for (int i = 0; i < maxCount; i++)
column[i] = 0;
for (int i = 0; i < (2 * maxCount); i++)
rup[i] = lup[i] = 0; //初始定义全部无皇后
}
public void backtrack(int i) {
if (i == maxCount) {
showAnswer();
} else {
for (int j = 0; j < maxCount; j++) {
if ((column[j] == 0) && (rup[i + j] == 0) && (lup[i - j + maxCount] == 0)) {
//若无皇后
queen[i] = j; //设定为占用
column[j] = rup[i + j] = lup[i - j + maxCount] = 1;
backtrack(i + 1); //循环调用
column[j] = rup[i + j] = lup[i - j + maxCount] = 0;
}
}
}
}
protected void showAnswer() {
num++;
System.out.println("\n解答" + num);
for (int y = 0; y < maxCount; y++) {
for (int x = 0; x < maxCount; x++) {
if (queen[y] == x) {
System.out.print("Q");
} else {
System.out.print(".");
}
}
System.out.println();
}
}
public static void main(String[] args) {
long start = System.currentTimeMillis();
Queener queen = new Queener();
queen.backtrack(0);
System.out.println("耗时:" + (System.currentTimeMillis() - start));
}
}
回答:
画个图就明白了
从左下到右上的斜线,横坐标+1则纵坐标-1,所以横纵坐标之和是固定值,而且不同的斜线这个值不同,最大的情况是 7 + 7 = 14
,最小是 0 + 0 = 0
,共 15 条这样的斜线。所以这条直线如果要用标志数组,这个数组大小应该是 15(最后一个索引是 14),直接用 maxCount * 2
,即 16 包含了 索引 14,浪费一个整数,但是好算,如果精确一点是 maxCount * 2 - 1
。
从左上到右下的斜线,横坐标+1则纵坐标+1,横纵坐标之差是固定值,最大为 7 - 0 = 7
,最小为 0 - 7 = -7
,也是 15 条线。由于数组下标不能为负,所以 + maxCount
修为正整数,其范围也是 1 到 15。大小为 maxCount * 2
的数组也会浪费一个位置,但是如果不想浪费这个位置,修正偏移量就是 mxCount - 1
,算起来复杂。
以上是 八皇后问题百度解法的缓存没弄明白 的全部内容, 来源链接: utcz.com/p/944209.html