Hello I am currently reading at the knight tour problem at Geeksforgeeks https://www.geeksforgeeks.org/the-knights-tour-problem-backtracking-1 I am testing the code bymyself and when I change the sequence of knight moves at the code

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

to this

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

and the problem seems doesn't reach to solution. Does this probem relies on the sequence of the knight moves or what is the cause of it? as to my understanding, the recursion will search all possible moves so it should not be difference right?

CodePudding user response：

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

This is exactly the problem that is also mentioned on 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.

The order of moves in the implementation you quote from GfG, is a lucky order. With the order that you have tested with, the amount of backtracking is enormous. One can image that taking the right moves in the very beginning of the path is crucial. If one of the early moves is wrong, there will be a tremendous amount of backtracking taking place in the deeper nodes of the recursion tree.

There is a heuristic that greatly reduces the number of moves to consider, most of the time only 1: this is 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,...

In the case of an 8×8 board there is no practical need for breaking ties: the backtracking will resolve wrong choices. But as now the search tree is very narrow, this does not lead to a lot of backtracking, even if we're unlucky.

Here is an implementation in a runnable JavaScript snippet. It intentionally shuffles the list of moves randomly, and prints "backtracking" whenever it needs to backtrack, so that you can experiment on different runs. This will show that this always finds the solution with hardly any backtracking on average:

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