c++ - 使用递归的骑士巡回算法

Question

我一直在编写代码来解决奈特的游览问题。我写了这段代码，现在有点困惑。我重新阅读并分析了几次，但未能找到导致问题的错误。我将不胜感激任何帮助。

#include <iostream>
const int N = 5; // size of table
int moves_table[2][8] = { { 1, 2, 2, 1, -1, -2, -1, -1 }, { -2, -1, 1, 2, -1, -2, -2, -1 } }; //my moves table that i use to increment or decrement my x and y cordinates
int THETABLE[N][N] = { 0 }; //all elements of table equal to zero
bool iknight_tour(int x, int y, int r); // this function will return true if Knight is able to be on every place on chessmate, without being twice at the same place, starting from TABLE[x][y]
bool if_move_correct(int x, int y); //checks if move can be done
int main()
{
    bool some_variable = iknight_tour(0, 0, 1); 
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            std::cout << THETABLE[i][j] << "\t";
        }
        std::cout << std::endl;
    }
    std::cout << std::endl;
    std::cout << some_variable;
    std::cout << std::endl;

    return 0;
}
bool if_move_correct(int x, int y)
{
    if (x < N && x >= 0 && y < N && y >= 0 && THETABLE[x][y] == 0)
    {
        return true;
    }
    else
    {
        return false;
    }
}
bool iknight_tour(int x, int y, int r)
{
    THETABLE[x][y] = r;
    if (r == N*N)
    {
        return true;
    }
    else
    {
        for (int i = 0; i < 8; i++)
        {
            {
                if ((if_move_correct(x + moves_table[0][i], y + moves_table[1][i]))==true)
                {
                    if((iknight_tour(x + moves_table[0][i], y + moves_table[1][i], r + 1))==true)
                    {
                        return true;
                    }
                }   
            }
        }
        THETABLE[x][y] = 0;
    }   
    return false;
}

例如对于 i_kinghtour(0,0,1) 我得到:
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0

我应该得到:
1 20 17 12 3
16 11 2 7 18
21 24 19 4 13
10 15 6 23 8
25 22 9 14 5

Answer 1

这会移动表格:

int moves_table[2][8] = { { 1,  2,  2, 1, -1, -2, -1, -1 }, 
                          { -2, -1, 1, 2, -1, -2, -2, -1 } }; 

看起来很奇怪。 -1,-1 出现两次，-2,-2 出现。

也许它会更好地工作:

int moves_table[2][8] = { { 1,  2,  2, 1, -1, -2, -2, -1 }, 
                          { -2, -1, 1, 2, -2, -1,  1,  2 } };