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 lled with a number from f1; 2; : : : ; 9g, where some entries are already lled 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. Speci cally, we have xi;j;k 2 f0; 1g 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 nd a member in the feasible set de ned by
-
(8i; k);
Pj
xi;j;k = 1
(8i; j);
k xi;j;k = 1
(8j; k);Pi xi;j;k = 1
(8k; 8(3 3)
block b);
P
x
i;j;k
= 1
(i;j)2b
P
The rst 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 le as a command-line input, print out the initial- and nal-board poistions (cf. gure 3 for an illustration). The input le is formatted as follows { there are 9 rows and 9 numbers, where the number 0 represents the un lled-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 rst 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++ stu { all you have to do, is to gure 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 well-versed/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 le called input, which was used in the illustrative example of gure 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 le is exactly the same as the previous programming assignment. I am looking for an output that looks something like what is shown in gure 3.
Essentially, each time lpsolve nds a solution to the puzzle, you have to add an extra constraint that eliminates/precludes the solution. You use lpsolve to nd a solution of the newly constructed ILP to nd a di erent solution (if one exists). This process is repeated till no more new solutions can be found.
3
Figure 3: Sample output.
4
