八皇后问题百度解法的缓存没弄明白

我在百度上面看到八皇后的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

回到顶部