为什么这个程序只找到一个解决方案？

Question

我想编写一个程序来找到拉丁方的所有解。我想使用回溯来做到这一点。我使用类似的方法解决了 n-queens 问题并且它有效。此代码仅找到第一个解决方案并且不会回溯。

public static boolean isSafe(int[][] board, int row, int col) {

    for(int i = 0; i < board.length; i++) {
        if(row != i) {
            if(board[i][col] == board[row][col]) return false;
        }
        if(col != i) {
            if(board[row][i] == board[row][col]) return false;
        }
    }
    return true;
}

public static void enumerate(int N) {
    int[][] board = new int[N][N];
    enumerate(board, 0, 0);
}

public static void enumerate(int[][] board, int row, int col) {
    int boardSize = board.length;
    if (col == boardSize ) {
        System.out.println();
        print(board);
        SaveToFile.saveSquare("Latin", "BT", board, boardSize);

    }
    else {
        for (int i = 1; i <= boardSize; i++) {
            board[row][col] = i; 
            if (isSafe(board, row, col)) {
                if(row+1 == boardSize) {
                    enumerate(board, 0, col+1);
                }
                else {
                    enumerate(board, row+1, col);
                }
            }
        }
    }
}

public static void print(int[][] board) {
    for(int i=0; i<board.length;i++) {
        for(int j=0; j<board.length; j++) {
            System.out.print(" "+board[i][j]+" ");
        }
        System.out.println();
    }
    System.out.println();
}

public static void main(String[] args) {

    for(int i = 2; i <=2; i++) {
        SaveToFile.createFile("Latin", "BT", i);
        enumerate(i);
    }
}

我知道我的代码看起来很糟糕，但我稍后会重构它；) 感谢您的帮助:)

Answer 1

您必须在递归调用后清除您在板上设置的值：

public static void enumerate(int[][] board, int row, int col) {
    int boardSize = board.length;
    if (col == boardSize ) {
        System.out.println();
        print(board);
        SaveToFile.saveSquare("Latin", "BT", board, boardSize);

    }
    else {
        for (int i = 1; i <= boardSize; i++) {
            board[row][col] = i;
            if (isSafe(board, row, col)) {
                if(row+1 == boardSize) {
                    enumerate(board, 0, col+1);
                }
                else {
                    enumerate(board, row+1, col);
                }
            }
            //RESET!!!
            board[row][col] = 0;
        }
    }
}

为什么这个程序只找到一个解决方案？

Why this program find only one solution?

java

recursion

backtracking

latin-square