Programming Assignment 2: Sudoku Solver via Exhaustive Solution

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.

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 positions (cf. gure 4 for an illustration). The input le is formatted as follows

























Figure 1: Sample output.

{ 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.

The approach you will take for this assignment is to use recursion to imple-ment an exhaustive-search procedure that solves a Sudoku puzzle. That is, you start with the rst un lled-value in the board and pick a valid assignment that satis es the row-, column- and block-constraints identi ed above. Following this, you move to the next un lled position and do the same. If at some point in this process you reach a partially- lled board-position that cannot be lled


1






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 4. The 0’s represent the incomplete board positions/values.




further under the three constraints, you backtrack to the last assignment that was made before you got stuck and modify the assigned value accordingly. This can be implemented using recursion as follows:


Boolean Solve(row, column)

    1: Find an i row and j column such that puzzle[i][j] = 0. If you cannot nd such an i and j, then you have solved the puzzle.

    2: for k 2 f1; 2; : : : ; 9g do

    3: puzzle[i][j] = k.

    4: if Row-, Column- and Block-Assignment constraints are satis ed by the above assignment, and Solve(i, j) returns true then

    5: Return true.

    6: end if

    7: end for

f /* If we got here then all assignments made to puzzle[i][j] are invalid. So, we reset its value and return false*/g.
    8: puzzle[i][j] = 0

    9: Return false.

Figure 3: Pseudo-code for the recursive implementation of the exhaustive-search algorithm for the Sudoku puzzle. You solve the puzzle by calling Solve(0,0), assuming the indices are in the range f0; 1; : : : ; 8g.



First Part of the Assignment

Your implementation should use a class Sudoku with appropriately de ned pri-vate and public functions that

1. check if the row-, column- and block-assignment constraints are met,


2





    2. reads the incomplete puzzle from an input le that is read at the command-line,

    3. prints the puzzle at any point of the search.

along with a recursive procedure that solves the puzzle that was introduced above.

Second Part of the Assignment

The following blog mentions Sudoku puzzles that can have multiple solutions. I want you to modify your code from the second programming assignment to nd all solutions to a Sudoku puzzle.

You de nitely want to be cautious with this { the empty Sudoku puzzle has theoretically 6,670,903,752,021,072,936,960 solutions. The last thing you want to do is to attempt to print them out! You will nd four input les on Compass that identi es four di erent Sudoku puzzles. Two of them have just one solution, while the other two have multiple solutions. I suggest you run your code on these input les.

Write a C++ program that takes the initial board position as input and presents all solutions the 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 positions (cf. gure 4 for an illustration). The input le format is exactly the same as what was used for the second programming assignment.

The approach you will take for this assignment is to use recursion to modify the exhaustive-search procedure that solved the Sudoku puzzle in the second programming assignment. This is a relatively straightforward thing to do, if you have understood the recursion in the previous programming assignment.
























3





















































Figure 4: Sample output.







4