骑士巡回赛持续时间太长 [英] Knights tour backtracking lasts too long

问题描述

在8x8板上进行回溯可以解决骑士巡回赛的问题持续多长时间?因为我的算法已经准备好了某种时间，而且似乎无法完成.但是，当我尝试使用6x6或5x5电路板时，它可以成功完成.

How long does it last to solve the knights tour problem with backtracking on an 8x8 board? Because my algo allready computes somehow too long and it seems, like it wont finish. But when I try a 6x6, or 5x5 board, it finishes succesfuly.

代码:

class KnightsTour{

private boolean[][] board;
private int count, places;
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)
};

public KnightsTour(int n) {
    board = new boolean[n][n];
    places = n*n;
    count = 0;
     }

public boolean ride(int x, int y) {


    board[x][y] = true;
    count++;

    if (count == places) {
        return true;
    }

    for (Point p : moves) {
        int nextX = x + p.x;
        int nextY = y + p.y;

        if (nextX < 0 || nextX >= board.length || nextY < 0 || nextY >= board.length || board[nextX][nextY]) {
            continue;
        } 
        if (ride(nextX, nextY)) {
            return true;
        }
    }

    board[x][y] = false;
    count--;

    return false;
}
}

推荐答案

我遇到了同样的问题.一切都顺利进行，直到n = 7，突然之间，要计算n=8总是要花很多时间.我希望这对某人有帮助:)

I came across the same problem. Everything runs smoothly till n=7 and suddenly it takes forever to calculate for n=8. I hope this helps someone :)

问题在于检查移动的顺序.您正在使用:

The problem lies with the order in which you are checking for the moves. You are using :

xMove[8] = { -2, -2, 2, 2, -1, -1, 1, 1}

yMove[8] = { -1, 1, -1, 1, -2, 2, -2, 2}

如果将这些向量绘制在2D平面中，则会随意放置它们.换句话说，它们不是以顺时针或逆时针方式排序的.考虑一下:

If you plot these vectors in the 2D plane, they are haphazardly placed. In other words, they are not ordered in either a clockwise or an anti-clockwise manner. Consider this instead :

xMove[8] = { 2, 1, -1, -2, -2, -1, 1, 2 }

yMove[8] = { 1, 2, 2, 1, -1, -2, -2, -1 }

如果绘制这些矢量，它们将按逆时针圆整齐地排列. 某种程度上，这导致对于n的较大值，递归运行得非常快.请注意，从n=9开始，仍然需要永远计算.

If you plot these vectors, they are neatly arranged in an anticlockwise circle. Somehow this causes the recursion to run much quickly for large values of n. Mind you, it still takes forever to calculate for n=9 onwards.

这篇关于骑士巡回赛持续时间太长的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！