SCHOOL OF ECONOMICS

ECON2208

Introduction to Decision Science

2008 Session 2 group assignment2

Students :

Yu Shimada z3212000

Xin (Carol) Long z3157093

Hee Young (Angie) Parkz3246034

An Operation Research on Formulation Integer Program to Solve Sudoku Puzzle

I.introduction

T

he Sudoku game has become more and more popular recently as there have been many books on Sudoku and many newspapers that publish daily Sudoku puzzles. In light of the popularity of modelling in Excel and the popularity of using Solver it is highly instructive to express the popular Sudoku game as an Excel Solver Model.

Several operations researchers have written papers promoting the use of Excel. This report is based on the formulation method represented by Howard (2007), who used a 3-dimensional model with basic puzzle constraints to demonstrate the solving process for a specific Sudoku instance.

II.3-dimensional formulation

It is shown that most Sudoku games are displayed in a 9 by 9 form. In this report, we only consider this form. However, all concepts are easily transferred to any other Sukodugames wit other forms such as 4 by 4 and etc.

The table below is a sample of a standard 9 by 9 puzzle.

1 / 9
5 / 9 / 7 / 3
2
6
4
3 / 4
8 / 9

Note tat the total number of variables is 9X9X9=729 . We do not have the objective value since the goal is simply to find a feasible solution.

In our excel file for this report, the cells shaded in different colours represent the 729 variables with value of 1,2,…,9 respectively. Using different colours helps us to identify the variables easily. For example, in the yellow table which represents values of 3, cells shown with figure 1 indicate all the corresponding elements of the solution table1 all have the value of 3.

Now we are going to set up the constraints for this model.

Let if the cell in row i and column j of the puzzle has the value k, where i, j,k = 1, 2, … ,9.

We have five constraints:

  1. Each cell contains a single integer.
  2. Each integer appears only once in each (3 by 3) grid.
  3. Each integer appears only once in each row.
  4. Each integer appears only once in each column.
  5. The specified elements of the individual puzzle appear in cells.

Variables: (which is binary, i, j, k=1,2,…,9)

s.t.

i=1:9 j=1:9 (1.)every position in matrix must be filled.

j=1:9 k=1:9 (3.)only one k in each row

i=1:9 k=1:9 (4.)only one k in each column

i=1:3, j=1:3 (2)

i=4:6, j=1:3 (2)

i=7:9, j=1:3 (2)

i=1:3, j=4:6 (2)

i=4:6, j=4:6 (2)

i=7:9, j=4:6 (2)

i=1:3, j=7:9 (2)

i=4:6, j=7:9 (2)

i=7:9, j=7:9 (2)

The next step is to add the individual constraints imposed by the specific puzzle which is shown in table2 in the excel file.

Excel’s standard solver is limited to 200 variables and the 9 by 9 problem has 729 variables. Thus for this problem, a premium solver is required.

III.conclusion

We have successfully solved all puzzles that we have attempted using this model. Historical studies have demonstrated many other methods to solve Sudoku games. In this report, we model Sudoku with 3-dimensional approach. Afterwards, we rearrange the spreadsheet to enter the basic puzzle constraints into premium Solver. We then demonstrate how to include the solution for a specific Sukodu instance.