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

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

...问题似乎无法解决

这正是维基百科上也提到的问题：

除了最小的棋盘之外，对骑士之旅进行暴力搜索是不切实际的。例如，在 8×8 的棋盘上大约有 4×10⁵¹ 种可能的移动序列，这远远超出了现代计算机（或计算机网络）在如此大的集合上执行操作的能力。

您从 GfG 引用的实现中的移动顺序是一个 lucky 顺序。根据您测试的顺序，回溯量是巨大的。可以想象，在道路的一开始就采取正确的行动是至关重要的。如果早期的某个动作是错误的，则递归树的更深节点中将会发生大量的回溯。

有一种启发式方法可以大大减少要考虑的步数，大多数时候只有 1 步：这是 Warnsdorff 规则：

马被移动，以便它总是前进到马向前移动最少的方格。在计算每个候选方格的向前移动次数时，我们不会计算重新访问任何已访问过的方格的移动次数。可以有两个或多个选择，且向前移动的次数相等；有多种方法可以打破这种关系，...

在 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");