java 递归 - 需要帮助解决回溯骑士之旅

Question

我正在研究骑士之旅问题。在我的程序中，用户可以选择等于 3 或更大的数字 n。该数字将确定二维数组中 n*n 的表大小。然后，只要起点大于或等于0，小骑士就会根据用户给出的起点开始旅行。

当骑士走到死胡同时(截至输出中可视化表中的第 12 回合)，我的问题就出现了。我想以某种方式跟踪它的运动，这样我就可以堵住死胡同，后退一步并从那里尝试。我发现我可能需要一个三维数组，以便我可以保存每个方 block 中的所有转弯数字。但话又说回来，我需要一个不是静态的 ArrayList。任何建议将不胜感激。这是我的代码:

    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.  Turn: " + turns);
                if (takeTour(x-2, y+1))
                {
                    return true;
                }
                else
                {
                    return false;
                }
            }
            // 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.    Turn: " + turns);
                if (takeTour(x-2, y-1))
                {
                    return true;
                }
                else
                {
                    return false;
                }
            }
            // 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.    Turn: " + turns);
                if (takeTour(x-1, y-2))
                {
                    return true;
                }
                else
                {
                    return false;
                }
            }
            // 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.   Turn: " + turns);
                if (takeTour(x+1, y-2))
                {
                    return true;
                }
                else
                {
                    return false;
                }
            }
            // 2 Right, 1 Up
            if (x < squares -2 && y > 0 && table[x+2][y-1] == 0)
            {
                moves.add("X: " + x + ", Y: " + y + ". Moving 2 Right, 1 Up.   Turn: " + turns);
                if (takeTour(x+2, y-1))
                {
                    return true;
                }
                else
                {
                    return false;
                }
            }
            // 2 Right, 1 Down
            if (x < squares -2 && y < squares -1 && table[x+2][y+1] == 0)
            {
                moves.add("X: " + x + ", Y: " + y + ". Moving 2 Right, 1 Down. Turn: " + turns);
                if (takeTour(x+2, y+1))
                {
                    return true;
                }
                else
                {
                    return false;
                }
            }
            // 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. Turn: " + turns);
                if (takeTour(x+1, y+2))
                {
                    return true;
                }
                else
                {
                    return false;
                }
            }
            // 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.  Turn: " + turns);
                if (takeTour(x-1, y+2))
                {
                    return true;
                }
                else
                {
                    return false;
                }
            }
/*
            I need some code here before it gives up searching
*/  
            // If we'd tried every single paths
            // and we still end up here, there's no solution
            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 < 3 )
                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();
            }
        }
    }

我的 4*4 表格输出如下所示:

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. Moving 2 Right, 1 Down. Turn: 1
X: 2, Y: 1. Moving 2 Left, 1 Down.  Turn: 2
X: 0, Y: 2. Moving 2 Up, 1 Right.   Turn: 3
X: 1, Y: 0. Moving 2 Right, 1 Down. Turn: 4
X: 3, Y: 1. Moving 2 Left, 1 Down.  Turn: 5
X: 1, Y: 2. Moving 2 Up, 1 Right.   Turn: 6
X: 2, Y: 0. Moving 2 Left, 1 Down.  Turn: 7
X: 0, Y: 1. Moving 2 Right, 1 Down. Turn: 8
X: 2, Y: 2. Moving 2 Left, 1 Down.  Turn: 9
X: 0, Y: 3. Moving 2 Up, 1 Right.   Turn: 10
X: 1, Y: 1. Moving 2 Right, 1 Up.   Turn: 11
Did not find any way to complete Knights Tour!
   1   4   7  12
   8  11   2   5
   3   6   9   0
  10   0   0   0

Answer 1

当在 BackTracking 上尝试不同的可能性时，您需要在每个递归步骤中检查所有可能性。在您一步提供的代码中，您仅尝试一种可能性，然后返回。这样做您无法探索所有可能性。

我的建议是更改函数参数以接受当前位置 (x,y) 和先前访问过的位置的 boolean 数组。如果你需要构建最终有效解决方案的路径，我还建议添加步数(你已经完成的步数)和一个 int 数组来存储哪一步访问了哪个位置。

接下来我提供一个不是最有效的解决方案。事实上，您可以尝试修剪回溯的可能性，以避免递归爆炸(CPU 效率)，并且可以尝试避免某些矩阵副本(内存效率)。

package knightsTour;

import java.util.Scanner;


