Homework 11: Sudoku Solver

Due: Friday 17 16 April 2010 at 119:59:59 pmam

The Sudoku Game

Sudoku is a 9*9 grid-based puzzle in which the goal is to place numbers from 1 to 9 in the grid squares taking into account specific constraints. The 9 * 9 puzzle grid can be seen as divided into 9 sub-grids of size 3*3. The 3 main conditions in the classic version of Sudoku state are that each square in the grid contains a number from 1 to 9 and a number cannot be repeated:

• In any line
• In any column
• In any on the k3*k 3 sub-puzzles

For more information of the game of Sudoku, visit: http://en.wikipedia.org/wiki/Sudoku

...

The support code provided contains a DrJava project and a few simple Junit tests. Download the code from here.

Your assignment is to implement:

• the method findSolution in the PartialSolution class.
• at least 5 more tests (3 for findSolution, 1 for isDeadEnd, 1 for isFinal).

Extra credit

For extra credit, improve the implementation of setElement and/or findSolution as you see fit, in order to improve the performance of the algorithms by examining fewer PartialSolution's. The improvement will be quantified by seeing if there is a decrease in the count of partial solutions in order to solve a puzzle (the count of partial solutions is returned by the getIntermediateSolutions() function of the PartialSolution class ).

Restriction: Keep using the setElement method in findSolution and do not change the contract of the setElement or findSolution methods.

Submission

Submit via Owlspace a .zip file containing all the files from the support code including those that you modified. Don't forget to add as header to the PartialSolution class, your names and ids.