java - 使用递归在 Java 中通过国际象棋骑士移动模式将数字放入二维数组中

Question

public class ChessComplete 
{
    private int size;
    private int[][] board;
    private long callNum;

    public ChessComplete(int size)//constructor with 2D array size as a parameter
    {
        this.size = size;
        board = new int [size][size];
        board[0][0] = 1;
    }
    public boolean isValid(int r, int c)//To check the if the number that is added is in the 2D array is in bound
    {
        if(r < 0 || c < 0 || r >= size || c >= size)
        {
            return false;
        }
        return true;
    }

    /*
     * Move through the 2D array by placing the consecutive number for each (row,col) until its full
     * Moves Are only allowed in a chess knight pattern
     */
    public boolean move(int r, int c, int count) {
    callNum++;

    if (!isValid(r, c)) {
        return false;
    }

    if (count == (size * size))// Base case if count reaches the end of 2D
                                // array

    {

        return true;
    }
    board[r][c] = count;// fills the positon with the current count

    if (board[r][c] == 0) {
        return false;
    }

    // Check if each possible move is valid or not
    if (board[r][c] != 0) {

        for (int i = 0; i < 8; i++) {

            int X[] = { 2, 1, -1, -2, -2, -1, 1, 2 };
            int Y[] = { 1, 2, 2, 1, -1, -2, -2, -1 };

            // Position of knight after move
            int x = r + X[i];
            int y = c + Y[i];

            if (move(x, y, count + 1)) {

                return move(x, y, count + 1);
            }

        }
    }
    board[r][c] = 0;
    return false;
}
    public long getSteps()//Number of reccursive trials
    {
        return callNum;
    }
    public void displayBoard()
    {
        String s = " ";
        for(int r = 0; r < size; r++)
        {
            for(int c = 0; c < size; c++)
            {
                System.out.print(board[r][c] + " ");
            }
            System.out.println();
        }

    }
}

输出为:

1,  0,  0,  0,  0, 

0,  0,  0,  23, 0, 

0,  2,  0,  0,  0, 

0,  0,  0,  0, 24, 

0,  0,  3,  0,  0 

Recursive method call count: 78,293,671

说明

注意，在位置(行，列)(0, 0)处有一个1，在位置(2, 1)处有一个2。正如你所看到的，棋盘上的马以类似的方式移动。这样我们就需要用连续的数字填充整个二维数组，使其严格遵循骑士模式。

问题

我不明白为什么整个二维数组没有被所有其他连续数字填充。例如，在二维数组中用 3 填充该位置后，数字会一直跳到 23。

Answer 1

在执行移动之前，您没有检查该方 block 是否未被占用，因此您的解决方案包括相互覆盖的重复移动。

更改 isValid 以检查目标方 block 是否为空:

public boolean isValid(int r, int c) {
    if (r < 0 || c < 0 || r >= size || c >= size || board[r][c] != 0) {
        return false;
    }
    return true;
}

...并删除构造函数中的初始化步骤 board[0][0] = 1;(应通过第一次调用 move 进行设置)。

此外(但不是致命的)，

if (move(x, y, count + 1)) {
    return move(x, y, count + 1);
}

应该是

if (move(x, y, count + 1)) {
    return true;
}

并且检查 if (board[r][c] == 0) 和 if (board[r][c] != 0) 不会执行任何操作，因为它们是在您设置 board[r][c] = count; 之后发生的。