java - 递归 Java 编程，Knight's Tour 让我抓狂

Question

我一直在做一个学校项目，但无法解决这个问题。出现死胡同时，骑士会跳回到最后一步的问题。

我已经添加了 4x4 测试的输出，您可以清楚地看到，当骑士看到 12 号有一条死路时，它会跳回到 11 号回合。然后它从 11 号回合继续并“解决”巡演”。

此外，如果模式不能解决问题，我不确定如何继续。因为那时我需要以某种方式记录该模式，这样我就不会再次陷入相同的模式。抱歉我的英语不好，提前谢谢。

        package knightsTour;

    import java.util.Scanner;
    import java.util.ArrayList;

    public class KnightsTour
    {
        private static int turns = 0;
        private static ArrayList<String> moves = new ArrayList<String>();

        private static int squares;
        private static int table[][];

        private static boolean takeTour(int x, int y) {
            // Checks if all squares is used. If true, algorithm will stop
            if (checkIfFinished())
                return true;
            table[x][y] = ++turns;
            // 2 Left, 1 Down
            if (x > 1 && y < squares -1 && table[x-2][y+1] == 0)
            {
                moves.add("X: " + x + ", Y: " + y + ". Moving 2 Left, 1 Down");
                if (takeTour(x-2, y+1))
                {
                    return true;
                }
            }
            // 2 Left, 1 Up
            if (x > 1 && y > 0 && table[x-2][y-1] == 0)
            {
                moves.add("X: " + x + ", Y: " + y + ". Moving 2 Left, 1 Up");
                if (takeTour(x-2, y-1))
                {
                    return true;
                }
            }
            // 2 Up, 1 Left
            if (y > 1 && x > 0 && table[x-1][y-2] == 0)
            {
                moves.add("X: " + x + ", Y: " + y + ". Moving 2 Up, 1 Left");
                if (takeTour(x-1, y-2))
                {
                    return true;
                }
            }
            // 2 Up, 1 Right
            if (y > 1 && x < squares -1 && table[x+1][y-2] == 0)
            {
                moves.add("X: " + x + ", Y: " + y + ". Moving 2 Up, 1 Right");
                if (takeTour(x+1, y-2))
                {
                    return true;
                }
            }
            // 2 Right, 1 Up
            if (x < squares -2 && y > 0 && table[x+2][y-1] == 0)
            {
                System.out.println("x:" + x + ", y:" + y + " (2r,1u)moving to x:" + (x+2) + ", y:" + (y-1));
                moves.add("X: " + x + ", Y: " + y + ". Moving 2 Right, 1 Up");
                if (takeTour(x+2, y-1))
                {
                    return true;
                }
            }
            // 2 Right, 1 Down
            if (x < squares -2 && y < squares -1 && table[x+2][y+1] == 0)
            {
                System.out.println("x:" + x + ", y:" + y + " (2r,1d)moving to x:" + (x+2) + ", y:" + (y+1));
                moves.add("X: " + x + ", Y: " + y + ". Moving 2 Right, 1 Down");
                if (takeTour(x+2, y+1))
                {
                    return true;
                }
            }
            // 2 Down, 1 Right
            if (y < squares -2 && x < squares-1 && table[x+1][y+2] == 0)
            {
                moves.add("X: " + x + ", Y: " + y + ". Moving 2 Down, 1 Right");
                if (takeTour(x+1, y+2))
                {
                    return true;
                }
            }
            // 2 Down, 1 Left
            if (y < squares -2 && x > 0 && table[x-1][y+2] == 0)
            {
                moves.add("X: " + x + ", Y: " + y + ". Moving 2 Down, 1 Left");
                if (takeTour(x-1, y+2))
                {
                    return true;
                }
            }
            return false;
        }

        // Checks if all squares is used
        private static boolean checkIfFinished()
        {
            for (int i = 0; i < squares; i++)
            {
                for (int j = 0; j < squares; j++)
                {
                    if (table[i][j] == 0)
                        return false;
                }
            }
            return true;
        }

        // Made this to save code from 3 duplicates
        private static void invalidNumber()
        {
            System.out.println("Invalid number! Killing proccess");
            System.exit(0);
        }

        public static void main(String[] args) {

            Scanner sc = new Scanner(System.in);
            System.out.print("Number of squares: ");
            squares = Integer.parseInt(sc.nextLine());
            if (squares < 1 )
                invalidNumber();

            System.out.println("Note: Start values is from 0 -> n-1"
                            + "\n0,0 is at top left side");
            System.out.print("X start value: ");
            int x = Integer.parseInt(sc.nextLine());
            if (x < 0 || x > squares -1)
                invalidNumber();

            System.out.print("Y start value: ");
            int y = Integer.parseInt(sc.nextLine());
            if (y < 0 || y > squares -1)
                invalidNumber();
            sc.close();

            table = new int[squares][squares];

            boolean tourComplete = takeTour(x, y);

            for (String s : moves)
            {
                System.out.println(s);
            }
            if (!tourComplete)
                System.out.println("Did not find any way to complete Knights Tour!");

            // Print the table with the move-numbers
            for (int i = 0; i < squares; i++)
            {
                for (int j = 0; j < squares; j++)
                {
                    System.out.printf("%4d", table[j][i]);
                }
                System.out.println();
            }
        }
    }

这是 4x4 的输出:

Number of squares: 4
Note: Start values is from 0 -> n-1
0,0 is at top left side
X start value: 0
Y start value: 0
x:0, y:0 (2r,1d)moving to x:2, y:1
x:1, y:0 (2r,1d)moving to x:3, y:1
x:0, y:1 (2r,1d)moving to x:2, y:2
x:1, y:1 (2r,1u)moving to x:3, y:0
x:1, y:1 (2r,1d)moving to x:3, y:2
x:1, y:2 (2r,1d)moving to x:3, y:3
X: 0, Y: 0. Moving 2 Right, 1 Down
X: 2, Y: 1. Moving 2 Left, 1 Down
X: 0, Y: 2. Moving 2 Up, 1 Right
X: 1, Y: 0. Moving 2 Right, 1 Down
X: 3, Y: 1. Moving 2 Left, 1 Down
X: 1, Y: 2. Moving 2 Up, 1 Right
X: 2, Y: 0. Moving 2 Left, 1 Down
X: 0, Y: 1. Moving 2 Right, 1 Down
X: 2, Y: 2. Moving 2 Left, 1 Down
X: 0, Y: 3. Moving 2 Up, 1 Right
X: 1, Y: 1. Moving 2 Right, 1 Up
X: 1, Y: 1. Moving 2 Right, 1 Down
X: 3, Y: 2. Moving 2 Left, 1 Down
X: 1, Y: 1. Moving 2 Down, 1 Right
X: 1, Y: 2. Moving 2 Right, 1 Down
Did not find any way to complete Knights Tour!
   1   4   7  12
   8  11   2   5
   3   6   9  13
  10  14  15  16

Answer 1

你最好的选择是添加 List<Point> visited到你的递归调用的方法。我也会改变你的 int x和int y参数 Point 。这样你就可以直接调用 visited.contains(point)以确定您是否已经对此进行了测试 Point 。在这种情况下，您不会使用特定的 Point 进行递归调用。然后继续下一个。