University of Utah School of Computing
EAE 2420:
Introduction to Computer Science II
Homework 4
Assigned: Friday, Sep 19, 2014
Due: Mon, Sep 29, 2014, at 3pm.

Homework 4

Part I: Write a program to solve sudoku puzzles

(This assignment is based on one given by Peter Jensen in the Spring 2009 CS2420.) Sudoku puzzles are quite simple: Given a 9x9 square of numbers and spaces, fill in the empty spaces with numbers 1..9 such that every row contains no duplicates, every column contains no duplicates, and every 3x3 sub-square contains no duplicates.  This means that each row, column, and 3x3 sub-square will contain exactly one of each number 1..9.  Here is an example puzzle:

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

To solve this puzzle, note that the middle 3x3 sub-square on the top row does not currently have a 7 in it, but it needs one.  Notice that the only place for the 7 in this sub-square is the middle square in the top row.  If it is put in any other position in another row, it would duplicate a 7 for that row.  Using logic similar to this, the entire puzzle can be solved.

Fortunately, writing a program to solve Sudoku puzzles can be done using brute force, no convoluted logic is required.  Simply test the numbers 1..9 one at a time in the first square to see if they are allowed.  If so, put that number in the square, and proceed to the next empty square.  Repeat (recursively).  If you make it to the end, you've solved the puzzle!  If you encounter a square with no legal moves, back up to the previous square and try a different number for that square.  If no other numbers work there, back up to its previous square and try a different number.  This is backtracking, and its what you must use to solve this assignment.

Write a Sudoko solver using backtracking.  Specifically, the application should do the following:

  1. The application should take a filename as a command line argument and read a Sudoku puzzle from that file.  Here are a few sample files you can use:

    puzzle1.txt (easy for a human)
    puzzle2.txt (hard for a human)

    Each file has one non-blank character per puzzle location.  Any non-blank character other than a digit 1..9 represents an empty space in the puzzle.  Each non-blank character is separated from the others by at least one space.

  2. The application should print or display the original puzzle for the user.  You may do this in any way you like.  You may use the console or a GUI based application. 

  3. The application should solve the puzzle using backtracking only.  Your code must make use of recursion and backtracking, and your program should count the number of backtracking steps that it makes.  (A backtracking step is defined as removing an incorrect value from the puzzle.)

  4. The application should print or display the solved puzzle for the user.  Again, you may do this any way you like.  You should also display the number of backtracking steps that it took to find this solution.
You are free to be creative in your programming of this application.  Make sure to think about your design and comment your code, as a significant number of points will be awarded based on the quality of your code and comments. 

Here is the output from my solution when run on the second test case above: 

Unsolved: 
 
  6 8 .   . . .   . 5 .  
  . . .   . . 5   . . .  
  . . 3   8 . .   2 6 .  
 
  1 . 7   . 2 .   . . .  
  . . 9   5 . 8   6 . .  
  . . .   . 1 .   7 . 2  
 
  . 2 1   . . 9   4 . .  
  . . .   4 . .   . . .  
  . 3 .   . . .   . 2 8  
 
 
Solved: 
 
  6 8 2   7 9 3   1 5 4  
  7 1 4   2 6 5   8 9 3  
  5 9 3   8 4 1   2 6 7  
 
  1 6 7   3 2 4   5 8 9  
  2 4 9   5 7 8   6 3 1  
  3 5 8   9 1 6   7 4 2  
 
  8 2 1   6 3 9   4 7 5  
  9 7 5   4 8 2   3 1 6  
  4 3 6   1 5 7   9 2 8  

Number of backtracking steps: 14512
This demonstrates an adequate user interface and solution.  Good luck, and have fun with this assignment!

Part II: Written Homework

What to hand in

Create a web page for the assignment. Add a description of your program and some input and output puzzles. Use the CADE online handin system to handin your source code. Please zip and handin your entire project directory (including an info.txt file). If you work in a team only one of you need to submit the source code, but both need to make web pages.

Grading

Each homework assignment will receive a grade out of 100 points. This week, the available points will be broken down like so:
  • 55 points: Sudoku Solver
  • 10 points: Comments describing the class, each method as well as the interesting pieces of the code itself
  • 10 points: Elegence of programming
  • 10 points: Picture and web page
  • 15 points: Written Homework

Hints:

You do not have to code your solution exactly the way I coded mine.  I encourage you to stop reading now and give it a try.  If you get stuck, you can always come back to these hints.

OK, I warned you - my strategy may not be the best, and you'll learn more by doing this on your own.  ;)

The main application:

I represented the Sudoku puzzle using a Sudoku class.  This made writing the application easy.  After reading a filename fromt he command line, I simply created a Sudoku object.  The constructor was responsible for reading the file data into a two-dimensional array.

Then, the application simply printed out the object.  The Sudoku object's toString method prepared a String representation for the entire puzzle, and I printed that out with the "Unsolved:" message in my application.

I called 'solve' in my Sudoku object from the main application. 

I then printed out the puzzle again, and I made a call to a getBacktrackingCount method in the object to get the number of backtracking steps.

In total, my main application was only about 15 lines of code.

The Sudoku class:

My Sudoku class only had a small handful of methods and variables.  You should be able to figure most of these out.  The only tricky one is the recursive backtracking method.

To write it, consider the following:  Assume that you will fill in the squares in a particular order.  You will move left-to-right, and then top-to-bottom.  So, you will fill in the first row before proceeding to the second.  This means that if your program is currently working on filling in a square at location (r, c), then all the squares above this row r are already filled in, and all the squares to the left of this column c are already filled in.

By making this assumption, then we can write a recursive routine.  To solve the puzzle, place a valid number in the current square at (r, c), and then use the same method recursively to solve the puzzle at the next square.  If you reach a position after the end of the puzzle, then the entire puzzle is solved!  (Return something indicating that it was solved.)  If you reach a square that you cannot put a valid number into, then the current solution is impossible.  (Return something indicating that it was not solved.)

In your code, you try a number in the current square and then recursively solve the puzzle from the next square.  (You will have to figure out a way to make the recursive call advance to the next square.)  If from this square the puzzle is solved, you should also return something indicating the puzzle was solved.  If not, you should remove the value you placed in this square and try another value.  If no other value will fit, return something indicating that it was not solved.

That's the goal.  It is useful to write a helper method to determine if you can legally place a particular value in a particular square.  Also, you only need one loop in your recursive method - the loop that tries the values 1..9 in the current square.  Finally, make sure your recursive method does not try to store row and column indices in instance variables.  You should be recursing on these values, they should be parameters.