Recursion: Sudoku

CS 206 - Introduction to Data Structures

HW 7

Recursion: Sudoku

Due: ????

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.

Recursive Backtracking solution

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 go 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 humann-like solution approaches. Howerver your solution must use recursion with backtracking.

Sugestions for coding

Please note that this are only suggestions. You can approach the problem in any way. That said, I would suggest starting as follows:

Write the system for reading in the board fix. Use iteration (for and while loops).
Write the copy method for puzzles. This could be written later but it should be easy so get it done.Use iteration
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?)
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.Use iteration
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.
Write the isSolved. This should be really easy.Again, use iteration.
Write solve
When the solver works 100% of the time, go back through you code and remove iteration.

Data

Sudoku puzzles for this assignment will be in CSV files similar to the following

	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).

Some rules:

You may use iteration to read the csv file as in the pseudocode above. You should not use iteration otherwise. As an incentive to avoid other iteration, each use of iteration will be penalized on a sliding scale. The first use, -1 point; the second -2 points; etc. This count is applied at the code, not at runtime. So, if you have 4 uses of iteration in your code, then you loose 10 points (1+2+3+4). To avoid loosing points you may do some pretty silly seeming recursions. So be it.
When your program has reached a solution, it should print that solution.
Use an appropriate set of data structures and classes. You may use data structure inplementations provided by Java or those discussed in class.
Command line input. The puzzle file must be given (or givable) on the command line For instance, if the main method is the class Solver, then
```
				java Solver puzzle.csv
			
```
Exception handling. Your program should not die; under any circumstances. It should gracefully handle at least the following issues:
- What happens when the puzzle file is missing
- What happens when the puzzle file is corrupt.
The only exception you need not handle is a stack overflow. You really should not get a stack overflow, and you cannot handle it gracefully anyway.
Extra credit: Implement a smater strategy for solving than the one I outlined, where smart takes the form of making fewer recursive calls (and generally having a faster runtime). Show that your solution is smarter by counting the number of recursive calls.

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.

README: This file should follow the format of this sample README (https://cs.brynmawr.edu/cs206/README.txt)
Source files: Every .java file used in the final version of every part of your project (including the imported files)
Unique Data files used: This is expected to be blank as the only data files you should use are as above. However, you could use a data file (or two) as a part of your test driver class (I do not recommend this, I simply note that you could).

DO NOT INCLUDE:

Data files that are read from the class site.

The following steps for submission assume you created a folder named AssignmentN in the directory /home/YOU/cs206/ and that folder contains all of your code.

For this assignment N=5
Put the README file into the project directory (/home/YOU/cs206/AssignmentN)
In the README, include all of the data requested above for Jen and Jill and a brief discussion of the data (answering at least the two posed questions).
Go to the directory /home/YOU/cs206
Enter submit -c 206 -p N -d AssignmentN

For more on using the submit script click here