1

Javaでバックトラックと再帰を使用して4x4ボードでナイツツアーの問題を解決しようとしていますが、出力で次のステップシーケンスが得られます。

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

右上隅では、14、15、16 が互いに隣り合っていますが、これは不可能です。これは、騎士がチェス盤上を L 字型に移動するためです。誰かがこれを解決するのを手伝ってくれたらありがたいです。

コード：

public class KnightsTour {

private static int board[][] = new int[4][4];
private static int stepCounter = 1;

public Test() {
    initBoard(board);
    tour(0,0);
    printSol(board);

}

  public static void printSol(int[][] a) {
    for (int i = 0; i < a.length; i++) {
        for (int j = 0; j < a[i].length; j++) {
            if(a[i][j]>9){
                System.out.print(a[i][j] + "  ");
            }else{
                System.out.print(a[i][j] + "   ");
            }
        }
        System.out.println();
    }
    System.out.println();
}


public static void initBoard(int[][] a) {
    for (int i = 0; i < a.length; i++) {
        for (int j = 0; j < a[i].length; j++) {
            a[i][j] = -1;
        }
    }
}


public void tour(int x, int y) {


    if (((x < 0) || (x >= 4) || (y < 0) || (y >= 4)) || (board[x][y] != -1)) {
        return;
    }else{
        board[x][y] = stepCounter++;
        tour(x+2, y+1);
        tour(x+1, y-2);
        tour(x+1, y+2);
        tour(x-1, y+2);
        tour(x-2, y-1);
        tour(x-2, y+1);
        tour(x-1, y-2);
        tour(x+2, y-1);  
    }
}




public static void main(String[] args){
    new KnightsTour();
}
}
4

2 に答える 2

1

  • 関数がブール値を返すようにして、呼び出し元の関数が成功したかどうかを判断できるようにする必要があります。それ以外の場合は、解決策が見つかった後でも、考えられるすべての組み合わせを試すまで続行します。

    次に、関数を呼び出すたびに戻り値を確認し、成功した場合は true を返す必要があります。

    次に、完了したら明らかに true を返す必要もあります。

    私は次のようなものを提案します：

    if (stepCounter == 1 + board.length * board[0].length)
  return true;

    直後board[x][y] = stepCounter++;。

  • 関数呼び出しの最後に加えられた変更を元に戻す必要があります。つまりstepCounter、減らすboard[x][y]必要があり、に設定する必要があります-1。

これらの変更を正常に行った後-1、4x4 ボードでは不可能なため、実際にはすべての結果が表示されるはずですが、8x8 への変更は成功するはずです。

上記では使用していないことに注意してください。17ハードコードされた値 (たとえば、x >= 4) を使用しないことをお勧めします。final代わりに、配列のサイズまたは値のいずれかを使用してください。

于 2013-12-23T20:26:08.087 に答える
0

tour() 関数は、最初にアクセスした順序のステップ カウンターに正方形の値を設定するように見えます。しかし、あなたは複数のオプションを試しています。最初のツアーは、12 に到達した時点で行き止まりになります。その後の試みの 1 つが、13 ～ 16 の各マスに接触します。

訪問した順序ではなく、現在のツアーの状態を保存する必要があります。たとえば、バックトラックすると、現在の広場はツアーの一部ではなくなります。ツアーを見つけたら、やめるべきです。

于 2013-12-23T20:22:35.007 に答える