为何采用回溯法的拉丁方阵全解程序仅返回一个解？

嘿，我看到你用回溯法求解拉丁方阵时遇到了只输出第一个解、没有触发完整回溯的问题，而且你之前用类似思路搞定了N皇后，那咱们来一步步拆解问题所在~

核心问题分析 #

只找到第一个解的最常见原因是回溯逻辑中断：要么找到一个解后直接终止了递归，要么在递归过程中没有正确执行「撤销选择」的回溯步骤，导致程序无法探索其他可能的分支。

先看你提供的isSafe校验函数：

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; 
}

这个函数的逻辑是对的——检查当前位置的行和列是否有重复值，但可以做些效率优化（比如只检查已填充的部分，而非全量遍历），不过它不是导致不回溯的直接原因。

回溯主逻辑的修正 #

问题大概率出在你的回溯主函数里。如果你的主函数是类似N皇后找单个解的写法（找到解后直接return true），那程序会在第一个解出现后立即终止，不会继续回溯探索其他解。

要找到所有解，你需要调整主函数的逻辑：

1. 用void类型的函数，避免用布尔值中断递归
2. 找到解后仅记录/打印，不终止递归
3. 确保每个位置尝试完所有合法数字后，执行「撤销选择」的回溯操作

以下是修正后的完整示例代码：

主回溯函数

public static void solveLatinSquare(int[][] board, int row, int col) {
    int n = board.length;
    
    // 终止条件：所有行填充完成，找到一个解
    if (row == n) {
        printBoard(board); // 打印或记录当前解
        return; // 仅结束当前分支，回到上一层继续回溯
    }
    
    // 当前列遍历完毕，跳到下一行的第一列
    if (col == n) {
        solveLatinSquare(board, row + 1, 0);
        return;
    }
    
    // 尝试1到n的每个数字
    for (int num = 1; num <= n; num++) {
        board[row][col] = num; // 做出选择
        if (isSafe(board, row, col)) {
            // 递归填充下一列
            solveLatinSquare(board, row, col + 1);
        }
        board[row][col] = 0; // 回溯：撤销选择，恢复初始状态
    }
}

优化后的isSafe函数（可选，提升效率）

原函数会遍历全量行和列，其实只需要检查已填充的部分即可：

public static boolean isSafe(int[][] board, int row, int col) {
    int num = board[row][col];
    
    // 检查当前列的已填充行（上方行）
    for (int i = 0; i < row; i++) {
        if (board[i][col] == num) {
            return false;
        }
    }
    
    // 检查当前行的已填充列（左侧列）
    for (int i = 0; i < col; i++) {
        if (board[row][i] == num) {
            return false;
        }
    }
    
    return true;
}

辅助打印函数

public static void printBoard(int[][] board) {
    int n = board.length;
    for (int[] row : board) {
        for (int num : row) {
            System.out.print(num + " ");
        }
        System.out.println();
    }
    System.out.println("-----");
}

关键注意点 #

• 不要在找到解后用return true终止递归，否则程序会直接退出，无法探索其他分支
• 必须在递归调用后执行「撤销选择」的操作（比如把当前位置重置为0），这样才能回到上一层尝试其他数字
• 确保初始棋盘的未填充位置用一个不会与1~n重复的值（比如0）初始化

内容的提问来源于stack exchange，提问作者Bartek Przydatek