public class KnightsTour {

private static final int[] MOVE_X = new int[] { -2, -2, -1, -1, +1, +1, +2, +2 };
private static final int[] MOVE_Y = new int[] { +1, -1, +2, -2, +2, -2, +1, -1 };

private final int SQUARES;
private final int INIT_X;
private final int INIT_Y;

private int[][] path;


public KnightsTour(int squares, int x, int y) {
    this.SQUARES = squares;
    this.INIT_X = x;
    this.INIT_Y = y;
}

public int[][] getPath() {
    return this.path;
}

public boolean takeTour() {
    boolean[][] visited = new boolean[this.SQUARES][this.SQUARES];
    for (int i = 0; i < this.SQUARES; ++i) {
        for (int j = 0; j < this.SQUARES; ++j) {
            visited[i][j] = false;
        }
    }
    visited[this.INIT_X][this.INIT_Y] = true;

    this.path = new int[this.SQUARES][this.SQUARES];

    return takeTourBT(this.INIT_X, this.INIT_Y, 0, visited, this.path);
}

private boolean takeTourBT(int posX, int posY, int step, boolean[][] visited, int[][] path) {
    debug(step, visited);

    if (checkIfFinished(visited)) {
        return true;
    }

    // Increase the step count
    ++step;

    // Try recursively (cut when a branch success)
    boolean success = false;
    for (int i = 0; i < MOVE_X.length && !success; ++i) {
        int nextX = posX + MOVE_X[i];
        int nextY = posY + MOVE_Y[i];
        if (nextX >= 0 && nextX < this.SQUARES && nextY >= 0 && nextY < this.SQUARES && !visited[nextX][nextY]) {
            // Next position is valid and has not been visited
            // Mark position
            visited[nextX][nextY] = true;
            // Call
            boolean branchSuccess = takeTourBT(nextX, nextY, step, visited, path);
            if (branchSuccess) {
                // We are comming back from the good solution, mark the path
                path[nextX][nextY] = step;
            }
            success = success | branchSuccess;
            // Unmark the position for next try
            visited[nextX][nextY] = false;
        }
    }

    return success;
}

// Adds some verbose for debugging
private void debug(int step, boolean[][] visited) {
    System.out.println("*********************** STEP " + String.valueOf(step) + " ***********************");
    for (int i = 0; i < this.SQUARES; ++i) {
        for (int j = 0; j < this.SQUARES; ++j) {
            if (visited[i][j]) {
                System.out.print("X ");
            } else {
                System.out.print(". ");
            }
        }
        System.out.println("");
    }
    System.out.println("*******************************************************");
}

// Checks if all squares is used
private boolean checkIfFinished(boolean[][] visited) {
    for (int i = 0; i < this.SQUARES; ++i) {
        for (int j = 0; j < this.SQUARES; ++j) {
            if (!visited[i][j]) {
                return false;
            }
        }
    }

    return true;
}

public static void main(String[] args) {
    // Process arguments
    int squares = 0;
    int x = 0;
    int y = 0;
    try (Scanner sc = new Scanner(System.in)) {
        System.out.print("Number of squares: ");
        squares = Integer.parseInt(sc.nextLine());
        if (squares < 3) {
            throw new Exception("[ERROR] Invalid number of squares");
        }

        System.out.println("Note: Start values is from 0 -> n-1" + "\n0,0 is at top left side");
        System.out.print("X start value: ");
        x = Integer.parseInt(sc.nextLine());
        if (x < 0 || x > squares - 1) {
            throw new Exception("[ERROR] Invalid start x position");
        }

        System.out.print("Y start value: ");
        y = Integer.parseInt(sc.nextLine());
        if (y < 0 || y > squares - 1) {
            throw new Exception("[ERROR] Invalid start y position");
        }
    } catch (Exception e) {
        // Error occurred, exit
        System.err.println("Killing process");
        System.exit(1);
    }

    // Initialize the KnightsTour
    KnightsTour kt = new KnightsTour(squares, x, y);

    // Make the tour
    boolean success = kt.takeTour();

    // Post process
    if (success) {
        System.out.println("The tour was sucessfull!");
    } else {
        System.out.println("Did not find any way to complete Knights Tour!");
    }

    int[][] path = kt.getPath();
    for (int i = 0; i < path.length; ++i) {
        for (int j = 0; j < path[i].length; ++j) {
            String stepSTR = (path[i][j] < 10) ? "0" + String.valueOf(path[i][j]) : String.valueOf(path[i][j]);
            System.out.print(stepSTR + " ");
        }
        System.out.println("");
    }
}

}

尝试使用大小为 5 和起始位置 (0,0) 的代码。

请注意:

• 您可以通过注释调试调用来启用/禁用调试迭代
• 我用 2 个数组压缩了执行移动的方式，以避免重复，但为了清楚起见，您可以再次展开它。
• 在每个递归步骤中，在深入之前，我们检查是否可以执行移动，标记下一个位置并继续。在返回的路上，我们取消标记位置，检查移动是否到达成功的步骤，并在需要时重建好的解决方案。