CMPSC 16 Final Project (Sudoku Solver)
In this project, you will write a computer program that will solve the popular Sudoku game.
In Sudoku, the player is presented a partly filled in gameboard, and is expected to find the missing numbers that will complete the board while adhearing to 3 simple rules.

The goal is to fill in the game board so that the numbers 1 through 9 occur exactly once in each row, column, and 3x3 box.
The numbers can appear in any order and diagonals are not considered.
 ╔═══╤═══╤═══╦═══╤═══╤═══╦═══╤═══╤═══╗
a║   │   │   ║   │   │   ║   │   │   ║
 ╟───┼───┼───╫───┼───┼───╫───┼───┼───╢
b║   │   │   ║   │   │   ║   │   │   ║
 ╟───┼───┼───╫───┼───┼───╫───┼───┼───╢
c║   │   │   ║   │   │   ║   │   │   ║
 ╠═══╪═══╪═══╬═══╪═══╪═══╬═══╪═══╪═══╣
d║   │   │   ║   │   │   ║   │   │   ║
 ╟───┼───┼───╫───┼───┼───╫───┼───┼───╢
e║   │   │   ║   │   │   ║   │   │   ║
 ╟───┼───┼───╫───┼───┼───╫───┼───┼───╢
f║   │   │   ║   │   │   ║   │   │   ║
 ╠═══╪═══╪═══╬═══╪═══╪═══╬═══╪═══╪═══╣
g║   │   │   ║   │   │   ║   │   │   ║
 ╟───┼───┼───╫───┼───┼───╫───┼───┼───╢
h║   │   │   ║   │   │   ║   │   │   ║
 ╟───┼───┼───╫───┼───┼───╫───┼───┼───╢
i║   │   │   ║   │   │   ║   │   │   ║
 ╚═══╧═══╧═══╩═══╧═══╧═══╩═══╧═══╧═══╝
   1   2   3   4   5   6   7   8   9 

Fig.1 empty puzzle board

Your initial game board will consist of several numbers that are already placed (Fig. 2). Those numbers are called givens and cannot be changed. Your goal is to fill in the empty squares following the simple rule above.

 ╔═══╤═══╤═══╦═══╤═══╤═══╦═══╤═══╤═══╗
a║   │   │ 7 ║   │   │ 1 ║ 3 │   │   ║
 ╟───┼───┼───╫───┼───┼───╫───┼───┼───╢
b║ 3 │   │   ║   │ 5 │   ║ 6 │   │   ║
 ╟───┼───┼───╫───┼───┼───╫───┼───┼───╢
c║ 5 │   │ 8 ║   │ 3 │   ║   │   │ 4 ║
 ╠═══╪═══╪═══╬═══╪═══╪═══╬═══╪═══╪═══╣
d║   │ 8 │   ║   │ 6 │   ║ 9 │   │   ║
 ╟───┼───┼───╫───┼───┼───╫───┼───┼───╢
e║ 7 │   │   ║   │   │   ║   │   │ 6 ║
 ╟───┼───┼───╫───┼───┼───╫───┼───┼───╢
f║   │   │ 4 ║   │ 1 │   ║   │ 7 │   ║
 ╠═══╪═══╪═══╬═══╪═══╪═══╬═══╪═══╪═══╣
g║ 2 │   │   ║   │ 8 │   ║ 4 │   │ 3 ║
 ╟───┼───┼───╫───┼───┼───╫───┼───┼───╢
h║   │   │ 6 ║   │ 7 │   ║   │   │ 8 ║
 ╟───┼───┼───╫───┼───┼───╫───┼───┼───╢
i║   │   │ 5 ║ 9 │   │   ║ 7 │   │   ║
 ╚═══╧═══╧═══╩═══╧═══╧═══╩═══╧═══╧═══╝
   1   2   3   4   5   6   7   8   9
Sample Sudoku Board

Fig.2 puzzle board with givens

A filled-in row must have one of each digit. That means that each digit appears only once in the row. For example:

 ╔═══╤═══╤═══╦═══╤═══╤═══╦═══╤═══╤═══╗
a║ 3 │ 9 │ 2 ║ 1 │ 5 │ 8 ║ 7 │ 4 │ 6 ║
 ╟───┼───┼───╫───┼───┼───╫───┼───┼───╢

Fig.3 Sudoku sample puzzle's top row

Similarly, each digit must appear in a filled-in column exactly once. The first column could be filled as is shown below:
 ╔═══╤
