CS 206 - Introduction to Data Structures

Recursion to solve Sudoku

Due April 11 prior to 11:59:59 pm EDT

Alternatives

Sudoku is the main and default assignment. If, however, you just do not want to deal with sudoku, there is an alternative which is described at the end of the assignment. I urge you to do the sudoku assignment, but both are worth equal credit.

Sudoku

Sudoku is a game / logic puzzle with a simple set of rules. This assignment is to write a recursive sudoku solver. If you are unfamiliar with sudoku you should learn the rules and solve a couple of puzzles before starting. Puzzles are available on sudoku.com. I prefer the interface on the New York Times website.

A recursive backtracking Sudoku solver

There are many approaches to solving Sudoku puzzles. I describe one here, you need not follow my exact approach. Here is pseudocode for my approach: 
Puzzle 
    //at its simplest this could be just a 2d array (specifically 9x9) of int

boolean isSolved(Puzzle p)
    return true if the puzzle is completely solved false otherwise

boolean isSolvable(Puzzle p)
    return true if the puzzle still might be solvalble, false otherwise

List legalmovesat(Puzzle p, int xloc, int yloc)
    return the list of numbers the can be legally put into the position given the board

Puzzle copy(Puzzle p)
    return a new instance of puzzle that is an exact copy of the provided puzzle.  Importantly, making a change in the copy should have no effect on the original. 

Puzzle solve(Puzzle p, int xloc, int yloc)
    if isSolved(p)
        return p
    if not isSolvable(p)
        return null 
    if (yloc>9)
        xloc++
        yloc=0
    if (xloc>9)
        return null
    if (p(xloc, yloc) != 0)
        return solve(p, xloc, yloc+1)
    else
        legalmoves = legalmovesat(p, xloc, yloc)
        foreach legalmove : legalmoves
            set p(xloc, yloc) to legalmove
            np = solve(copy(p), xloc, yloc+1)
            if (np!=null)
                return np
        return null
Generally, this approach starts in one corner of the puzzle and fills in a legal guess, then recursively goes to the next square, backtracking when it gets to points in which the puzzle cannot be solved. Note that while this approach can certainly be used by humans to solve sudoku puzzles, it is not the way that any reasonable person would. You are free to implement other, more human-like solution approaches. Whatever your approach, your solution must use recursion with backtracking.

Suggestions for coding

Please note that these are only suggestions. You can approach the problem in any way. That said, I would suggest starting as follows:
  1. Write the system for reading in the board first. Use iteration (for and while loops).
  2. Write the copy method for puzzles. This could be written later but it should be easy so get it done. Use iteration.
  3. Consider rewriting the read and copy methods to be purely recursive. (This could be done much later, but recursion is fun, so why not do it now?) (See the requirements section below)
  4. Write the "legalmovesat" method. This should be, by far the most complex piece of code you write for this assignment. Use iteration. Make sure that this is perfectly correct before doing anything else. If it is not prefect, the rest of the program will fail. Consider breaking down the problem as follows: first create a utility function boolean isLegal(int number, int row, int column)Within that utility function first check if the number is legal "vertically". Then check if it is legal horizontally, then finally check it it is legal within inits 3x3 group. I suggest writing bothin of these functions so they can be testable directly. For instance, in a main function, read in a board. Then call isLegal on some number and some position. You should be able to check that the answer to this is correct by hand. Once you have isLegal written, then legalMovesAt is just a loop from 1 to 9 calling "is legal move". Again, check this by directly calling it from your main function.
  5. Write the isSolvable method. This can be written by just making calls to legalmovesat from every square that is not filled in. If you find a square for which legalmovesat returns a zero length list, then the puzzle is not solvable. (There are many other ways to write is solvable, this is probably the easiest.) Again, use iteration.
  6. Write the isSolved. This should be really easy. just check is every square is filled. Again, use iteration.
  7. Write solve
  8. When the solver works 100% of the time, consider going back through you code and remove or at least recuce the use of, iteration.

Data

	0,0,0,2,0,0,0,0,0
	0,0,0,5,9,0,3,0,7
	0,0,0,0,0,0,6,9,0
	0,0,0,0,0,8,0,0,0
	0,1,9,0,0,0,0,8,3
	0,0,4,0,6,0,0,0,0
	3,0,0,0,2,0,7,0,1
	0,5,7,0,0,4,0,0,0
	0,8,0,0,3,0,0,0,0
Zeros (0) in this file represent blanks (unknowns) in the puzzle, they are the spaces your program needs to fill in. In the directory /home/gtowell/Public/206/a7/ are several puzzles (*.csv) of differing levels of difficulty. All are solvable. All have solutions in files (*.csv.soln).

Requirements (ish)

Alternative assignment

From the Goodrich textbook, do the following problems:

Electronic Submissions

Your program will be graded based on how it runs on the department’s Linux server, not how it runs on your computer. The submission should include the following items:

The following steps for submission assume that you created a project named AssignmentN in the directory /home/YOU/cs206/

  1. For this assignment N=7
  2. Put the README file into the project directory
  3. Go to the directory /home/YOU/cs206
  4. Enter /home/gtowell/bin/submit -c 206 -p N -d AssignmentN

For more on using the submit script click here