4

再帰についてもう少し学ぼうとしていますが、どういうわけかナイトツアーを解決できず、誰かが私の論理エラーを指摘してくれることを望んでいます。

class main {

    static int fsize = 5; // board size (5*5)
    static int board[][] = new int[fsize][fsize];
    static int[] move_x = {1, 2, 2, 1, -1, -2, -2, -1}; // possible moves (x-axis)
    static int[] move_y = {-2, -1, 1, 2, 2, 1, -1, -2}; // possible moves (y-axis)

    // x = current x coordinate
    // y = current y coordinate
    static void Solve(int move_number, int x, int y) {
        board[x][y] = move_number;

        // check whether the knight has been on all filds or not
        if (move_number == ((fsize * fsize) - 1)) {
            for (int i = 0; i < fsize; i++) {
                for (int c = 0; c < fsize; c++) {
                    System.out.printf("%3d", board[i][c]);
                }
                System.out.println("\n");
            }
        } 
        else {
            // calculate new board coordinates
            for (int i = 0; i < 8; i++) {
                for (int c = 0; c < 8; c++) {
                    // Check whether the new coordinates are valid or not
                    if ((x + move_x[i]) >= 0 && (x + move_x[i]) < fsize && (y + move_y[c]) >= 0 && (y + move_y[c]) < fsize) {
                        // check whether the knight has been on this field or not (-1 = hasn't been here)
                        if (board[x + move_x[i]][y + move_y[c]] == -1) {
                            System.out.println("Move: " + move_number + "\n");
                            // Find next field
                            Solve(move_number + 1, (x + move_x[i]), (y + move_y[c]));
                        }
                    }
                }
            }
            // couldn't find a valid move
            board[x][y] = -1;
        }
    }

    public static void main(String[] args) {
        for (int i = 0; i < fsize; i++) {
            for (int c = 0; c < fsize; c++) {
                board[i][c] = -1;
            }
        }

        Solve(0, 0, 0);
    }
}

編集：これが大丈夫だといいのですが。このプログラムを実行しようとしましたが、22を超える有効な移動を取得できませんでした。

4

4 に答える 4

2

次の 2 つのことを行うことで、コードを修正できました。

  • for (int i = 0; i < 8; i++)次の 8 つの可能性をチェックするには、単一レベルのループ のみを使用します。
    • ここに 2 つのネストされたループがあるのはなぜですか? これらの 8 つの可能性を確認したいだけです。
    • 各レベルでの動きは 64 ではなく、8 つだけです。
  • で最後board[x][y] = -1;の発言をするSolve
    • if条件に関係なくこれを実行したい
    • このレベルboard[x][y] = move_number;を終了する前に元に戻す必要があります

それらを修正した後、宿題は完了、修正、完了です。おめでとう！

疑似コードで

今、これはあなたが持っているものです：

static void Solve(int move_number, int x, int y) {
    board[x][y] = move_number;

    if (DONE) {
       PRINT;
    } else {
        for (int i = 0; i < 8; i++) {
            for (int c = 0; c < 8; c++) {
                ATTEMPT_MOVE(i, c); // doesn't make sense!!!
            }
        }
        board[x][y] = -1; // this doesn't belong here!!!
    }
}

このコードを修正するには、次のようにするだけです。

static void Solve(int move_number, int x, int y) {
    board[x][y] = move_number;

    if (DONE) {
       PRINT;
    } else {
        for (int i = 0; i < 8; i++) {
           ATTEMPT_MOVE(i); // now makes more sense!
        }
    }

    board[x][y] = -1; // must undo assignment in first line!
}

追加の提案

  • ロジックをヘルパー メソッドに分解します。つまり、ボードの印刷と有効な座標のチェックです。
于 2010-05-15T12:13:00.790 に答える
1

これが問題です-最初に試みられた移動が成功した場合でも（解決につながった場合）、別の有効な移動を試みています。関数が解に到達したかどうかを示すブール値を返すようにします。したがって、関数をそれ自体から呼び出すときは、次の有効な動きが返された場合にのみ試行する必要がありますfalse。また、別の動きを試みるときは、前の動きをクリアする必要があります (配列が変更されたため)。

編集：

