-1

所以这是我的骑士之旅问题的代码，我一直在努力找出问题所在。

#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 点，当它开始重复自己时。我无法弄清楚为什么我的递归函数会这样做。任何帮助，将不胜感激。谢谢

4

2 回答 2

1

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

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

一种解决方案是将板的副本传递给每个递归调用，然后在最后返回板。

另外：使用蛮力，您可能不会期望找到更大的电路板的游览，因为运行时间呈指数渐近增长。

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

于 2016-03-24T20:18:37.943 回答
0

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

if(!Knights_tour((valid_x[i]+x), (valid_y[i]+y), move_count))
{
    board[x][y] = 0;
}
于 2016-03-27T13:12:55.990 回答