骑士之旅异常行为

Question

这是我的骑士巡回赛问题的代码，我一直在绞尽脑汁想找出问题所在。

#include <iostream>
#include <vector>
using namespace std;
void Knights_tour(int x, int y, int move_count);
bool isSafe(int x, int y);

int m,n,start_x,start_y;
int valid_x [8] = {2,2,-2,-2,1,1,-1,-1};
int valid_y [8] = {1,-1,1,-1,2,-2,2,-2};
vector<vector<int>> board;


int main(int argc, char* argv[])
{
    m=atoi(argv[1]);
    n=atoi(argv[2]);
    start_x=atoi(argv[3]);
    start_y=atoi(argv[4]);

    board.resize(m);

    for(int i=0; i<m; i++)
        board[i].resize(n);

    Knights_tour(start_x, start_y, 1);

    for(int i=0; i<m; i++)
    {
        for(int j=0; j<n; j++)
        {
            cout<<"[  "<<board[i][j]<<"  ]";
        }
        cout << endl;
    }

    return(0);
}
void Knights_tour(int x, int y, int move_count)
{
    board[x][y]=move_count;
    if(move_count==(m*n))
    {
        cout << "Success!" << endl;
        return;
    }
    for(int i=0; i<8; i++)
    {

        if(isSafe((valid_x[i]+x), (valid_y[i]+y)))
        {
            move_count++;
            Knights_tour((valid_x[i]+x), (valid_y[i]+y), move_count);
        }
    }
}
bool isSafe(int x, int y)
{
    if(x>=0 && x<n && y>=0 && y<m && board[x][y]==0)
        return true;
    else
        return false;
}

它通过命令行获取板的尺寸以及起始坐标。例如，运行 "./Knight 5 5 0 0" 产生一个 5x5 矩阵并从坐标 0 开始。这是

的样子

[  1  ][  18  ][  16  ][  12  ][  15  ]
[  17  ][  13  ][  13  ][  7  ][  15  ]
[  17  ][  2  ][  9  ][  4  ][  11  ]
[  14  ][  18  ][  6  ][  14  ][  8  ]
[  8  ][  16  ][  3  ][  10  ][  5  ]

如您所见，它在 13 点之前一直运行良好，那时它开始自我重复。我不明白为什么我的递归函数会这样做。任何帮助，将不胜感激。谢谢

Answer 1

如果我对你的代码的理解正确，你正在尝试使用递归暴力尝试所有可能的解决方案来找到一个 mxn 板的骑士之旅。

发生该错误的原因可能是未导致解决方案的递归调用仍在修改电路板，但不会回溯以清除修改后的电路板值。由于 board[x][y]==0 失败，其他递归调用无法找到解决方案。

一个解决方案是将棋盘的副本传递到每个递归调用，然后 return 最后传递棋盘。

此外：使用暴力破解，您可能无法期望找到更大的电路板，因为运行时间呈指数渐近增长。

编辑：错别字 edit2：添加了可能的解决方案

Answer 2

在每次调用时创建板的完整副本会占用大量内存。我认为您可以通过使用 Knights_tour return 一个 bool 来避免它，当找到解决方案时该 bool 为真。展开堆栈时可以使用 return 值来决定是否应该取消设置 board[x][y]。

if(!Knights_tour((valid_x[i]+x), (valid_y[i]+y), move_count))
{
    board[x][y] = 0;
}

骑士之旅异常行为

Knight's tour abnormal behavior

c++

knights-tour