algorithm - 回溯优化

Question

最近我试图解决著名的little bishops算法问题。在我读到的一个网站中，我应该将棋盘分为黑色和白色部分以优化执行。之后，我应该使用回溯来计算将主教分别放在黑色方 block 和白色方 block 上的可能方法的数量。

在下面的代码中，我尝试将 6 个象仅放在 8 x 8 棋盘的白色方 block 上。我这样做只是为了验证该技术是否真的有效。

//inside main function
int k = 6; //number of bishops
int n = 8; //length of one side of chessboard
Integer[] positions = new Integer[k];

long result = backtrack(positions, 0, n);

//find how many times we double counting each possible combination of bishops
int factor = 1;
for(int i = k; i>0; i--) {
    factor = factor * i;
}
System.out.println("The result is " + result/factor);


//implementation of other functions
public long backtrack(Integer[] prevPositions, int k, int n) {

    if(k == 6) {
        return 1;
    }
    long sum = 0;

    Integer[] candidates = new Integer[n*n];
    int length = getCandidates(prevPositions, k, candidates,  n);

    for(int i=0 ; i<length ; i++) {            
        prevPositions[k] = candidates[i];
        sum += backtrack(prevPositions,k+1,n);
    }

    return sum;
}

public Integer getCandidates(Integer[] prevPositions, int k, Integer[] candidates, int n) {
    int length = 0;
    //only white squares are considered as candidates, hence i+=2
    for (int i = 0; i < n*n; i+=2) {
        boolean isGood = true;
        int iRow = i / n;
        int iCol = i % n;

        for (int j = 0; j < k; j++) {
            int prev = prevPositions[j];
            if (i == prev) {
                isGood = false;
                break;
            } else {
                int prevRow = prev / n;
                int prevCol = prev % n;
                if (Math.abs(iRow - prevRow) == Math.abs(iCol - prevCol)) {
                    isGood = false;
                    break;
                }
            }
        }

        if(isGood) {
            candidates[length] = new Integer(i);
            length++;
        }
    }
    return length;
}

尽管我明白为什么将棋盘分成白色和黑色方 block 可以优化问题，但仍然需要大约 11 秒来计算将所有象仅放在白色方 block 上的可能方法的数量。你能帮我吗？我做错了什么？

Answer 1

这里有一些改进搜索的方法。

(1) 除了生成和测试，您可以考虑有限域搜索，其中每个主教都有一个可能位置的“域”。每当你放置主教时，你就会修剪剩余主教的领域。如果主教的领域变空了，你必须回溯。

(2) 作为一个改进，如果你有 n 个主教要放置并且还剩下 m < n 个地方，你必须回溯。

(3) 使用动态规划/记忆化，存储 1 个主教、2 个主教...的解决方案，并从 n 个主教解决方案的集合中计算出 n + 1 个主教解决方案的集合。

(4) 利用对称性来减少搜索空间。在这种情况下，(至少)存在黑/白对称和旋转/反射对称。

(5) 尝试找到更好的表示。例如，位模式。

(6) 如果您使用不同的表示，请考虑使用“trail”(参见 Prolog)来跟踪您需要在回溯时撤消的操作。

干杯!