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

Question

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

Answer 1

画个图就明白了

从左下到右上的斜线，横坐标+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，算起来复杂。