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 
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 个字段的改进。由于其他未访问的字段不能按顺序访问，因此无法以相同的方式进一步改进。

于 2012-05-15T12:57:43.493 回答
1

一个非常适合骑士旅行（甚至在纸上）的旧启发式总是跳到最受限制的方格，这是骑士移动最少的地方。

如果有多个具有相同限制的方格，则随机选择其中一个。

已经证明，理论上你可以通过这条规则进入死胡同，但通常（我认为超过 99%）它可以完成 64 次巡回赛。

于 2012-05-15T13:03:54.897 回答
0

您创建一个方法，该方法返回骑士所在的给定当前单元格的可能单元格列表，然后按照每个单元格作为候选者的元素数量对它们进行排序，在ascending order.
递归调用将首先尝试具有 alower number个候选者的那些单元格，并更快地找到解决方案。但是，对于全套解决方案，您仍然需要探索整个搜索区域。

于 2012-12-15T10:10:37.103 回答