骑士之旅 - 导致无限循环，我无法弄清楚为什么 [英] Knights tour - results in an infinite loop and i can't figure out why

问题描述

我正在尝试使用回溯来解决骑士的旅行问题。我认为我的算法应该有效。我试过但我无法弄清楚它为什么不起作用。它导致无限循环。

I'm trying to solve the knight's tour problem using backtracking. I think the algorithm I have should work. I've tried but I can't figure out why it isn't working. It results in an infinite loop.

但是，如果我注释掉回溯线 solutionBoard [dst.x] [dst.y] = - 1; 它有效！
我只是不明白为什么！
任何帮助将不胜感激。

However if I comment out the line that back track solutionBoard[dst.x][dst.y]=-1; it works! I just don't understand why! Any help would be appreciated.

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

推荐答案

你的算法似乎只能工作很好，可以为较小的问题实例产生正确的结果，例如5x5或7x7板。似乎 8x8板对于蛮力 /回溯方法来说太大了。

Your algorithm seems to work just fine, yielding correct results for smaller problem instances, like a 5x5 or 7x7 board. It seems like the 8x8 board is just too big for the brute force / backtracking approach.

不过，您可以简化 findTour 方法，使其更易于理解和调试：

Still, you can simplify your findTour method, making it easier to understand and to debug:

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 （需要将所有代码调整为可变大小！）

Example-Output for findTour(0, 0, 1) with size = 7 (need to adapt all code to variable size!)

 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启发式： 我们移动骑士，以便我们始终前往骑士将向前移动最少的方格。 我们可以通过对移动进行排序来实现这一目标...

Still better: Use one of the other algorithms mentioned in the Wikipedia article, for example the rather simple Warnsdorff heuristic: "We move the knight so that we always proceed to the square from which the knight will have the fewest onward moves." We can achieve this by sorting the 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））。结果：

... and changing the successors-loop to for (Point p : sortedPoints(x, y)). Results:

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

事实上，对于我尝试过的所有尺码， findTour 方法被称为完全 size ^ 2 次，即它在第一次尝试时找到了游览，完全没有回溯。

Indeed, for all the sizes I tried, the findTour method was called exactly size^2 times, i.e. it found the tour on first try, without backtracking at all.

这篇关于骑士之旅 - 导致无限循环，我无法弄清楚为什么的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！