2

8X8のチェス盤では、騎士だけを考慮して、チェス盤の任意の正方形から騎士を開始する場合、目的は、正方形を繰り返さずに、最大数の正方形をカバーすることです。これまでのところ、以下のコードで最も効率的な解決策を見つけました。

60    29    34    49    0    15    46    0

35    50    1    16    45    48    11    0

30    59    28    33    2    9    14    47

51    36    31    44    17    12    3    10

58    43    52    27    32    25    8    13

37    40    55    18    23    6    21    4

42    57    38    53    26    19    24    7

39    54    41    56    0    22    5    20

1で始まる数字は、騎士がたどる道を示しています。私の質問は、このコードを修正して、64（私の場合は60に達する）の完全な答えを得ることができるかということです。

package game;
import java.io.BufferedReader;  
import java.io.IOException;
import java.io.InputStreamReader;

public class Knight {
static int board[][]=new int[8][8];
static int value=1;
public static void zero()
{
    for(int i=0;i<7;i++)
        for(int j=0;j<7;j++)
            board[i][j]=0;
}

public static void knightpos(int x,int y)throws IOException
{
    if(value==61)
    {   System.out.println();
    for(int i=0;i<8;i++)
    {
        System.out.println();
        System.out.println();
        for(int j=0;j<8;j++)
        System.out.print("    "+board[i][j]);
    }

        System.exit(0);
    }


    if(x+1<=7&&y+2<=7)
    {
        if(board[x+1][y+2]==0)
        {  board[x+1][y+2]=value++;
           knightpos(x+1,y+2);
        }
    }

    if(x+2<=7&&y+1<=7)
    {
         if(board[x+2][y+1]==0)
        {
           board[x+2][y+1]=value++;
           knightpos(x+2,y+1);
        }
    }

    if(x-2>=0&&y-1>=0)
    {
        if(board[x-2][y-1]==0)
        {board[x-2][y-1]=value++;
           knightpos(x-2,y-1);
        }
    }

    if(x+2<=7&&y-1>=0)
    {
          if(board[x+2][y-1]==0)
        {board[x+2][y-1]=value++;
           knightpos(x+2,y-1);
        }
    }

    if(x+1<=7&&y-2>=0)
    {
        if(board[x+1][y-2]==0)
        {board[x+1][y-2]=value++;
           knightpos(x+1,y-2);}
    }

    if(x-1>=0&&y-2>=0)
    {
          if(board[x-1][y-2]==0)
        {board[x-1][y-2]=value++;
           knightpos(x-1,y-2);}
    }

    if(x-2>=0&&y+1<=7)
    {
          if(board[x-2][y+1]==0)
        {board[x-2][y+1]=value++;
           knightpos(x-2,y+1);}
    }

    if(x-1>=0&&y+2<=7)
    {
          if(board[x-1][y+2]==0)
        {board[x-1][y+2]=value++;
           knightpos(x-1,y+2);}
    }
    board[x][y]=0;
    value--;
    return;
}

public static boolean chk() {

    for(int i=0;i<7;i++)
        for(int j=0;j<7;j++)
            if(board[i][j]==0)
                return false;

    return true;

}


public static void main(String args[])throws IOException
{
    InputStreamReader ir = new InputStreamReader(System.in);
    BufferedReader br = new BufferedReader(ir);
    System.out.println("Knight chess game input x,y position ");
    int x=Integer.parseInt(br.readLine());
    int y=Integer.parseInt(br.readLine());
{
    if(!chk())
            {   
                zero();
                value=1;
                knightpos(x,y);
            }

}           
}
}
4

3 に答える 3

1

騎士のツアー（紙の上でも）に非常にうまく機能する古いヒューリスティックは、常に最も制限された広場にジャンプします。これは、騎士の動きが最も少ない場所です。

同じ制限のある正方形が複数ある場合は、そのうちの1つをランダムに選択します。

理論的にはこのルールで行き止まりになることが証明されていますが、通常（99％以上だったと思います）フル64ツアーでうまくいきます。

于 2012-05-15T13:03:54.897 に答える
1 
60    29    34    49    0    15    46    0

35    50    1    16    45    48    11    0

30    59    28    33    2    9    14    47

51    36    31    44    17    12    3    10

58    43    52    27    32    25    8    13

37    40    55    18    23    6    21    4

42    57    38    53    26    19    24    7

39    54    41    56    0    22    5    20

ソリューションを見ると、ゼロに分岐できる最初のステップはステップ 3 です。追加情報として、60 から 1 に再びジャンプして、サイクルを構築できたことがわかります (ただし、できませんでした。ある場所を二度訪れることは許されていないからです。

しかし、4 から始めて 60 に移動し、そこから 1、2、3 と進み、ゼロ フィールドの 1 つを訪れることができます。

ただし、これは 1 つのフィールドの改善にすぎません。他の未訪問フィールドは順番に訪問できないため、これを同じ方法でさらに改善することはできません。

于 2012-05-15T12:57:43.493 に答える
0

騎士がいる特定の現在のセルの可能なセルのリストを返すメソッドを作成し、各セルが候補として持つ要素の数でそれらを並べ替えますascending order.
再帰呼び出しはlower number、候補の a を持つセルを最初に試行し、ソリューションにすばやく到達します。ただし、ソリューションの完全なセットについては、検索領域全体を探索する必要があります。

于 2012-12-15T10:10:37.103 に答える