骑士之旅问题的解决是否取决于骑士移动的顺序？

Question

你好，我目前正在 Geeksforgeeks 阅读骑士巡回赛问题 https://www.geeksforgeeks.org/the-knights-tour-problem-backtracking-1 我正在自己测试代码，当我改变顺序时骑士按代码移动

 let xMove = [ 2, 1, -1, -2, -2, -1, 1, 2 ];
 let yMove = [ 1, 2, 2, 1, -1, -2, -2, -1 ];

至此

let xMove = [1,1,-1,-1,2,2,-2,-2]
let yMove = [2,-2,-2,2,-1,1,-1,1]

而且问题似乎没有得到解决。这个问题是否依赖于马移动的顺序或者它的原因是什么？据我了解，递归将搜索所有可能的动作，所以应该没有区别吧？

Answer 1

...and the problem seems doesn't reach to solution

这正是Wikipedia上也提到的问题：

A brute-force search for a knight's tour is impractical on all but the smallest boards. For example, there are approximately 4×10⁵¹ possible move sequences on an 8×8 board, and it is well beyond the capacity of modern computers (or networks of computers) to perform operations on such a large set.

您从 GfG 引用的实现中的移动顺序是幸运顺序。对于您测试过的订单，回溯量是巨大的。人们可以想象，在道路的一开始就采取正确的行动是至关重要的。如果一个早期的动作是错误的，那么在递归树的更深的节点中将会发生大量的回溯。

有一个启发式方法可以大大减少要考虑的步数，大多数时候只有 1 个：这是 Warnsdorff's rule:

The knight is moved so that it always proceeds to the square from which the knight will have the fewest onward moves. When calculating the number of onward moves for each candidate square, we do not count moves that revisit any square already visited. It is possible to have two or more choices for which the number of onward moves is equal; there are various methods for breaking such ties,...

在 8×8 棋盘的情况下，没有打破平局的实际需要：回溯将解决错误的选择。但是现在搜索树很窄，这不会导致很多回溯，即使我们运气不好。

这是一个可运行的 JavaScript 片段中的实现。它故意随机打乱移动列表，并在需要回溯时打印“回溯”，以便您可以在不同的运行中进行试验。这将表明这总是找到平均几乎没有任何回溯的解决方案：

class Solver {
    constructor(size) {
        this.size = size;
        this.grid = Array.from({length: size}, () => Array(size).fill(-1));
    }
    toString() {
        return this.grid.map(row => 
            row.map(i => (i + "").padStart(2, "0")).join(" ")
        ).join("\n");
    }
    liberty(x, y) {
        // Count the number of legal moves
        return [...this.getMoveList(x, y)].length;
    }
    *getMoveList(x, y) {
        // Get list of legal moves, in random order
        let moves = [[1, 2], [1, -2], [-1, -2], [-1, 2],
                     [2, -1], [2, 1], [-2, -1], [-2, 1]];
        // Shuffle moves randomly
        for (var i = moves.length - 1; i > 0; i--) {
            var j = Math.floor(Math.random() * (i + 1));
            [moves[i], moves[j]] = [moves[j], moves[i]]; // Swap
        }
        // Yield the valid positions that can be reached
        for (let [moveX, moveY] of moves) {
            if (this.grid[x + moveX]?.[y + moveY] == -1) {
                yield [x + moveX, y + moveY];
            }
        }
    }
    getBestMoveList(x, y) {
        // Get list of move(s) that have the least possible follow-up moves
        let minLiberty = 100000;
        const bestMoves = [];
        // Consider every legal move:
        for (let [nextX, nextY] of this.getMoveList(x, y)) {
            let liberty = this.liberty(nextX, nextY);
            if (liberty < minLiberty) {
                minLiberty = liberty;
                bestMoves.length = 0; // Empty the array
            }
            if (liberty == minLiberty) bestMoves.push([nextX, nextY]);
        }
        if (Math.random() >= 0.5) bestMoves.reverse();
        return bestMoves;
    }
    solve(x, y, moveCount=0) {
        this.grid[x][y] = moveCount++;
        if (moveCount == this.size * this.size) return true;
        // Try all of the BEST next moves from the current coordinate x, y
        for (let [nextX, nextY] of this.getBestMoveList(x, y)) {
            if (this.solve(nextX, nextY, moveCount)) return true;
        }
        console.log("backtrack");
        this.grid[x][y] = -1;
        return false;
    }
}    

// Driver code
const solver = new Solver(8);
let success = solver.solve(0, 0);
console.log(success ? solver.toString() : "Solution does not exist");

骑士之旅问题的解决是否取决于骑士移动的顺序？

Does Knight tour Problem solve depend on sequence of knight move?

algorithm

recursion

knights-tour