Using the basic sudoku puzzle from wikipedia HERE, we’ll start to build this out.
Using the same input methods as the python version (here)
Lets bring in the actual board…
<- c(5,3,0,0,7,0,0,0,0,
board 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)
First, it’s important to push this into a matrix.
<- matrix(board, nrow = 9, ncol = 9, byrow = TRUE) board
Next, lets develop the code to render each cell’s possible answers:
<- function(board, i, j){
possible # Creates an all TRUE logical vector
<- rep(TRUE,9)
possible # Lists all known numbers from the row, column, and 3x3 cell
<- unique(c(board[i,], board[,j], board[3*((i-1) %/% 3) + 1:3, 3*((j-1) %/% 3) + 1:3]))
selected_num # Removes NAs
<- na.omit(selected_num)
selected_num # Changes the logical vector to FALSE for all values currently in use for the row, column, and 3x3 cell
<- FALSE
possible[selected_num] # Returns this logical vector for use in subsequent functions...
return(possible)
}
As the comments imply, we are simply returning a logical vector list that describes which numbers are available or possible
.
Next, we’ll draft the function to iterate through all cells and determine a solution through recursion.
# The 'board' argument here provides the matrix, length 81 (9x9), to iterate through.
# The 'progress' argument here provides a starting value to recursively iterate through.
<- function(board, progress = 81) {
solve # Provision to make a matrix with 0s into NA for future processing
if (0 %in% board) {
== 0] <- NA
board[board else board
} # Once all cells have been assessed within the 'possible_choices' function, it stops the recursion.
if (progress == 0) {
# Successfully filled in the board
return(board)
}# Get the i,j coordinates
# A fancy way to iterate through the coordinate numbers one by one (right to left, bottom to top)
<- ((progress - 1) %% 9) + 1
i <- ((progress - 1) %/% 9) + 1
j # If a spot is open, identifies what numbers are available `choices`
if (is.na(board[i, j])) {
<- which(possible(board, i, j))
choices else{
} <- c(board[i, j])
choices
}# Try each possible choice, until all the requirements of the two functions are satisfied.
for (k in choices) {
<- k
board[i, j] # recursion
<- solve(board, progress - 1)
answer # If all possible positions have been completed, simply return the answer.
if (!is.null(answer)) {
return(answer)
}
}return(NULL)
}
Although there is a lot going on here, I’ve attempted to put in some fairly descriptive comments. I tried to follow the Python code thematic plan, while using some of R’s fantastic infix operators to skip a few steps here or there and a bit of recursion. You’ll also note that I also switch all zeros to NAs, to make things a bit easier to code using is.na
.
solve(board)
[,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
Arguably, I’m not a base R coder or programmer. Therefore, much of this post was generated from various websites, SOF, and other corners of the web–the R community is amazing. In a future post, I’ll work to re-write this in some type of tidyverse rendition… if that is a thing. I’ll at least try.
Reuse
Citation
@online{l.debusk-lane2020,
author = {M. L. DeBusk-Lane},
title = {Sudoku {Solver} in {R}},
date = {2020-02-28},
langid = {en}
}