Solving Sudoku with Integer Programming in R

This problem appeared as a homework problem in the problem set in the edX course MITx: 15.053x Optimization Methods in Business Analytics.

Problem Statement

Sudoku is a popular number puzzle. The goal is to place the digits in [1,9] on a nine-by-nine grid, with some of the digits already filled in, where [1,9] denotes the set of integers from 1 to 9. Your solution must satisfy the following four rules:

  • Rule 1. Each cell contains an integer in [1,9].
  • Rule 2. Each row must contain each of the integers in [1,9].
  • Rule 3. Each column must contain each of the integers in [1,9].
  • Rule 4. Each of the nine 3×3 squares with bold outlines must contain each of the integers in [1,9].

Sudoku isn’t an optimization problem, it’s actually a feasibility problem: we wish to find a feasible solution that satisfies these rules. You can think of it as an optimization problem in which the objective is always equal to 0. This problem firsts asks you to use integer programming formulation techniques to model the rules of Sudoku. It then asks you to solve it.

Formulate the rules and solve the following Sudoku puzzle as a feasibility problem. What is the value of A+B+C in your solution?

sudokuabc

Problem Formulation
rules

The above five constraints exactly represent all the four rules of Sudoku. Let’s solve the integer programming problem using R Rglpk.

## [1] "objective function vector length: 729"
## [1] "dimension of the constraint matrix: 354 x 729"
## [1] "an arbitrary block subset of the constraint matrix [81:90, 131:140] shown below:"
##     [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9] [,10]
## row    0    1    0    0    0    0    0    0    0     0
## row    0    0    1    0    0    0    0    0    0     0
## row    0    0    0    1    0    0    0    0    0     0
## row    0    0    0    0    1    0    0    0    0     0
## row    0    0    0    0    0    1    0    0    0     0
## row    0    0    0    0    0    0    1    0    0     0
## row    0    0    0    0    0    0    0    1    0     0
## row    0    0    0    0    0    0    0    0    1     0
## row    0    0    0    0    0    0    0    0    0     1
## row    0    0    0    0    0    0    0    0    0     0
## [1] "The binary constraint matrix as image:"

mat.png

The following is the solution that Rglpk came up with as a result of the feasibility integer program with the above constraints:

## $optimum
## [1] 0
## 
## $solution
##   [1] 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0
##  [36] 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0
##  [71] 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0
## [106] 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 1 0 0
## [141] 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0
## [176] 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0
## [211] 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0
## [246] 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0
## [281] 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0
## [316] 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0
## [351] 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1
## [386] 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0
## [421] 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 1 0
## [456] 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0
## [491] 0 0 0 0 1 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1
## [526] 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0
## [561] 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0
## [596] 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0
## [631] 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0
## [666] 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0
## [701] 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1
## 
## $status
## [1] 0
## [1] 81
## [1] "A + B + C =  5"

The following is the solution that Rglpk came up with converted to the tabular form for Sudoku:
solution

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s