回溯优化

Question

最近我试图解决着名的little bishops算法问题。在我阅读的其中一个网站中，我应该将棋盘分成黑白部分以优化执行。之后，我应该使用回溯来统计可能的方法，以便将主教分成黑色方块和白色方块。

在下面的代码中，我尝试将6个主教放在8乘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秒计数可能的方式把所有的主教只白色方块数。你能帮我吗？我究竟做错了什么？

Answer 1

这里有几个方法来改善您的搜索。

（1）您可以考虑有限域搜索，而不是生成和测试，其中每个主教都有可能位置的“域”。每当你放置一位主教时，你就会修剪剩余主教的领域。如果主教的域名变空了，你必须回溯。 （2）作为一种改进，如果你有n个主教可以放置，并且还有其他个地方，你必须回溯。 （3）使用动态编程/记忆，其中存储1主教，2主教，...的解决方案，并计算n组主体解决方案中n + 1主教解决方案的集合。

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

（5）试着找到一个更好的表示。例如，位模式。 （6）如果使用不同的表示法，请使用“trail”（比较Prolog）来跟踪在回溯时需要撤销的操作。

干杯！