a║ 3 │
 ╟───┼
b║ 1 │
 ╟───┼
c║ 8 │
 ╠═══╪
d║ 4 │
 ╟───┼
e║ 5 │
 ╟───┼
f║ 6 │
 ╠═══╪
g║ 2 │
 ╟───┼
h║ 7 │
 ╟───┼
i║ 9 │
 ╚═══╧
   1   

Fig. 4 Sudoku sample puzzle's first column.

There are nine 3x3 boxes, or regions surrounded by thick lines that must contain each digit exactly once. The top-left region could be filled as:
  ╔═══╤═══╤═══╦═
a║ 3 │ 9 │ 2 ║
  ╟───┼───┼───╫─
b║ 1 │ 5 │ 7 ║
 ╟───┼───┼───╫
c║ 8 │ 4 │ 6 ║
  ╠═══╪═══╪═══╬═

Fig. 5 Sudoku sample puzzle's top-left region


Your Assignment
You will be given a file with a Sudoku game in it. (Example input)

1. You must then print all of the possible values that could be entered into each cell, given the game rules. For example, the example input would output:

  Possible values:
  -------------------------------------------------------------------------------------------------------------------------------------------------------------------------
  |     1,2,3,5,8          1,3,8,9          1,2,5,8,9     |         6               2,5,7            2,5,7,8      |         4            1,2,3,5,7,9         1,2,7,9      |
  |         7               1,8,9          1,2,4,5,8,9    |       4,5,8             2,4,5               3         |         6              1,2,5,9            1,2,9       |
  |     2,3,4,5,6            3,6             2,4,5,6      |       4,5,7               9                 1         |      2,3,5,7              8                2,7        |
  -------------------------------------------------------------------------------------------------------------------------------------------------------------------------
  |    1,2,3,4,6,8       1,3,6,7,8,9      1,2,4,6,7,8,9   |      4,5,7,9           2,4,5,7          2,4,5,7,9     |      2,7,8,9           1,2,7,9         1,2,6,7,8,9    |
  |       2,4,6               5             2,4,6,7,9     |         1                 8              2,4,7,9      |       2,7,9             2,7,9               3         |
  |       1,2,8            1,7,8,9          1,2,7,8,9     |         3                2,7                6         |      2,7,8,9              4                 5         |
  -------------------------------------------------------------------------------------------------------------------------------------------------------------------------
  |       1,5,8               4              1,5,7,8      |         2              1,3,5,7           5,7,8,9      |     3,5,7,8,9             6               7,8,9       |
  |         9              1,6,7,8              3         |      4,5,7,8          1,4,5,6,7          4,5,7,8      |      2,5,7,8            2,5,7            2,4,7,8      |
  |       5,6,8               2              5,6,7,8      |     4,5,7,8,9         3,4,5,6,7         4,5,7,8,9     |         1              3,5,7,9           4,7,8,9      |
  -------------------------------------------------------------------------------------------------------------------------------------------------------------------------
2. At this point, you should write a function that will solve the puzzle by trying all possible values (Hint: A recursive function can make this really simple and clean). The output should look like this:

  Solved gameboard:
-------------------------------------------------------------------------------------------------------------------------------------------------------------------------
|         5                 8                 1         |         6                 7                 2         |         4                 3                 9         |
|         7                 9                 2         |         8                 4                 3         |         6                 5                 1         |
|         3                 6                 4         |         5                 9                 1         |         7                 8                 2         |
-------------------------------------------------------------------------------------------------------------------------------------------------------------------------
|         4                 3                 8         |         9                 5                 7         |         2                 1                 6         |
|         2                 5                 6         |         1                 8                 4         |         9                 7                 3         |
|         1                 7                 9         |         3                 2                 6         |         8                 4                 5         |
-------------------------------------------------------------------------------------------------------------------------------------------------------------------------
|         8                 4                 5         |         2                 1                 9         |         3                 6                 7         |
|         9                 1                 3         |         7                 6                 8         |         5                 2                 4         |
|         6                 2                 7         |         4                 3                 5         |         1                 9                 8         |
-------------------------------------------------------------------------------------------------------------------------------------------------------------------------
Time taken to solve the game: 0.693649 seconds.
3. Provide a write-up explaining your methodology for solving this problem. There is no minimum or maximum length, but you should explain why you solved it like you did, and more importantly how you "wanted" to solve it, if you couldn't get it to work. This will enable us to give you partial credit as long we understand your methodology.

