sta*_*oob 0 algorithm r matrix sudoku backtracking
假设我有以下数独：
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)
[,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）对于给定的行或给定的列 - 哪些数字是有效的选择？
以下代码查看第一列中哪些可能的数字是有效选择：
y = 1:9
setdiff(y, problem[1,])
[1] 1 2 3 9
2) 在任何时候，给定的行或列是否会导致违规？（即同一数字多次出现 - 不包括 0）
#TRUE = no violation, FALSE = violation
check_vector <- function(v) {
for (i in 1:9) {
if (sum(v == i) > 1) {
return(FALSE)
}
}
return(TRUE)
}
# no violation
v1 = c(5, 3, 0, 0, 7, 0, 0, 0, 0)
# violation (3,3)
v2 = c(5, 3, 3, 0, 7, 0, 0, 0, 0)
> check_vector(v1)
[1] TRUE
> check_vector(v2)
[1] FALSE
我的问题：我不知道如何一起使用这些功能来回溯数独并填写所有数字。有人可以告诉我该怎么做吗？
谢谢！
注意：如果可能的话，我希望最终答案使用我已经编写的代码
如果你想在不使用额外的包的情况下解决它，你可以尝试下面的代码，它有点使用“回溯”的想法（但不完全相同）。
请注意，下面的代码只是一种实现示例，还不够优化。您可能会在那里找到一些提示，并根据您的口味进一步优化它。
sudoku <- function(m) {
# check valid values to fill in the given position of matrix
checker <- function(mat, i, j) {
iblk <- 3 * (ceiling(i / 3) - 1) + (1:3)
jblk <- 3 * (ceiling(j / 3) - 1) + (1:3)
u <- unique(c(mat[i, ], mat[, j], mat[iblk, jblk]))
setdiff(1:9, u)
}
# help to generate all possible matrices
helper <- function(m, idx) {
i <- (idx - 1) %/% 9 + 1
j <- (idx - 1) %% 9 + 1
if (m[i, j] == 0) {
u <- checker(m, i, j)
lapply(u, \(x) {
m[i, j] <- x
m
})
} else {
list(m)
}
}
# initial value
lst <- list(m)
cnt <- 1
repeat {
lst <- unlist(
lapply(
lst,
helper,
idx = cnt
),
recursive = FALSE
)
if (cnt == length(m)) {
return(lst[[1]])
}
cnt <- cnt + 1
}
}
> (solution <- sudoku(problem))
[,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9]
[1,] 5 6 1 8 4 7 9 2 3
[2,] 3 7 9 5 2 1 6 8 4
[3,] 4 2 8 9 6 3 1 7 5
[4,] 6 1 3 7 8 9 5 4 2
[5,] 7 9 4 6 5 2 3 1 8
[6,] 8 5 2 1 3 4 7 9 6
[7,] 9 3 5 4 7 8 2 6 1
[8,] 1 4 6 2 9 5 8 3 7
[9,] 2 8 7 3 1 6 4 5 9
我想采用以下解决方案：
repeat {
possible <- rep(1:9, each = 9^2) |>
array(dim = c(9,9,9))
for(j in 1:9) {
for(i in 1:9) {
if (!is.na(problem[i,j]) && problem[i,j] != 0) {
possible[i,j,-problem[i,j]] <- NA
possible[-i,j,problem[i,j]] <- NA
possible[i,-j,problem[i,j]] <- NA
possible[(floor((i-1)/3)*3 + 1):(floor((i-1)/3)*3 + 3),
(floor((j-1)/3)*3 + 1):(floor((j-1)/3)*3 + 3),
problem[i,j]] <- NA
possible[i,j,problem[i,j]] <- problem[i,j]
}
}
}
collapsed_problem <- matrix(rep(NA, 81) |> as.numeric(), nrow = 9)
for(j in 1:9) {
for(i in 1:9) {
if (table(possible[i, j, ]) |> length() == 1) {
collapsed_problem[i, j] <- table(possible[i, j, ]) |> attr("dimnames") |> unlist() |> as.numeric()
}
for(k in 1:9) {
if (table(possible[(floor((i-1)/3)*3+1):(floor((i-1)/3)*3+3),
(floor((j-1)/3)*3+1):(floor((j-1)/3)*3+3),
k] ) == 1) {
offs <- which(
possible[(floor((i-1)/3)*3+1):(floor((i-1)/3)*3+3),
(floor((j-1)/3)*3+1):(floor((j-1)/3)*3+3),
k] == k,
arr.ind = T)
collapsed_problem[floor((i-1)/3)*3 + offs[1], floor((j-1)/3)*3 + offs[2]] <- k
}
}
}
}
print(collapsed_problem)
if (sum(problem, na.rm = T) == sum(collapsed_problem, na.rm = T) ||
!any(is.na(collapsed_problem))
) {
problem <- collapsed_problem
break
}
problem <- collapsed_problem
}
此代码将迭代返回以下结果（我决定使用 NA 而不是 0，因为 NA 假设单元格中没有值，而 0 是特定值）：
[,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9]
[1,] 5 6 NA 8 4 7 NA NA NA
[2,] 3 NA 9 NA NA NA 6 8 NA
[3,] NA NA 8 NA 6 3 NA NA NA
[4,] NA 1 NA NA 8 NA NA 4 NA
[5,] 7 9 NA 6 5 2 NA 1 8
[6,] 8 5 NA NA 3 NA 7 9 NA
[7,] NA NA 5 NA NA 8 2 NA 1
[8,] NA NA 6 NA NA NA 8 3 7
[9,] NA NA NA 3 1 6 4 5 9
[,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9]
[1,] 5 6 NA 8 4 7 NA 2 NA
[2,] 3 NA 9 NA 2 NA 6 8 NA
[3,] NA NA 8 9 6 3 NA 7 NA
[4,] 6 1 NA 7 8 9 NA 4 NA
[5,] 7 9 NA 6 5 2 3 1 8
[6,] 8 5 NA NA 3 NA 7 9 NA
[7,] NA 3 5 NA NA 8 2 6 1
[8,] 1 NA 6 NA NA NA 8 3 7
[9,] 2 8 NA 3 1 6 4 5 9
[,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9]
[1,] 5 6 1 8 4 7 9 2 3
[2,] 3 7 9 NA 2 NA 6 8 NA
[3,] 4 2 8 9 6 3 NA 7 NA
[4,] 6 1 3 7 8 9 5 4 NA
[5,] 7 9 4 6 5 2 3 1 8
[6,] 8 5 NA NA 3 NA 7 9 6
[7,] 9 3 5 4 7 8 2 6 1
[8,] 1 4 6 2 9 NA 8 3 7
[9,] 2 8 7 3 1 6 4 5 9
[,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9]
[1,] 5 6 1 8 4 7 9 2 3
[2,] 3 7 9 NA 2 NA 6 8 4
[3,] 4 2 8 9 6 3 1 7 5
[4,] 6 1 3 7 8 9 5 4 2
[5,] 7 9 4 6 5 2 3 1 8
[6,] 8 5 2 1 3 4 7 9 6
[7,] 9 3 5 4 7 8 2 6 1
[8,] 1 4 6 2 9 5 8 3 7
[9,] 2 8 7 3 1 6 4 5 9
[,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9]
[1,] 5 6 1 8 4 7 9 2 3
[2,] 3 7 9 5 2 1 6 8 4
[3,] 4 2 8 9 6 3 1 7 5
[4,] 6 1 3 7 8 9 5 4 2
[5,] 7 9 4 6 5 2 3 1 8
[6,] 8 5 2 1 3 4 7 9 6
[7,] 9 3 5 4 7 8 2 6 1
[8,] 1 4 6 2 9 5 8 3 7
[9,] 2 8 7 3 1 6 4 5 9
并最终解决问题。