数独求解器失效排查：无法填充空白数独，请求技术协助

我尝试实现一个数独求解器，采用逐列检查并在出错时回溯尝试下一个数字的算法，但当前求解器无法填充空白数独，多次检查重写代码仍未找到问题，需要协助排查。

原代码 #

class Solution
{
  public void solveSudoku (char[][]board)
  {
    helper (board, 0, 0);
  }
  public boolean helper (char[][]board, int row, int col)
  {
    if (row == board.length)
      return true;
//next recursion row and col
    int nrow = 0;
    int ncol = 0;

    if (col == board.length - 1)
      {
    nrow = row + 1;
    ncol = 0;
      }
    else
      {
    nrow = row;
    ncol = col + 1;
      }
//if number already exist
    if (board[row][col] != '.')
      {
    if (helper (board, nrow, ncol))
      return true;
    //else check with 1 to 9 no
    else
      {
        for (int i = 1; i <= 9; i++)
          {
        if (isSafe (board, row, col, i))
          {
            //if number safe then set the number
            board[row][col] = (char) (i + '0');
            //and go for next col
            if (helper (board, nrow, ncol))
              return true;
            //if next recursion return false then reset this to '.'
            else
              board[row][col] = '.';

          }
          }
      }
      }
    return false;
  }

  public boolean isSafe (char[][]board, int row, int col, int n)
  {
//check with col
    for (int i = 0; i < board.length; i++)
      {
    if (board[i][col] == (char) (n + '0'))
      return false;
      }
    //check row
    for (int j = 0; j < board.length; j++)
      {
    if (board[row][j] == (char) (n + '0'))
      return false;
      }

    int sr = 3 * (row / 3);
    int sc = 3 * (col / 3);
//check 3*3 matrix
    for (int i = sr; i < sr + 3; i++)
      {
    for (int j = sc; j < sc + 3; j++)
      {
        if (board[i][j] == (char) (n + '0'))
          return false;

      }
      }
    return true;
  }
}

测试输入 #

[["5","3",".",".","7",".",".",".","."],["6",".",".","1","9","5",".",".","."],[".","9","8",".",".",".",".","6","."],["8",".",".",".","6",".",".",".","3"],["4",".",".","8",".","3",".",".","1"],["7",".",".",".","2",".",".",".","6"],[".","6",".",".",".",".","2","8","."],[".",".",".","4","1","9",".",".","5"],[".",".",".",".","8",".",".","7","9"]]

实际输出 #

[[".",".",".",".","7",".",".",".","."],["6",".",".","1","9","5",".",".","."],[".","9","8",".",".",".",".","6","."],["8",".",".",".","6",".",".",".","3"],["4",".",".","8",".","3",".",".","1"],["7",".",".",".","2",".",".",".","6"],[".","6",".",".",".",".","2","8","."],[".",".",".","4","1","9",".",".","5"],[".",".",".",".","8",".",".","7","9"]]

预期输出 #

[["5","3","4","6","7","8","9","1","2"],["6","7","2","1","9","5","3","4","8"],["1","9","8","3","4","2","5","6","7"],["8","5","9","7","6","1","4","2","3"],["4","2","6","8","5","3","7","9","1"],["7","1","3","9","2","4","8","5","6"],["9","6","1","5","3","7","2","8","4"],["2","8","7","4","1","9","6","3","5"],["3","4","5","2","8","6","1","7","9"]]

问题分析与修正 #

核心错误 #

原代码的逻辑分支完全颠倒：

• 当当前位置是已填充的固定数字时，代码错误地在递归失败后尝试替换该数字（违反数独规则，固定数字不能修改）。
• 当当前位置是**空白（'.'）**时，代码没有进入填充逻辑，直接返回false，导致所有空白位置都被跳过。

修正后的代码 #

class Solution
{
  public void solveSudoku (char[][]board)
  {
    helper (board, 0, 0);
  }
  public boolean helper (char[][]board, int row, int col)
  {
    if (row == board.length)
      return true;
    // 计算下一个递归的行列
    int nrow = 0;
    int ncol = 0;

    if (col == board.length - 1)
    {
      nrow = row + 1;
      ncol = 0;
    }
    else
    {
      nrow = row;
      ncol = col + 1;
    }

    // 如果当前位置已有数字，直接递归下一个位置
    if (board[row][col] != '.')
    {
      return helper(board, nrow, ncol);
    }
    else
    {
      // 尝试1-9的数字
      for (int i = 1; i <= 9; i++)
      {
        if (isSafe(board, row, col, i))
        {
          board[row][col] = (char)(i + '0');
          // 递归下一个位置，成功则返回true
          if (helper(board, nrow, ncol))
            return true;
          // 回溯，重置为空白
          board[row][col] = '.';
        }
      }
      // 所有数字都尝试失败，返回false
      return false;
    }
  }

  public boolean isSafe (char[][]board, int row, int col, int n)
  {
    // 检查列
    for (int i = 0; i < board.length; i++)
    {
      if (board[i][col] == (char)(n + '0'))
        return false;
    }
    // 检查行
    for (int j = 0; j < board.length; j++)
    {
      if (board[row][j] == (char)(n + '0'))
        return false;
    }

    // 检查3*3小方格
    int sr = 3 * (row / 3);
    int sc = 3 * (col / 3);
    for (int i = sr; i < sr + 3; i++)
    {
      for (int j = sc; j < sc + 3; j++)
      {
        if (board[i][j] == (char)(n + '0'))
          return false;
      }
    }
    return true;
  }
}

关键修改点 #

1. 调整逻辑分支：
   • 当前位置是固定数字时，直接递归下一个位置，返回递归结果，不做任何修改。
   • 当前位置是空白时，才进入循环尝试1-9的数字，执行回溯逻辑。
2. 移除了原代码中错误的「替换固定数字」逻辑，确保数独的初始固定值不被修改。

修正后的代码可以正确填充数独，得到预期输出。

内容的提问来源于stack exchange，提问作者Aniket Ingawale