如何避免访问二维数组中的无效位置？

Question

我正在研究 Knight's Tour 问题，并且正在为其制定递归解决方案。 https://www.chess.com/terms/knights-tour-chess#:~:text=The%20knight's%20tour%20is%20a,same%20square%20more%20than%20once.

我有一个矩阵[8][8] 和一个名为knightMove(int currentRow, int currentColumn); 的方法。此方法应将马从当前位置可以进行的所有可能移动添加到数组中。如果可能移动的位置值等于0，那么knightMove(newRow, newColumn)将从新位置再次调用。

如果它发现了死胡同，那么它会在上一次调用中尝试数组中的下一个可能的移动。如果它用完了以前的数组位置，它将尝试在这个数组之前调用的数组中的下一个位置，依此类推。程序只有在找到问题的正确解决方案时才会结束。

现在我的问题来了，我想避免使用这么多 'ifs' 来检查马的移动是否超出 table。

ArrayList <int[]> moves = new ArrayList<int[]>();
int[] arr = new int[2];
int max=8;
if (currentColumn-2 > 0){
    
    if(currentRow - 1 > 0){
        arr[0] = currentColumn-2;
        arr[1] = currentRow-1;  
        moves.add(arr);
    } 
    
    if(currentRow+1 < max){
        arr[0] = currentColumn-2;
        arr[1] = currentRow+1;
        moves.add(arr);
    }
} 
if (currentRow-2 > 0){
    
    if(currentColumn-1 > 0){                
        arr[0] = currentColumn-1;  
        arr[1] = currentRow-2;
        moves.add(arr);  
    } 
    
    if(currentColumn+1 < max){
        arr[0] = currentColumn+1;
        arr[1] = currentRow-2;
        moves.add(arr);
    }
} 
if (currentColumn+2 > 0){
    
    if(currentRow-1 > 0){
        arr[0] = currentColumn+2;
        arr[1] = currentRow-1;  
        moves.add(arr);
    } 
    
    if(currentRow+1 < max){
        arr[0] = currentColumn+2;
        arr[1] = currentRow+1;
        moves.add(arr);
    }
} 
if (currentRow+2 > 0){
   
    if(currentColumn-1 > 0){
        arr[0] = currentColumn-1;  
        arr[1] = currentRow+2;
        moves.add(arr);
    } 
   
    if(currentRow+1 < max){
        arr[0] = currentColumn+2;
        arr[1] = currentRow+1;
        moves.add(arr);
    }
} 

 for (int[] c : moves){
 // recursive logic...
 }

我对无效职位不感兴趣。如果编译器不能访问这些无效位置，它就应该不对它们做任何事情，也不要破坏我的代码。专注于那些真正有效的职位。我想做类似下面的事情，只添加数组中有效位置的值（Utopic 解决方案）：

int[] temp = {
    table[currentRow-2][currentColumn-1], 
    table[currentRow-2][currentColumn+1], 
    table[currentRow+1][currentColumn-2], 
    table[currentRow-1][currentColumn-2],  
    table[currentRow+2][currentColumn-1], 
    table[currentRow+2][currentColumn+1], 
    table[currentRow-1][currentColumn+2], 
    table[currentRow+1][currentColumn+2]  
};

我需要帮助找出更好的方法来避免访问矩阵中的无效位置。

Answer 1

这是我多次测试之一的结果。

Origin row: 3, column: 4
    Move to row: 1, column: 5
    Move to row: 1, column: 3
    Move to row: 2, column: 6
    Move to row: 2, column: 2
    Move to row: 4, column: 6
    Move to row: 4, column: 2
    Move to row: 5, column: 5
    Move to row: 5, column: 3

Origin row: 1, column: 1
    Move to row: 0, column: 3
    Move to row: 2, column: 3
    Move to row: 3, column: 2
    Move to row: 3, column: 0

Origin row: 7, column: 7
    Move to row: 5, column: 8
    Move to row: 5, column: 6
    Move to row: 6, column: 5
    Move to row: 8, column: 5

Origin row: 1, column: 7
    Move to row: 0, column: 5
    Move to row: 2, column: 5
    Move to row: 3, column: 8
    Move to row: 3, column: 6

Origin row: 7, column: 1
    Move to row: 5, column: 2
    Move to row: 5, column: 0
    Move to row: 6, column: 3
    Move to row: 8, column: 3

我做的第一件事是创建一个 Coordinate class。这允许我将索引越界测试放在一个地方，在 Coordinate class.

knightMove 方法计算出多少移动是有效的，创建坐标数组，returns 有效移动坐标。

这是完整的可运行代码。

public class MoveKnight {

    public static void main(String[] args) {
        MoveKnight mk = new MoveKnight();
        displayOutput(mk, 3, 4);
        displayOutput(mk, 1, 1);
        displayOutput(mk, 7, 7);
        displayOutput(mk, 1, 7);
        displayOutput(mk, 7, 1);
    }

    private static void displayOutput(MoveKnight mk, int row, int column) {
        System.out.println("Origin row: " + row + ", column: " + column);
        Coordinate[] output = mk.knightMove(row, column);
        for (int index = 0; index < output.length; index++) {
            System.out.println("    Move to row: " + output[index].getRow() + 
                    ", column: " + output[index].getColumn());
        }
        System.out.println();
    }

    public Coordinate[] knightMove(int currentRow, int currentColumn) {
        Coordinate[] difference = { new Coordinate(-2, 1), new Coordinate(-2, -1), 
                new Coordinate(-1, 2), new Coordinate(-1, -2), new Coordinate(1, 2), 
                new Coordinate(1, -2), new Coordinate(2, 1), new Coordinate(2, -1) };

        int count = 0;
        for (int index = 0; index < difference.length; index++) {
            Coordinate destination = new Coordinate(currentRow, currentColumn);
            destination.incrementCoordinate(difference[index]);
            if (destination.isValid()) {
                count++;
            }
        }

        Coordinate[] output = new Coordinate[count];
        count = 0;
        for (int index = 0; index < difference.length; index++) {
            Coordinate destination = new Coordinate(currentRow, currentColumn);
            destination.incrementCoordinate(difference[index]);
            if (destination.isValid()) {
                output[count++] = destination;
            }
        }

        return output;
    }

    public class Coordinate {

        private int column, row;

        public Coordinate(int row, int column) {
            setRowColumn(row, column);
        }

        public int getColumn() {
            return column;
        }

        public int getRow() {
            return row;
        }

        public void incrementCoordinate(Coordinate increment) {
            this.row += increment.getRow();
            this.column += increment.getColumn();
        }

        public void setRowColumn(int row, int column) {
            this.row = row;
            this.column = column;
        }

        public boolean isValid() {
            return row >= 0 && row < 8 && column >= 0 && column < 8;
        }

    }

}

如何避免访问二维数组中的无效位置？

How to avoid accessing an invalid position in a 2d array?

java

arrays

recursion

matrix

knights-tour