CS 261 Homework 5 - Sudoku Solver

Due Fri Mar 14 at 11:59pm

Overview

Sudoku is a popular puzzle game in which the player tries to fill a 9x9 grid of numbers with the digits 1 through 9, so that a digit occurs only once in each row, each column, and each 3x3 sub-grid. In this assignment, you will be writing a program that can solve an arbitrary Sudoku puzzle using a brute-force, recursive backtracking algorithm. Solutions will be displayed on the command-line, so that your program's output should look like this (puzzle from Wikipedia):

Solving Puzzle #1
+-------+-------+-------+
| 5 3 . | . 7 . | . . . |
| 6 . . | 1 9 5 | . . . |
| . 9 8 | . . . | . 6 . |
+-------+-------+-------+
| 8 . . | . 6 . | . . 3 |
| 4 . . | 8 . 3 | . . 1 |
| 7 . . | . 2 . | . . 6 |
+-------+-------+-------+
| . 6 . | . . . | 2 8 . |
| . . . | 4 1 9 | . . 5 |
| . . . | . 8 . | . 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 |
+-------+-------+-------+

Your program will read in a text file that contains a list of puzzles (yes, more than one) and then will solve each in turn, printing the puzzles and their solutions.

Moreover, in order to help you practice writing recursive programs, your program must not contain any iteration: no for or while loops are allowed! You are welcome to use iterative loops to test and debug your program (or to temporarily fill in functionality)---however, these loops must all be excised from your final submitted program.

