Sudoku

Sudoku is a popular puzzle where you fill in numbers on a grid, trying to keep certain conditions true. To learn more about how Sudoku works, check out http://www.sudoku.com. You'll find a sample puzzle and an explanation of the rules.

Write a program that reads a file containing an unfinished Sudoku puzzle, then uses recursion to solve it and display the results to the screen. The input should simply contain the numbers in the puzzle delimited by spaces on each line. For example, this puzzle:

Public domain puzzle obtained from Wikipedia Commons

would be represented in your input as:

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

5 3 4 | 6 7 8 | 9 1 2 
6 7 2 | 1 9 5 | 3 4 8 
1 9 8 | 3 4 2 | 5 6 7
------+-------+------ 
8 5 9 | 7 6 1 | 4 2 3 
4 2 6 | 8 5 3 | 7 9 1 
7 1 3 | 9 2 4 | 8 5 6 
------+-------+------ 
9 6 1 | 5 3 7 | 2 8 4 
2 8 7 | 4 1 9 | 6 3 5 
3 4 5 | 2 8 6 | 1 7 9

You should indicate the filename of the input through a command-line argument. In other words, running your program should look something like this:

python sudoku.py input1.txt

You can find documentation on how to handle command line arguments within this Python tutorial,

Hint

The code for solving the 8-queens puzzle that I provided in class should be of considerable assistance. It helps a lot if you structure your program like this one. Feel free to use this program as a starting point if you like. Cite it appropriately.

Developing your own code

This goes without saying, but I'll say it anyway. There are undoubtedly lots of examples of software on the Internet for solving Sudoku puzzles. Some of it might even be in Python. Develop your own. Using code that you find on the Internet is unethical, doesn't provide you with the learning opportunity that you get by developing this yourselves, and would result in charges by the College for academic dishonesty.

Optional extensions

Having fun and want to do more? Consider trying the following:

• Make your program work on Sudoku puzzles of larger size, such as a 16 x 16 version or a 25 x 25 version. How big can your program handle in reasonable amounts of time?
• Write a program to create Sudoku puzzles for others to solve. Any puzzles that you create should have just one unique solution.

Have fun!