class main {

static int fsize = 5; // board size (5*5)
static int board[][] = new int[fsize][fsize];
static int[] move_x = {1, 2, 2, 1, -1, -2, -2, -1}; // possible moves (x-axis)
static int[] move_y = {-2, -1, 1, 2, 2, 1, -1, -2}; // possible moves (y-axis)

// x = current x coordinate
// y = current y coordinate
static boolean solve(int move_number, int x, int y)
{
    boolean ret = true;
    board[x][y] = move_number;
    if(move_number == ((fsize * fsize) - 1))
    {
        for(int i = 0; i < fsize; i++)
        {
            for(int c = 0; c < fsize; c++)
            {
                System.out.printf("%3d", board[i][c]);
            }
            System.out.println("\n");
        }
    }
    else
    {
        for(int i = 0; i < 8; i++)
        {
            if((x + move_x[i]) >= 0 && (x + move_x[i]) < fsize
                    && (y + move_y[i]) >= 0
                    && (y + move_y[i]) < fsize)
            {
                if(board[x + move_x[i]][y + move_y[i]] == -1)
                {
                    if (solve(move_number + 1, (x + move_x[i]), (y + move_y[i]))) {
                        break;
                    }
                }
            }
        }
        ret = false;
        board[x][y] = -1;
    }
    return ret;
}
public static void main(String[] args) {
    for (int i = 0; i < fsize; i++) {
        for (int c = 0; c < fsize; c++) {
            board[i][c] = -1;
        }
    }

    solve(0, 0, 0);
}

}

これは以下を返します:

 0 15 20  9 24

 19 10 23 14 21

 16  1 18  5  8

 11  6  3 22 13
于 2010-05-15T12:05:10.277 に答える
1

うーん、それで私はそれを試してみて、何が起こっているのかを理解しようとしました. ここに私が集めることができたものがあります。

  1. sprung_xそれらは騎士の動きを表しているため、一緒にsprung_y移動することになっています。これらの配列を移動するための独立したインデックスとしてandがありますが、実際には 1 つの変数である必要があります。私は内側のループをたたき、私が見たどこでも使用しました.ciforic
  2. メソッドの最後で、SucheWeg呼び出したセルを -1 にリセットしています。これにより、無限ループが発生しました。その行を削除すると、セル 1、2 で 19 回の移動で正常に完了することができました。Knight's Tour の定義によると、それは (0, 0) で開始したセルから 1 回の攻撃移動であり、完全なツアーを表します。
  3. ウィキペディアfsizeによると、あなたの 5 は完了しない可能性があります。テストには代わりに 6 を使用しました。
  4. 最後まで到達したときに何が起こるかを説明する必要があります。コードでは、最後のステップで出力がありますが、メソッドSucheWegは引き続き実行され、正常に終了する方法が必要です。行き止まりに達した場合は、決定の展開を許可する必要があります (-1 リセットは #2 からのものだと思います)。**メソッドから戻るときは、手順を元に戻す前に、ボードがいっぱいになっていないことを確認する必要があります。それがいっぱいなら、あなたは終わりに達しました。

私が使用したコードを表示するだけです：

static boolean isFull(int b [][])
{
   for(int i = 0; i < b.length; i++)
   {
      for(int k = 0; k < b[i].length; k++)
      {
         if(b[i][k] == -1) return false;
      }
   }
   return true;
}

static void SucheWeg(int schrittnummer, int x, int y)
{
   board[x][y] = schrittnummer;
   if(schrittnummer == ((fsize * fsize) - 1)) return;

   for(int i = 0; i < 8; i++)
   {
      int nextX = x + sprung_x[i];
      int nextY = y + sprung_y[i];

      // if we can visit the square, visit it
      if(nextX >= 0 && nextX < fsize && nextY >= 0 && nextY < fsize)
      {
         if(board[nextX][nextY] == -1)
         {
            SucheWeg(schrittnummer + 1, nextX, nextY);
         }
      }
   }
   if(isFull(board)) return;  // this is how we avoid resetting to -1
   board[x][y] = -1;          // reset if you get this far, so you can try other routes
}

次に、main私たちのためにそれを印刷しました：

for(int i = 0; i < fsize; i++)
{
   for(int c = 0; c < fsize; c++) System.out.format("%02d ", board[i][c]);
   System.out.println("");
}

出力は次のとおりです。

00 33 28 17 30 35 
27 18 31 34 21 16 
32 01 20 29 10 05 
19 26 11 06 15 22 
02 07 24 13 04 09 
25 12 03 08 23 14

最後にもう 1 つ言いたいことがあります。このアルゴリズムをうまく実装すれば、無限ループをキャッチできます。これが実際に宿題である場合は、無限ループを心配することなく、任意のサイズのボードで実行できるようになるまで修正する必要があります。現在、解決策がない場合、永久に実行される可能性があります。

于 2010-05-15T11:44:02.387 に答える
0

ちょっと宿題みたいなので、ヒントから始めます。

move_xとmove_yは、ナイトによって可能な x, y の動きです。ただし、これらは個別に索引付けできます (iおよびc)。あなたはそれを再考したいと思うかもしれません。

于 2010-05-15T11:45:54.810 に答える