CS 261 Homework 4 - Sudoku Solver

Due Fri Mar 15 at 5:00pm

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 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 and then will solve each one in turn, printing the puzzle and the output.

Moreover, in order to help you practice writing recursive programs, program should contain no 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.

Objectives

Necessary Files

You will want a copy of the Hwk4.zip file which contains the README for this assignment, as well as 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 (though it may take a tad longer for the hard puzzles!)

Details

  1. 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 in a possibly order, though you do not need to follow these suggestions. Make sure you complete and thoroughly test each step (unit testing) before you move on to the next!
  2. The first thing you should do is write a method to read and parse a text file with a single puzzle (e.g., the sudoku_wiki file). You can use a loop for now--the goal is to get some data into your program that you can work with. Parsing data files should be old-hat by now; review your Shape Decomposer and the Movie Library to get you started!
    • Think about what kind of data structure you will want to use to store a Sudoku puzzle. What kind of data structure would you need to use to store multiple Sudoku puzzles?
    • Make sure that you're reading the file correctly before you continue! Can you print out the puzzle once you've read it?
  3. Write a method to recursively print out the puzzle you have read in. Follow the recipes in the book: remember to include a stopping condition and a recursing condition.
    • Hint: you'd normally use a nested loop, 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 the rows.
    • Yes, you should include the border to segment off the squares--this helps with checking that the puzzle is solved correctly!
    • This is a good target for Wed Mar 06.
  4. In order to solve the puzzle, you'll need to know whether you can place a 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 the weekend of Mar 08.
  5. Write a recursive backtracking method that solves the sudoku puzzle. This method will try and place a number in the puzzle, try to solve the rest of the puzzle, and if it fails remove that number and try again. We will talk about how to write backtracking algorithms in class.
    • Like recursion itself, this method is both simple and complex. Effectively 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).
    • Make sure to include your stopping condition!
    • Test this method thoroughly. The Eclipse Debugger can be helpful here, as it will let you see what your puzzle looks like at any given point in the algorithm. 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 13.
  6. Now that you are able to solve a puzzle and should be feeling good about recursion, add a recursive method that will solve all of the puzzles that you parsed from the file. This is simpler than it sounds.
  7. Finally, go back to your file parsing code and replace the loops with recursive methods, so that your entire program works recursively.
    • Again, since you normally have a kind of nested loop, you will likey want to make a helper method that recursively reads through each line. You may also want a separate method that recursively reads each puzzle in the file
    • This functionality, along with the rest of your program, should be completed by Fri Mar 15
  8. Some notes about style:
    • Using appropriate variable and method names can help you keep track of what is going on with each method
    • 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.
    • 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.
  9. Be sure to complete the README.txt that you found in the Hwk3.zip file, and upload it along with your code!

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!

Submit your program to the Hwk4 submission folder on hedwig, following the instructions detailed in Lab A. You should upload all you classes, as well as the README.txt. Also include any extra puzzle files you used.

The homework is due at 5pm on Fri Mar 15.

Extensions

Grading

This assignment will be graded based on approximately the following criteria: