骑士之旅递归

Question

有人能找出我的 knight's tour code 中的错误吗？我似乎找不到它，而且我得到了一个无限循环，而不是堆栈溢出

private bool heuristic(int[,] board, int x, int y, ref int jmp)
{
    if (x < 0 || x > 7 || y < 0 || y > 7 || board[x, y] > 0)
        return false;
    board[x, y] = ++jmp;
    if (jmp == 64)
        return true;

    if (heuristic(board, x + 2, y + 1, ref jmp) ||
        heuristic(board, x + 2, y - 1, ref jmp) || heuristic(board, x - 2, y + 1, ref jmp) ||
        heuristic(board, x - 2, y - 1, ref jmp) || heuristic(board, x + 1, y + 2, ref jmp) ||
        heuristic(board, x + 1, y - 2, ref jmp) || heuristic(board, x - 1, y + 2, ref jmp) ||
        heuristic(board, x - 1, y - 2, ref jmp))
        return true;
    board[x, y] = 0;
    jmp--;
    return false;
}

并调用它：

var board = new int[8,8];
var x = 0;
var y = 0;
var jmp = 0;
var result = heuristic(board, x, y, ref jmp);

我需要一个 jmp 变量，因为我正在进行多次试验并且还想显示所采用的路径。谢谢！

Answer 1

根据Wikipedia：

There are 26,534,728,821,064 [...] tours

和

A brute-force search for a knight's tour is impractical on all but the smallest boards; for example, on an 8x8 board there are approximately 4×10⁵¹ possible move sequences, and it is well beyond the capacity of modern computers (or networks of computers) to perform operations on such a large set. However, the size of this number gives a misleading impression of the difficulty of the problem, which can be solved "by using human insight and ingenuity ... without much difficulty."

骑士之旅递归

Knight's Tour recursion

c#

recursion

knights-tour