使用递归 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

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

更改isValid以检查目标方块是否为空：

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; 之后。

使用递归 Java 中的国际象棋骑士移动模式将数字放置在二维数组中

Placing numbers in a 2D array by a chess knight move pattern in Java using recursion

java

arrays

chess

multidimensional-array

说明

问题