java recurison - 需要帮助解决回溯 Knight's Tour

Question

我正在研究 Knight's Tour 问题。在我的程序中，用户可以 select 一个等于或大于 3 的数字 n。该数字将在二维数组中由 n*n 确定 table 的大小。然后骑士会根据用户给定的起点开始它的巡回赛，只要他们高于或等于0。

当骑士走到死胡同时，我的问题就来了（截至输出中可视化 table 的第 12 回合）。我想以某种方式跟踪它的运动，这样我就可以堵住死胡同，后退一步，然后从那里开始尝试。我发现我可能需要一个三维数组，这样我就可以保存每个方格中的所有转数。但是话又说回来，我需要一个 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 table 输出如下所示：

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 上尝试不同的可能性时，您需要在每个递归步骤中检查它们。在您一步提供的代码中，您只尝试一种可能性，然后 return。这样做你无法探索所有的可能性。

我的建议是更改函数参数以接受当前位置 (x,y) 和先前访问过的位置的布尔数组。如果你需要构建最终有效解的路径，我也建议加上步数（你完成的步数）和一个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) 尝试此代码。

注意：

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

java recurison - 需要帮助解决回溯 Knight's Tour

java recurison - Need help for solving backtracking Knight's Tour

java

recursion

knights-tour