4. (Extra Credit) For extra credit also write a version of your solver than can solve a non-standard size Sudoku board.

Grading
Reading in the intital puzzle: 10%
Printing the initial puzzle: 10%
Printing the board with possible values: 20%
Solving the puzzle: 20%
Written Report: 20%
Code style: 20%
A non-traditional size board: +10% (Extra)

Example


$ ssh [your username]@csil.cs.ucsb.edu
$ cd /cs/student/cspensky/cs16/sudoku/
$ ./sudoku input.txt
Reading gameboard....
Initial gameboard:
-------------------------------------------------------------------------------------------------------------------------------------------------------------------------
|                                                       |         6                                             |         4                                             |
|         7                                             |                                             3         |         6                                             |
|                                                       |                           9                 1         |                           8                           |
-------------------------------------------------------------------------------------------------------------------------------------------------------------------------
|                                                       |                                                       |                                                       |
|                           5                           |         1                 8                           |                                             3         |
|                                                       |         3                                   6         |                           4                 5         |
-------------------------------------------------------------------------------------------------------------------------------------------------------------------------
|                           4                           |         2                                             |                           6                           |
|         9                                   3         |                                                       |                                                       |
|                           2                           |                                                       |         1                                             |
-------------------------------------------------------------------------------------------------------------------------------------------------------------------------
Possible values:
-------------------------------------------------------------------------------------------------------------------------------------------------------------------------
|     1,2,3,5,8          1,3,8,9          1,2,5,8,9     |         6               2,5,7            2,5,7,8      |         4            1,2,3,5,7,9         1,2,7,9      |
|         7               1,8,9          1,2,4,5,8,9    |       4,5,8             2,4,5               3         |         6              1,2,5,9            1,2,9       |
|     2,3,4,5,6            3,6             2,4,5,6      |       4,5,7               9                 1         |      2,3,5,7              8                2,7        |
-------------------------------------------------------------------------------------------------------------------------------------------------------------------------
|    1,2,3,4,6,8       1,3,6,7,8,9      1,2,4,6,7,8,9   |      4,5,7,9           2,4,5,7          2,4,5,7,9     |      2,7,8,9           1,2,7,9         1,2,6,7,8,9    |
|       2,4,6               5             2,4,6,7,9     |         1                 8              2,4,7,9      |       2,7,9             2,7,9               3         |
|       1,2,8            1,7,8,9          1,2,7,8,9     |         3                2,7                6         |      2,7,8,9              4                 5         |
-------------------------------------------------------------------------------------------------------------------------------------------------------------------------
|       1,5,8               4              1,5,7,8      |         2              1,3,5,7           5,7,8,9      |     3,5,7,8,9             6               7,8,9       |
|         9              1,6,7,8              3         |      4,5,7,8          1,4,5,6,7          4,5,7,8      |      2,5,7,8            2,5,7            2,4,7,8      |
|       5,6,8               2              5,6,7,8      |     4,5,7,8,9         3,4,5,6,7         4,5,7,8,9     |         1              3,5,7,9           4,7,8,9      |
-------------------------------------------------------------------------------------------------------------------------------------------------------------------------
Solving the game...
Solved gameboard:
-------------------------------------------------------------------------------------------------------------------------------------------------------------------------
|         5                 8                 1         |         6                 7                 2         |         4                 3                 9         |
|         7                 9                 2         |         8                 4                 3         |         6                 5                 1         |
|         3                 6                 4         |         5                 9                 1         |         7                 8                 2         |
-------------------------------------------------------------------------------------------------------------------------------------------------------------------------
|         4                 3                 8         |         9                 5                 7         |         2                 1                 6         |
|         2                 5                 6         |         1                 8                 4         |         9                 7                 3         |
|         1                 7                 9         |         3                 2                 6         |         8                 4                 5         |
-------------------------------------------------------------------------------------------------------------------------------------------------------------------------
|         8                 4                 5         |         2                 1                 9         |         3                 6                 7         |
|         9                 1                 3         |         7                 6                 8         |         5                 2                 4         |
|         6                 2                 7         |         4                 3                 5         |         1                 9                 8         |
-------------------------------------------------------------------------------------------------------------------------------------------------------------------------
Time taken to solve the game: 0.753544 seconds.

Feel free to create your own input files and try it out, although it may not be 100% error free. Use at your own risk.



References
Cplusplus.com