This website uses cookies to collect usage information in order to offer a better browsing experience. By browsing this site or by clicking on the "ACCEPT COOKIES" button you accept our Cookie Policy.

How to Solve Sudoku with R – Open Source Automation

TheAutomatic.net

Contributor:
TheAutomatic.net
Visit: TheAutomatic.net

By:

Blogger, TheAutomatic.net, and Senior Data Scientist

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!

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 if 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.

Visit TheAutomatic.net for additional insight on this topic: http://theautomatic.net/2020/11/25/how-to-solve-sudoku-with-r/.

Disclosure: Interactive Brokers

Information posted on IBKR Traders’ Insight that is provided by third-parties and not by Interactive Brokers does NOT constitute a recommendation by Interactive Brokers that you should contract for the services of that third party. Third-party participants who contribute to IBKR Traders’ Insight are independent of Interactive Brokers and Interactive Brokers does not make any representations or warranties concerning the services offered, their past or future performance, or the accuracy of the information provided by the third party. Past performance is no guarantee of future results.

This material is from TheAutomatic.net and is being posted with permission from TheAutomatic.net. The views expressed in this material are solely those of the author and/or TheAutomatic.net and IBKR is not endorsing or recommending any investment or trading discussed in the material. This material is not and should not be construed as an offer to sell or the solicitation of an offer to buy any security. To the extent that this material discusses general market activity, industry or sector trends or other broad based economic or political conditions, it should not be construed as research or investment advice. To the extent that it includes references to specific securities, commodities, currencies, or other instruments, those references do not constitute a recommendation to buy, sell or hold such security. This material does not and is not intended to take into account the particular financial conditions, investment objectives or requirements of individual customers. Before acting on this material, you should consider whether it is suitable for your particular circumstances and, as necessary, seek professional advice.

In accordance with EU regulation: The statements in this document shall not be considered as an objective or independent explanation of the matters. Please note that this document (a) has not been prepared in accordance with legal requirements designed to promote the independence of investment research, and (b) is not subject to any prohibition on dealing ahead of the dissemination or publication of investment research.

Any trading symbols displayed are for illustrative purposes only and are not intended to portray recommendations.

trading top