ナイトツアーの異常動作

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 0 0" は5×5の行列を生成し、ここでは座標0から始まります実行すると、あなたはそれが開始されたとき、それは、完全にアップ13時まで働く見ることができるようにそれは

[ 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 ] 

次のようになりますそれ自体を繰り返す。なぜ私の再帰関数がこれを行うのか分かりません。どんな助けもありがとう。ありがとうございました

Answer 1

私はあなたのコードを正しく理解していれば、再帰ブルートフォースを使用してmxnボードのナイトツアーを見つけることができます。

ソリューションにつながっていない再帰呼び出しがボードを変更するが、変更されたボード値をクリアするためにバックトラックしないため、エラーが発生している可能性があります。 board[x][y]==0が失敗するため、他の再帰呼び出しが解決策を見つけることができません。

解決策の1つは、すべての再帰呼び出しにボードのコピーを渡し、最後にボードを返すことです。

また、bruteforceを使用すると、実行時間が指数関数的に漸近的に増加するため、より大きなボードのツアーを見つけることはおそらく期待できません。

編集：タイプミス EDIT2：多くのメモリを使用することになり、各コールでボード全体のコピーを作成追加可能な解決策

Answer 2

。私はあなたがKnights_tourに解決策が見つかったときに真であるブールを返すことによってそれを避けることができると思います。戻り値は、ボード[x] [y]の設定を解除するかどうか決定するためにスタックを巻き戻すときに使用できます。

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