Solving Sudoku with Integer Programming in R
Sandipan Dey
5 November 2016
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 3x3 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?
Problem Formulation
Let’s solve the integer programming problem using R Rglpk.
## [1] "objective function vector length: 729"## [1] "dimension of the constraint matrix: 354x729"## [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:"
## $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:
