java - 骑士巡回赛不会超过第四步

Question

我正在编写一个骑士巡回赛问题的解决方案，使用启发式方法来评估潜在的 Action ，并选择“最困难”的一个。我遇到一个问题，它完成了第四步，然后不会向前或向后移动到不同的 Action 。它到达的最远距离是:

1 -1 -1 -1 -1 
-1 -1 -1 -1 -1 
-1 2 -1 -1 -1 
-1 -1 -1 -1 4 
-1 -1 3 -1 -1

我现在正在开发 5 x 5 开发板，然后最终升级到 8 x 8。我只是想先看看它在小范围内发挥作用。我知道有一些有效的举动，我只是不确定是否是启发式比较出了问题，或者是否完全是我没有看到的其他东西。

package csne2;

import java.util.Scanner;

public class KnightsTour 
{
    private final static int BOARD_LENGTH = 5;      //The length of the board
    private final static int MAX_MOVES = BOARD_LENGTH * BOARD_LENGTH;
    private static int board[][];                   //The simulated board
    private static int[][] hueristic = new int[][]
    {
        {2, 3, 4, 3, 2},
        {3, 4, 6, 4, 3},
        {4, 6, 8, 6, 4},
        {3, 4, 6, 4, 3},
        {2, 3, 4, 3, 2}
    };
    //List of possible moves for the knight
    private final static int xMove[] = { 2, 1, -1, -2, -2, -1, 1, 2 };
    private final static int yMove[] = { 1, 2, 2, 1, -1, -2, -2, -1 };

    public static void main(String[] args) 
    {
       Scanner in = new Scanner(System.in);
       System.out.printf("Enter starting row (0-7): ");
       int row = in.nextInt();
       System.out.printf("Enter starting column (0-7): ");
       int col = in.nextInt();
       solveTour(row, col);
       in.close();
    }
    /**
     * Helper method to determine if a square is safe for the knight
     *
     * @param row the row the knight is on
     * @param col the column the knight is on
     * @return true if the square is safe for the knight
     */
     private static boolean isSafe(int row, int col)
     {
        return ((row >= 0 && row < BOARD_LENGTH)
               && (col >= 0 && col < BOARD_LENGTH)
               && (board[row][col] == -1));
     }

     /**
      * Helper method to print the tour solution to the console
      */
     private static void printTour() 
     {
         for (int r = 0; r < BOARD_LENGTH; r++) 
         {
             for (int c = 0; c < BOARD_LENGTH; c++)
             {
                 System.out.print(board[r][c] + " ");
             }
             System.out.printf("\n");
        }
     }

     /**
      * Solves the knight's tour using backtracking
      *
      * @param sRow the starting row
      * @param sCol the starting column
      */
     public static void solveTour(int sRow, int sCol) 
     {
         initializeBoard();

         board[sRow][sCol] = 1;
         if (solveTour(sRow, sCol, 2))
         {
             printTour();
         } 
         else 
         {
             System.out.printf("No Solution!%n");
             printTour();
         }
     }
     private static void initializeBoard()
     {
         board = new int[BOARD_LENGTH][BOARD_LENGTH];
         //Make all of board -1 because have not visited any square
         for (int r = 0; r < BOARD_LENGTH; r++) 
         {
             for (int c = 0; c < BOARD_LENGTH; c++)
             {
                 board[r][c] = -1;
             }
         }      
     }

     /**
      * Helper method that solve the tour
      *
      * @param row the current row
      * @param col the current column
      * @param kthMove the current move
      * @return true if there is a solution to the knight's tour
      */
     private static boolean solveTour(int row, int col, int kthMove) 
     {
        //Base case
        int nextRow = row;
        int nextCol = col;
        if(kthMove > MAX_MOVES)
        {
            return true;
        }

        int[] possXMoves = new int[5];
        int[] possYMoves = new int[5];
        int nextMove = 7;
        for(int i = 0; i < MAX_MOVES; i++)
        {
            for (int j = 0; j < xMove.length; j++)
            {
                if(isSafe(row + xMove[j], col + yMove[j]))
                {
                    possXMoves[j] = row + xMove[j];
                    possYMoves[j] = col + yMove[j];
                }
                else
                {
                    possXMoves[j] = row;
                    possYMoves[j] = col;
                }
            }
            for(int k = 0; k < 8; k++)
            {
                if(nextMove > hueristic[possXMoves[j]][possYMoves[j]])
                {
                    if(isSafe(possXMoves[j], possYMoves[j]))
                    {       
                        nextMove = hueristic[possXMoves[j]][possYMoves[j]];
                        nextRow = possXMoves[j];
                        nextCol = possYMoves[j];


                    }
                }
            }
            hueristic[nextRow][nextCol] = 7;
            if(isSafe(nextRow, nextCol)) 
            {
                board[nextRow][nextCol] = kthMove;

                if (solveTour(nextRow, nextCol, kthMove + 1 ))
                {
                    return true;
                } 
                else 
                {
                    board[nextRow][nextCol] = -1;
                    heuristic[nextRow][nextCol] = nextMove;


                }
            }
        }  
        return false;
        }
    }

