CS 261 Homework 5 - Sudoku Solver

Due Mon Nov 03 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 From Wikipedia
+-------+-------+-------+
| 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

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.

Additionally, 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 sure 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!

  1. Your first step should be to create an ADT (e.g., SudokuPuzzle) to represent a single sudoku puzzle that can be solved. Much of your logic will go in this class.
    • I recommend you store the data as a sudoku puzzle using an int[][]; that will give you quick and easy access to any particular entry in the puzzle.
    • Useful tip! Make a note about whether you will access items in your array as array[col][row] or array[row][col]. Since puzzles are square either one is fine, but you'll want to make sure you are consistent.
  2. You will need to have a way to load a file into a Sudoku puzzle. I recommend you make some prototyping code that iteratively reads a file and parses it into the puzzle; this will let you get something working without needing to worry about recursive file parsing (which can get a bit tricky; see below).
    • Since thise code will contain forbidden loops, you will need to eventually throw it away. That is okay! We often write up sample code to test a concept or act as a placeholder, even if it isn't used in our final project. You should become willing to discard old code when necessary.
    • Note that you are allowed to use built-in methods that use iteration. For example, the String.split() method can be very useful for breaking apart each row into individual numbers.
  3. 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 all the rows (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!
    • Note that having loaded and printed a puzzle is a good target for Fri Oct 24.
  4. 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 sub-grid or "box". Try writing three different helper methods that check these three conditions, and then calling all of them from a main "is valid" method
    • Checking the "box" can be tricky. You might think about the box as being a set of "short" (length 3) rows, and then simply using the same method that you use to check if an entry can be put in any of the rows! The number will only be valid if all of the "subrows" are valid.
      • And you can of course recursively loop through the subrows ;) Do not hard-code assumptions about the puzzle size!
    • Major style tip! This functionality is where the importance of good method names and detailed JavaDoc comments can pay off in spades.
      • Name your methods so that they explain clearly what they do. checkRow doesn't tell us anything about how to use the method; canPlaceInRow on the other hand makes it very clear how the method will be used!
      • Write out the JavaDoc for your method before you fill in the details of the method. Note what the parameters and the return value represent before you write any code--that way you'll have it very clearly documented what any row parameter represents!
    • Be sure to test your code thoroughly--this is an easy place to make a mistake! You should actually do this! Include a main method in the class with code that demonstrates that your methods work (remember: print the expected and actual output of the method!).
    • This functionality is a good target for Mon Oct 27.
  5. 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 Fri Oct 31.
  6. Now that you are able to solve a puzzle and should be feeling good about recursion, You will need to add functionality to recursively parse and solve all of the puzzles from a file. This is simpler than it sounds.
    • Create a new ADT (e.g., SudokuSolver) that can represent the collection of solveable puzzles.
    • Having one method that loads all the puzzles into a data structure (think: what kind of datastructure would be good for representing lots of puzzles?), then a separate method that recursively calls "solve" on each of those puzzles can help keep things from being overwhelming.
  7. The hardest part of this is being able to parse a file recursively. The trick is to create a single Scanner on the file, and then pass that object as a parameter to your recursive methods. Since the Scanner remembers which line it is currently on, you can simply advance it one line when you need to, and all your methods will be able to work off the same file.
    • Start by being able to parse a file with a single puzzle (like your temporary code). Go to that code and replace the loops with recursive methods. 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.
    • Once you have a method that can parse a single puzzle, recursively call that method (passing in the same Scanner) to parse all the puzzles!
    • This functionality, along with the rest of your program, should be completed by Mon Nov 03
  8. Be sure to complete the README.txt that you found in the Hwk5.zip file, and upload it along with your code!

Some helpful notes about style

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 vhedwig. 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 Monday, Nov 03.

Extensions

Grading

This assignment will be graded on approximately the following criteria:

This assignment will be graded out of 30 points. Note no credit will be given for programs that utilize for or while loops.