騎士之旅 - 導致無限循環，我無法弄清楚爲什麼

Question

我試圖用回溯來解決騎士的旅程問題。我認爲我應該使用的算法。我試過了，但我無法弄清楚它爲什麼不起作用。它導致無限循環。

但是，如果我註釋掉回線solutionBoard[dst.x][dst.y]=-1;它的作品！ 我只是不明白爲什麼！ 任何幫助，將不勝感激。

private int solutionBoard[][] = new int [8][8]; 

// The eight possible moves a knight can make from any given position 
private static final Point[] MOVES = new Point[] { new Point(-2, -1), 
     new Point(-2, 1), new Point(2, -1), new Point(2, 1), 
     new Point(-1, -2), new Point(-1, 2), new Point(1, -2), 
     new Point(1, 2) }; 

private int count = 0; 

public KnightsTour_DFS(){ 
    // board is 0- 7 
    //initialize visited 
    for(int i =0; i<8;i++){ 
     for(int j = 0; j< 8; j++){ 
      solutionBoard[i][j] = -1; 
     } 
    } 

    solutionBoard[0][0]=count++; 
    if(findTour(0, 0)){ 
     System.out.println("Tour found!!"); 
     printSolution(); 
    } 
} 

public boolean findTour(int x, int y){ 
    if(x <0 || y <0 || x>7 || y > 7){ 
     return false; 
    } 
    if(count == 64){ 
     //we've covered all node 
     return true; 
    } 
    for(int i = 0; i < this.MOVES.length; i++){ 
     Point dst = new Point(x + MOVES[i].x, y + MOVES[i].y); 
     if(canMove(dst)){ 
      solutionBoard[dst.x][dst.y]=count++; 
      if(findTour(dst.x, dst.y)){ 
       System.out.println("Solution shown on board\n"); 
       return true; 
      } 
      else{ 
       count --; 
       solutionBoard[dst.x][dst.y]=-1; 
      } 
     }  
    } 
    return false; 
} 

private void printSolution() { 
    System.out.println("Solution shown on board\n"); 
    for (int[] rows : solutionBoard) { 
     for (int r : rows) { 
      System.out.printf("%2d ", r); 
     } 
     System.out.println(); 
    } 
} 
public boolean canMove(Point destination){ 
    if(destination.x<0 || destination.y<0 || destination.x>7|| destination.y>7){ 
     return false; 
    } 
    if(solutionBoard[destination.x][destination.y] != -1){ 
     //already visited 
     return false; 
    } 
    return true; 
} 

Answer 1

你的算法似乎工作得很好，對於較小的問題實例（如5x5或7x7板）產生正確的結果。這似乎是8x8 board is just too big for the brute force /回溯方法。

不過，您可以簡化findTour方法，使它更容易理解和調試：

public boolean findTour(int x, int y, int c) { 
    solutionBoard[x][y] = c; 
    if (c == size*size) { 
     return true; 
    } 
    for (Point p : MOVES) { 
     Point dst = new Point(x + p.x, y + p.y); 
     if (canMove(dst) && findTour(dst.x, dst.y, c + 1)) { 
      return true; 
     }  
    } 
    solutionBoard[x][y] = -1; 
    return false; 
} 

例，輸出爲findTour(0, 0, 1)與size = 7（需要適應所有代碼可變大小！）

1 14 3 38 5 34 7 
12 39 10 33 8 37 26 
15 2 13 4 25 6 35 
40 11 32 9 36 27 44 
19 16 21 24 45 48 29 
22 41 18 31 28 43 46 
17 20 23 42 47 30 49  

更好：使用維基百科文章中提到的其他算法之一，例如相當簡單的Warnsdorff啓發式："We move the knight so that we always proceed to the square from which the knight will have the fewest onward moves."我們可以通過排序來移動...

public Point[] sortedPoints(final int x, final int y) { 
    Point[] sorted = Arrays.copyOf(MOVES, MOVES.length); 
    Arrays.sort(sorted, new Comparator<Point>() { 
     public int compare(Point p1, Point p2) { 
      return Integer.signum(nextMoves(p1) - nextMoves(p2)); 
     }; 
     private int nextMoves(Point p) { 
      Point dst = new Point(x + p.x, y + p.y); 
      if (canMove(dst)) { 
       int s = 0; 
       for (Point m : MOVES) { 
        Point dst2 = new Point(dst.x + m.x, dst.y + m.y); 
        if (canMove(dst2)) { 
         s++; 
        } 
       } 
       return s; 
      } else { 
       return 999; 
      } 
     } 
    }); 
    return sorted; 
} 

...並將後續循環更改爲for (Point p : sortedPoints(x, y))。結果：

size  findTour calls without and with heuristic 
5x5      76497  25 
7x7      8947880  49 
8x8      ???   64 
20x20     ???   400 

事實上，我嘗試了各種規模的findTour方法被調用正是size^2倍，即它發現在第一次嘗試之旅，不回溯的。