This assignment should be completed individually. You are welcome to ask for help from me, or from your classmates (but remember to follow the Gilligan's Island rule)!

Objectives

To practice writing recursive methods
To practice writing backtracking algorithms

Necessary Files

You will want a copy of the Hwk5.zip file which contains text files of Sudoku puzzles that you should use in writing your program.

Each puzzle is formatted as ten lines of text: a line with a label (which separates the puzzles), then 9 lines of 9 comma-separated integers that represents the puzzle--blank spots in the puzzle are represented with 0s. There are three included puzzle files: sudoku_wiki.txt that contains the Wikipedia puzzle displayed above, sudoko_easy.txt that contains 50 "easy" puzzles, and sudoku_hard.txt that contains 95 "hard" puzzles. Your program should be able to solve all the puzzles in these files (though it may take a tad longer for the hard puzzles!)

The zip file also contains a class SudokuFileParser.java, which contains an (iterative) method that you can use to parse a sudoku file. I'm providing this so you can dive right writing the solver; however, for your final submission you will need to rewrite this functionality to work recursively.

Finally, the zip file also contains the README.txt for this assignment, which you will need to fill out.

Assignment Details

Read through all of these instructions carefully before you begin! They detail the specifics of what you will need to implement to complete this assignment. They list steps you'll need to do, though you do not need to follow this particular order. Make you thoroughly testeach section of your program--this assignment lends itself to checking the functionality of each method before moving on, and making sure each piece works will help avoid more complicated bugs later!

Your first step will be to create a class (e.g., SudokuSolver) to get you started. Look over the provide SudokuFileParser, and make sure you can call that method and load a sudoku puzzle.
- Note that this file returns a sudoku puzzle represented using a 2d array of ints. You are of course welcome to modify the method if you feel a different data structure would be more effective. Consider: what kind of data structure would you need to use to store multiple sudoku files?
Write a method to recursively print out the puzzle you have read in. Follow the recipes in the textbook and that we discussed in class: remember to include a stopping condition and a recursing condition.
- Hint: you'd normally use a nested loop to print out a 2d array; therefore you'll need some kind of "nested" recursion. Consider writing two recursive methods: one that recursively prints a single row of numbers, and one that recursively prints each row (by calling the previous method).
- Yes, you should print the border to segment off the squares as in the example at the top of the page--this helps with checking that the puzzle is solved correctly!
- Being able to do this is a good target for Thur Mar 06.
In order to solve the puzzle, you'll need to know whether you can place a given number in a particular spot in the puzzle. Write a method that recursively determines this.
- Hint: A number can be invalid if it is already in the same row, the same column, or the same box. Try writing three different helper methods that check these three conditions.
- Be sure to test your code thoroughly--this is an easy place to make a mistake!
- This is a good target for Sun Mar 09.
Now the core of the assignment: write a recursive backtracking method that solves the sudoku puzzle.
- Backtracking can be tricky to get the hang of. The process works basically like this:
  1. try and solve the puzzle by placing a number.
  2. after placing the number try and recursively solve the rest of the puzzle (placing a number in the next spot)
  3. if that solved the puzzle, then report back that the puzzle is solved
  4. otherwise, remove that number because it didn't lead to a solution, and try to recursively solve the puzzle with the next number
  The key trick of backtracking is that each time you recusively "solve" the puzzle, you need to report back (return) whether or not the puzzle is solved. Basically your method will place a number, and then "delegate" to another method call to ask if everything else worked. If it did, then you won. But it it didn't, then you need to tell your boss (who delegated to you) that your number was bad. We'll go over this process more in class.
  
  Like recursion itself, backtracking is both simple and complex. Effectively you will have you will have two recursive conditions: one if the number does work (in which case you try to solve the rest of the puzzle), and one if the number does not work (in which case you may need to try another number).
- Test this method thoroughly. The Eclipse Debugger can be especially helpful here, as it will let you see what your puzzle looks like at any given point in the algorithm. Put a break point at the start of each method call, and inspect if the numbers placed in the puzzle are following the "brute force" strategy. (You can also print out the puzzle at every step, which can sometimes be easier than reading puzzle state from the debugger). You'll know when it works, because it will provide you with a completed puzzle!
- You should be sure to have this completed by Wed Mar 12.
Now that you are able to solve a puzzle and should be feeling good about recursion, add a recursive method that will parse and solve all of the puzzles from a file. This is simpler than it sounds.
- Having one method that loads all the puzzles into a data structure, then a separate method that solves those puzzles can help keep things from being overwhelming.
Finally, go back to the provided file parsing code and replace the loops with recursive methods, so that your entire program works recursively. This is a great exercise in adapting iterative methods into recursive ones!
- Again, since you normally have nested loop, you will likey want to make a helper method that recursively reads through each line.
- This functionality, along with the rest of your program, should be completed by Fri Mar 15
Be sure to complete the README.txt that you found in the Hwk5.zip file, and upload it along with your code!

Some notes about style

Using appropriate variable and method names can help you keep track of what is going on with each method. Methods will have a lot of parameters, so give them descriptive names so you remember which is which! It's easy to "refactor" to rename variables without needing to jump around in your program.
Use "launcher" or "wrapper" methods to start off your main recursive functions; this will help with readability.
Be careful about accessing instance variables directly: this can introduce bugs when using recursive methods (since each call may be accessing the field at the same time). Instead, you should pass information to subsequent recursive calls in the parameter to that method call. This is why recursive methods gain a lot of parameters!
Include copious comments about what each call does and when it does it to help you keep track of your program.
Also include full Javadoc comments for each method in your program.

Submitting

BEFORE YOU SUBMIT: make sure your code is fully documented and functional! If your code doesn't run, I can't give you credit! Your name should be in the class comment at the top of each class.

Submit your program to the Hwk5 submission folder on hedwig. Make sure you upload your work to the correct folder!. You should upload your entire src folder with all your classes. Be sure to complete the provided README.txt file with details about your program. Also include any extra puzzle files you found or used.

The homework is due at midnight on Friday, Mar 14. This is the Friday before Spring Break, so you may very well want to have it done earlier!

Extensions

Modify your program to print out all possible solutions to a Sudoku puzzle. I have not checked if any of the puzzles in the provided lists have multiple solutions; you may need to find examples of such puzzles online to test your program with
Modify your program so that it can also solve a 16x16 Sudoku puzzle. You will need to avoid hard-coding in the puzzle size (which you should avoid anyway--use a constant!), but otherwise your program will work exactly the same way. You can find puzzles to test with online.
Add functionality to generate Sudoku puzzles. There are a number of algorithms for this: one basic the basic idea is to place random numbers, and then check that the puzzle has a unique solution. If there isn't a solution, backtrack!
Of course, this solver can be used to support a program in which the player tries to solve a puzzle, and the program either tells them if they are correct or otherwise gives hints. Such an extension goes well beyond the scope of the assignment.

Grading

This assignment will be graded on approximately the following criteria:

Your program recursively prints a Sudoku puzzle [10%]
Your program recursively checks whether a number is valid in a particular spot [15%]
Your program uses recursive back-tracking to solve Sudoku puzzles [30%]
Your program recursively solves multiple puzzles [10%]
Your program recursively reads multiple Sudoku puzzles from a file [15%]
Program demonstrates clean recursive style, including the use of "launcher" methods [10%]
Program is fully documented with complete Javadoc comments [5%]
You have completed the included README.txt file [5%]