In this post we discuss how to write an R script to solve any Sudoku puzzle. There are some R packages to handle this, but in our case, we’ll write our own solution. For our purposes, we’ll assume the input Sudoku is a 9×9 grid. At the end result, each row, column, and 3×3 box needs to contain exactly one of each integer 1 through 9.

*Learn more about data science by checking out the great curriculum at 365 Data Science!*

Contents

**Step 0) Define a sample board**

Let’s define a sample Sudoku board for testing. Empty cells will be represented as zeroes.

board <- matrix(

c(0,0,0,0,0,6,0,0,0,

0,9,5,7,0,0,3,0,0,

4,0,0,0,9,2,0,0,5,

7,6,4,0,0,0,0,0,3,

0,0,0,0,0,0,0,0,0,

2,0,0,0,0,0,9,7,1,

5,0,0,2,1,0,0,0,9,

0,0,7,0,0,5,4,8,0,

0,0,0,8,0,0,0,0,0),

byrow = T,

ncol = 9

)

**Step 1) Find the empty cells**

In the first step, let’s write a function that will find all of the empty cells on the board.

find_empty_cells <- function(board) {

which(board == 0, arr.ind = TRUE)

}

**Step 2) Make sure cell placement is valid**

Next, we need a function that will check if a cell placement is valid. In other words, if we try putting a number into a particular cell, we need to ensure that the number appears only once in that row, column, and box. Otherwise, the placement would not be valid.

is_valid <- function(board, num, row, col) {

# Check if any cell in the same row has value = num

if(any(board[row, ] == num)) {

return(FALSE)

}

# Check if any cell in the same column has value = num

if(any(board[, col] == num)) {

return(FALSE)

}

# Get cells in num’s box

box_x <- floor((row – 1) / 3) + 1

box_y <- floor((col – 1) / 3) + 1

# Get subset of matrix containing num’s box

box <- board[(3 * box_x – 2):(3 * box_x), (3 * box_y – 2):(3 * box_y)]

# Check if the number appears elsewhere in its box

if(any(box == num)) {

return(FALSE)

}

return(TRUE)

}

**Step 3) Recursively solve the Sudoku**

In the third step, we write our function to solve the Sudoku. This function will return **TRUE** is the input Sudoku is solvable. Otherwise, it will return **FALSE**. The final result will be stored in a separate variable.

solve_sudoku <- function(board, needed_cells = NULL, index = 1) {

# Find all empty cells

if(is.null(needed_cells))

needed_cells <- find_empty_cells(board)

if(index > nrow(needed_cells)) {

# Set result equal to current value of board

# and return TRUE

result <<- board

return(TRUE)

} else {

row <- needed_cells[index, 1]

col <- needed_cells[index, 2]

}

# Solve the Sudoku

for(num in 1:9) {

# Test for valid answers

if(!is_valid(board, num, row, col)) {next} else{

board2 = board

board2[row, col] <- num

# Retest with input

if(solve_sudoku(board2, needed_cells, index + 1)) {

return(TRUE)

}

}

}

# If not solvable, return FALSE

return(FALSE)

}

**Calling the Sudoku solver**

Lastly, we call our Sudoku solver. The result is stored in the variable “result”, as can be seen below.

solve_sudoku(board)

**Conclusion**

That’s it for this post! If you enjoyed reading this and want to learn more about R or Python, check out the great data science program at 365 Data Science.

The post How to solve Sudoku with R appeared first on Open Source Automation.

*Permanent link to this post here*