1

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

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

//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;
}

尽管我可以理解为什么将棋盘划分为白色和黑色方块可以优化问题，但仍然需要大约 11 秒来计算将所有主教只放在白色方块上的可能方法的数量。你能帮我吗？我究竟做错了什么？

4

1 回答 1

4

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

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

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

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

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

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

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

干杯!

于 2013-06-03T00:00:49.057 回答