编辑:最终工作代码

package csne2;

import java.util.Scanner;

public class KnightsTour 
{
    private final static int BOARD_LENGTH = 5;      //The length of the board
    private final static int MAX_MOVES = BOARD_LENGTH * BOARD_LENGTH;
    private static int board[][];                   //The simulated board
    private static int[][] hueristic = new int[][]
    {
        {2, 3, 4, 3, 2},
        {3, 4, 6, 4, 3},
        {4, 6, 8, 6, 4},
        {3, 4, 6, 4, 3},
        {2, 3, 4, 3, 2}
    };
    private static int highestHeuristicNumPlusOne = 9;
    //List of possible moves for the knight
    private final static int xMove[] = { 2, 1, -1, -2, -2, -1, 1, 2 };
    private final static int yMove[] = { 1, 2, 2, 1, -1, -2, -2, -1 };

    public static void main(String[] args) 
    {
       Scanner in = new Scanner(System.in);
       System.out.printf("Enter starting row (0-7): ");
       int row = in.nextInt();
       System.out.printf("Enter starting column (0-7): ");
       int col = in.nextInt();
       solveTour(row, col);
       in.close();
    }
    /**
     * Helper method to determine if a square is safe for the knight
     *
     * @param row the row the knight is on
     * @param col the column the knight is on
     * @return true if the square is safe for the knight
     */
     private static boolean isSafe(int row, int col)
     {
        return ((row >= 0 && row < BOARD_LENGTH)
               && (col >= 0 && col < BOARD_LENGTH)
               && (board[row][col] == -1));
     }

     /**
      * Helper method to print the tour solution to the console
      */
     private static void printTour() 
     {
         for (int r = 0; r < BOARD_LENGTH; r++) 
         {
             for (int c = 0; c < BOARD_LENGTH; c++)
             {
                 System.out.print(board[r][c] + " ");
             }
             System.out.printf("\n");
        }
     }

     /**
      * Solves the knight's tour using backtracking
      *
      * @param sRow the starting row
      * @param sCol the starting column
      */
     public static void solveTour(int sRow, int sCol) 
     {
         initializeBoard();

         board[sRow][sCol] = 1;
         if (solveTour(sRow, sCol, 2))
         {
             printTour();
         } 
         else 
         {
             System.out.printf("No Solution!%n");
             printTour();
         }
     }
     private static void initializeBoard()
     {
         board = new int[BOARD_LENGTH][BOARD_LENGTH];
         //Make all of board -1 because have not visited any square
         for (int r = 0; r < BOARD_LENGTH; r++) 
         {
             for (int c = 0; c < BOARD_LENGTH; c++)
             {
                 board[r][c] = -1;
             }
         }      
     }

     /**
      * Helper method that solve the tour
      *
      * @param row the current row
      * @param col the current column
      * @param kthMove the current move
      * @return true if there is a solution to the knight's tour
      */
     private static boolean solveTour(int row, int col, int kthMove) 
     {
        //Base case
        int nextRow = row;
        int nextCol = col;
        if(kthMove > MAX_MOVES)
        {
            return true;
        }

        int[] possXMoves = new int[xMove.length];
        int[] possYMoves = new int[yMove.length];
        int nextMove = highestHeuristicNumPlusOne;
        for(int i = 0; i < MAX_MOVES; i++)
        {
            for (int j = 0; j < xMove.length; j++)
            {
                if(isSafe(row + xMove[j], col + yMove[j]))
                {
                    possXMoves[j] = row + xMove[j];
                    possYMoves[j] = col + yMove[j];
                }
                else
                {
                    possXMoves[j] = row;
                    possYMoves[j] = col;
                }
                if(nextMove > hueristic[possXMoves[j]][possYMoves[j]])
                {
                    if(isSafe(possXMoves[j], possYMoves[j]))
                    {       
                        nextMove = hueristic[possXMoves[j]][possYMoves[j]];
                        nextRow = possXMoves[j];
                        nextCol = possYMoves[j];


                    }
                }
            }

            if(isSafe(nextRow, nextCol)) 
            {
                board[nextRow][nextCol] = kthMove;

                if (solveTour(nextRow, nextCol, kthMove + 1 ))
                {
                    return true;
                } 
                else 
                {
                    board[nextRow][nextCol] = -1;


                }
            }
        }  
        return false;
        }
    }

感谢所有帮助，我会尽力澄清向我提出的任何问题。

Answer 1

solveTour方法存在很多问题

1. 魔数(Magic Number)。 5？ 7？为这些常量指定有意义的名称。 (提示:这些数字都是错误的)
2. 为什么在搜索时修改启发式表？
3. 为循环变量指定比 i j 和 k 更好的名称，并重新思考它们的作用。这些循环之一根本不应该存在。