*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 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?

## Problem Formulation

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:"`

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: