如何结合现有代码实现数独手动回溯求解？

待求解的数独矩阵 #

problem <- matrix(c(
    5, 3, 0, 0, 7, 0, 0, 0, 0,
    6, 0, 0, 1, 9, 5, 0, 0, 0,
    0, 9, 8, 0, 0, 0, 0, 6, 0,
    8, 0, 0, 0, 6, 0, 0, 0, 3,
    4, 0, 0, 8, 0, 3, 0, 0, 1,
    7, 0, 0, 0, 2, 0, 0, 0 ,6,
    0 ,6 ,0 ,0 ,0 ,0 ,2 ,8 ,0,
    0 ,0 ,0 ,4 ,1 ,9 ,0 ,0 ,5,
    0 ,0 ,0 ,0 ,8 ,0 ,0 ,7 ,9
), nrow = 9)

注：以下为用户粘贴的额外矩阵内容，与上述problem定义不符，仅供参考：

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

已实现的功能 #

1. 计算指定行/列的有效候选数字 #

通过setdiff获取1-9中未出现在目标行/列的数字，即为该行/列的有效候选数：

y <- 1:9
# 计算第1行的有效候选数字
setdiff(y, problem[1,])
# 输出：[1] 1 2 4 6 8 9

2. 行/列重复数字检查函数 #

该函数验证指定行/列（排除0）是否存在重复数字，返回TRUE表示无违规，FALSE表示存在重复：

# TRUE = 无违规，FALSE = 存在违规
check_vector <- function(v) {
  for (i in 1:9) {
    if (sum(v == i) > 1) {
      return(FALSE)
    }
  }
  return(TRUE)
}

# 无违规示例
v1 <- c(5, 3, 0, 0, 7, 0, 0, 0, 0)
# 存在违规示例（重复的3）
v2 <- c(5, 3, 3, 0, 7, 0, 0, 0, 0)

check_vector(v1)
# 输出：[1] TRUE
check_vector(v2)
# 输出：[1] FALSE

问题 #

不清楚如何结合上述两个功能，通过回溯法完成数独的全部数字填充，希望基于已编写的代码实现求解。

基于现有代码的回溯法实现 #

要完成数独求解，需补充3x3宫格的重复检查，再结合回溯逻辑实现递归填充：

1. 补充宫格检查相关函数 #

# 获取指定位置所在的3x3宫格
get_box <- function(mat, row, col) {
  box_row <- ((row - 1) %/% 3) * 3 + 1
  box_col <- ((col - 1) %/% 3) * 3 + 1
  mat[box_row:(box_row+2), box_col:(box_col+2)]
}

# 检查宫格内是否存在重复数字（排除0）
check_box <- function(mat, row, col) {
  box <- get_box(mat, row, col)
  check_vector(as.vector(box))
}

# 综合检查：行、列、宫格均无违规
is_valid <- function(mat, row, col, num) {
  # 复制矩阵并填入数字
  temp_mat <- mat
  temp_mat[row, col] <- num
  # 检查行、列、宫格
  check_vector(temp_mat[row, ]) && 
  check_vector(temp_mat[, col]) && 
  check_box(temp_mat, row, col)
}

2. 回溯求解函数 #

solve_sudoku <- function(mat) {
  # 遍历所有单元格，找到第一个未填充的位置（值为0）
  for (row in 1:9) {
    for (col in 1:9) {
      if (mat[row, col] == 0) {
        # 获取当前单元格的候选数字（行中未出现的数字）
        candidates <- setdiff(1:9, mat[row, ])
        # 遍历候选数字尝试填充
        for (num in candidates) {
          if (is_valid(mat, row, col, num)) {
            # 填入数字并递归求解
            mat[row, col] <- num
            result <- solve_sudoku(mat)
            # 如果递归返回有效解，直接返回
            if (!is.null(result)) {
              return(result)
            }
            # 回溯：当前数字导致无解，恢复为0
            mat[row, col] <- 0
          }
        }
        # 所有候选数字都无效，返回NULL表示无解
        return(NULL)
      }
    }
  }
  # 所有单元格已填满，返回解
  return(mat)
}

3. 调用求解 #

# 求解数独
solution <- solve_sudoku(problem)
# 打印结果
print(solution)

输出的有效解为：

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

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