...

What does this all mean?   ==> Rows, columns and blocks can all be represented with the same data structure!   We will use the interface ICellSet to represent the set of cells corresponding to a particular row, column or block.    There is also the implication that each cell "knows" which specific row, column and block to which it belongs, so each ICell has a set (vector) of ICellSets that correspond to the row, column and block to which that cell belongs (in that order).  

A "board" is therefore a set of three {{Vector<ICellSet>}}s representing the rows, columns and blocks of the board.   Note that any given cell will appear once in the rows, once in the columns and once in the blocks.   The data structures that we have created enable us to access the cells in multiple methods that clearly represent the cell relationships in the manner that best models the problem at hand, namely the Sudoku board.   We can easily and consistently see the cells in terms of rows or columns or blocks in a manner that is abstractly equivalent, enabling us to easily reuse the same code to process the cells in any direction we choose.   Compare this to a standard NxN matrix representation (a collection of rows) which represents only a single cell relationship feature, namely that they are in rows.   Luckily, accessing the cells in terms of columns is not too difficult, but accessing them in terms of blocks is a bear!

Solving Sudoku

The fundamental principle of Sudoku is that any given row, column or block must contain all integers from 1 to order*order inclusive, exactly once.   

In the beginning, a Sudoku board is defined by particular cells already being solved (i.e. have a single value in them) and all the rest being unsolved (i.e. have all possible values in them).   We can think of an unsolved cell as containing all possible guesses for the value at that moment, which at the beginning, is all possible values.  

Thus the simplest reduction process is to look at the set of all values from the solved cells in the row, column and block to which a cell belongs and eliminating those values from the current set of value choices for that cell.  (Hint:  HashSet<T>.removeAll() does exactly what you want!)   To reduce a cell set is to reduce every cell in that cell set.  To reduce a board is to reduce every cell in any collection of cell sets -- do you need to reduce every collection of cell sets?   

Requirement:  the reduction process for a cell set and for a board should be able to detect if the cell set or board is

• Irreducible - the reduction pass did not change any values.
• Solved - all the cells were solved already or became solved
• Unsolvable - a cell somewhere has or ends up having no value choices left, i.e. and empty HashSet of values. 
• Reducible - a change to the number of values for a cell somewhere occurred. 

Irreducible Sudoku boards ARE potentially solvable

You should first get a simple reduction pass working.   But once that is operational, you can tackle how to deal with irreducible boards.   An irreducible board means that, at least    To solve an irreducible board,

To find final solutions from a partial solution, one should look for a square with multiple possible values, generate the different partial solutions by specifying that the square contains one of the values (and impose the restrictions specified by the rules of Sudoku on the content of the other squares), and then recurse for each of these possible solutions until no square has more than one possible value. If square becomes empty, then it will not lead to a final solution. If all squares have exactly one value, then we have a final solution.

The support code provided contains a DrJava project and a few simple Junit tests.  The code download is coming "Real Soon Now" ...

Supporting Code Details 

Programming Tips

Mutating a value outside of an anonymous inner class

Controlling a loop from inside of an anonymous inner class

How to make copies of a board when you don't know which cell is the one you want to guess from

Your assignment is to implement:

Testing!

Extra credit

Incorporate the supplied GeneratePuzzle utility capability into the main Sudoku solve, both in the view and the model, to enable the user to generate and solve any of the 50,000 supplied puzzles. 

As any seasoned Sudoku player knows, there are other reduction rubrics that can be applied to more quickly reduce a board.   For instance, if an unsolved cell includes a value choice that no other unsolved cell in its cell contains, then the cell must have that value (this can be extended to a sub-set of values spread across multiple cells in a cell set).    Can you incorporate additional reduction rubrics in a modular, flexible and extensible fashion?

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 GameModel class, your names and ids.