Sudoku Solver in R

Code
R
Author

M. L. DeBusk-Lane

Published

February 28, 2020

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…

board <- 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)

First, it’s important to push this into a matrix.

board <- matrix(board, nrow = 9, ncol = 9, byrow = TRUE) 

Next, lets develop the code to render each cell’s possible answers:

possible <- function(board, i, j){
  # Creates an all TRUE logical vector
  possible <- rep(TRUE,9)
  # Lists all known numbers from the row, column, and 3x3 cell
  selected_num <- unique(c(board[i,], board[,j], board[3*((i-1) %/% 3) + 1:3, 3*((j-1) %/% 3) + 1:3]))
  # Removes NAs
  selected_num <- na.omit(selected_num)
  # Changes the logical vector to FALSE for all values currently in use for the row, column, and 3x3 cell
  possible[selected_num] <- FALSE
  # 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. 
solve <- function(board, progress = 81) {
  # Provision to make a matrix with 0s into NA for future processing
  if  (0 %in% board) {
    board[board == 0] <- NA
  } 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)
  i <- ((progress - 1) %% 9) + 1 
  j <- ((progress - 1) %/% 9) + 1 
  # If a spot is open, identifies what numbers are available `choices`
  if (is.na(board[i, j])) {
    choices <- which(possible(board, i, j))
  } else{
    choices <- c(board[i, j])
  }
  # Try each possible choice, until all the requirements of the two functions are satisfied. 
  for (k in choices) {
    board[i, j] <- k
    # recursion
    answer <- solve(board, progress - 1)
    # 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

BibTeX citation:
@online{l.debusk-lane2020,
  author = {M. L. DeBusk-Lane},
  title = {Sudoku {Solver} in {R}},
  date = {2020-02-28},
  langid = {en}
}
For attribution, please cite this work as:
M. L. DeBusk-Lane. 2020. “Sudoku Solver in R.” February 28, 2020.