ナイトツアーが正しく動作しない

Question

私はこのナイトツアーの問題を解決する必要があります。 NxN行列とナイトの座標を入力する必要があります。ここで、（1,1）は左下の要素です。今プログラムが正しく動作しますが、私の問題は、タスクには多くの入力があることがあるということです。だから私はmain関数にwhileループを追加しています（入力を継続して解決することができますが、最初の入力の後にプログラムがコンソールに書き込むことはできません）私にできる事は、コンソールを停止しているあなたは私の問題で私を助けてください事前に感謝を

#include <iostream> 

using namespace std; 

const int MAXN = 10; 
const int MAXD = 10; 

const int maxDiff = 8; 

const int diffX[MAXD] = { 1, 1, -1, -1, 2, -2, 2, -2 }; 
const int diffY[MAXD] = { 2, -2, 2, -2, 1, 1, -1, -1 }; 

unsigned board[MAXN][MAXN]; 
unsigned newX, newY; 

void printBoard(int n) 
{ 
int i, j; 
for (i = n; i > 0; i--) { 
    for (j = 0; j < n; j++) 
    { 
     if (j == 0) 
     { 
      cout << board[i - 1][j]; 
     } 
     else 
     { 
      cout << " " << board[i - 1][j]; 
     } 
    } 
    cout << endl; 
} 
} 

void nextMove(int X, int Y, int i, int n) 
{ 
int k; 
board[X][Y] = i; 
if (i == n * n) 
{ 
    printBoard(n); 
    return; 
} 

for (k = 0; k < maxDiff; k++) 
{ 
    newX = X + diffX[k]; newY = Y + diffY[k]; 
    if ((newX >= 0 && newX < n && newY >= 0 && newY < n) && (0 ==    board[newX][newY])) 
    { 
     nextMove(newX, newY, i + 1, n); 
    } 
} 
board[X][Y] = 0; 
} 

int main() 
{ 
int n; 
int startX; 
int startY; 
int br = 0; 
while (cin >> n >> startX >> startY) 
{ 
    if (n < 4 || n > 10) 
    { 
     break; 
    } 
    int i, j; 
    for (i = 0; i < n; i++) 
    { 
     for (j = 0; j < n; j++) 
     { 
      board[i][j] = 0; 
     } 
    } 
    nextMove(startX - 1, startY - 1, 1, n); 
} 
return 0; 
} 

編集：。？。どうやら私は条件を間違えIマトリックスは、しかし2 < nは< 10でなければなりません。プログラムが5未満のマトリクスで動作しない条件を変更してください。何が間違っているのですか？

Answer 1

1. 騎士ツアーはHaの特別なケースですミルティアンパス問題は一般にNP困難である。ヒューリスティックは、解を線形時間内に首尾よく見つけることができる。
2. （m≤nの場合）、これらの3つの条件の1つ以上が満たされない限り、クローズドナイトツアーは常に可能です。
   • mおよびn
   奇数M = 1、2、または4
   • M = 3、N = 4、6、または8 wiki

あなたが共にbruit-forceアプローチを使用します。したがって、それは解決策が見つからない場合に突き当たります。

最初の入力後にプログラムがnextMove()が解決策を見つけた後に実行し続けているので、私はもう

を書くことはできません。あなたはフラグ

if (i == n * n) 
{ 
    printBoard(n); 
    global_flag=true; 
    return; 
} 

を置き、

if ((newX >= 0 && newX < n && newY >= 0 && newY < n) && (0 == board[newX]newY])) 
{ 
    nextMove(newX, newY, i + 1, n); 
    if(global_flag) return; 
} 

に、このフラグをチェックする必要がありますループ