Description
A Sudoku Puzzle consists of a 9 × 9 grid, that is subdivided into nine 3 × 3
blocks. Each entry in the grid must be filled with a number from {1, 2, . . . , 9},
where some entries are already filled in. The constraints are that every number
should occur exactly once in each row, each column, and each 3 × 3 block.
The easiest (from a modeling standpoint, at least) way to solve this is to use
BILP formulation. Specifically, we have xi,j,k ∈ {0, 1} where
xi,j,k =
1 if the i-th row, j-th column entry is k
0 otherwise.
Technically, we do not need an objective function (but lpsolve will require you to
invent something). We are looking to find a member in the feasible set defined
by
(∀i, j),
P
k
xi,j,k = 1
(∀i, k),
P
j
xi,j,k = 1
(∀j, k),
P
i
xi,j,k = 1
(∀k, ∀(3 × 3) block b),
P
(i,j)∈b
xi,j,k = 1
The first constraint says that each entry should have one number in it. The
second, third and fourth constraints say that each number should occur once in
each row, column, and block, respectively.
First Part: Finding a solution using lp solve
Write a C++ program that takes the initial board position as input and presents
the solved puzzle as the output. Your program is to take the name of the input
file as a command-line input, print out the initial- and final-board poistions (cf.
figure 3 for an illustration). The input file is formatted as follows – there are
9 rows and 9 numbers, where the number 0 represents the unfilled-value in the
initial board. Figure 2 contains an illustrative sample.
You will need to make sure you have the Lpsolve API is installed on your
machine. This was covered in the first week of class, and there is an handout
on Compass that tells you how you can go about doing it. I have also uploaded
sudoku hint.cpp that takes care of the nitty-gritty C++ stuff – all you have
to do, is to figure out how the constraints can be inserted at the appropriate
spots in the code. You do not have to use my sample code if you are wellversed/comfortable with C++.
1
Figure 1: Sample output.
9 0 0 7 0 3 5 0 4
0 0 0 0 0 0 6 7 0
0 0 6 4 5 0 8 0 0
0 1 5 2 0 0 0 6 3
0 0 0 5 0 6 0 0 0
6 7 0 0 0 9 4 5 0
0 0 8 0 4 7 2 0 0
0 4 7 0 0 0 0 0 0
3 0 9 1 0 8 0 0 5
Figure 2: Sample input file called input, which was used in the illustrative
example of figure 3. The 0’s represent the incomplete board positions/values.
2
Second Part: Finding all solutions using lp solve
Using the lpsolve API, write a C++ program that takes the initial board position
as input and presents all solutions to a Sudoku puzzle. The format of the input
file is exactly the same as the previous programming assignment. I am looking
for an output that looks something like what is shown in figure 3.
Essentially, each time lpsolve finds a solution to the puzzle, you have to add
an extra constraint that eliminates/precludes the solution. You use lpsolve to
find a solution of the newly constructed ILP to find a different solution (if one
exists). This process is repeated till no more new solutions can be found.
3
Figure 3: Sample output.
4
