Homework 11: Sudoku Solver

Due: Friday 16 April 2010 at 9:59:59 am

 Under Construction!   The game architecture is being completely redone from last year's code.   Please read the following only as general guidance.   The instructions and descriptions will be changed very soon...

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 3*3 sub-puzzles

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

Need to practice your Sudoku-playing skills?    There are lots of on-line games.   Here's one: http://www.websudoku.com/

A Sudoku puzzle as needed for this assignment may not be well formed and in general may have no solutions or multiple solutions.   Your solution must be able to handle these situations!

The assignment

The purpose of this assignment is to build a Java solver that finds all of the different solutions of the game using a constraint-based approach.

In a constraint-based approach, each square is viewed as a variable that can take on multiple values from a given set. A partial (intermediate) solution is one in which at least one variable has more than one possible value. A final solution is one which each variable has exactly one value (all the sets are singletons).

The required solution (built on the basis of the support code provided) should work as follows. At each step, the program will evaluate a partial solution. Initially, this partial solution corresponds to the input Sudoku puzzle (a 9*9 matrix that is partially filled) in which the values of some squares are known and others are unknown.

Modeling Sudoku

To find all solutions for a partial solution, we have to keep track of all the possible values for each square in the grid. Each square is modeled by an interface, ICell.

In general, there are many ways to model a system.   Naively, we could simply model the Sudoku board as a NxN square matrix of cells.   We could certainly build our system this way and there might even be some advantages to doing so, e.g all out speed if one does a lot of optimization since the underlying processor architecture is optimized for arrays.

But one of the main tenets of modeling is that one's model of a system should should capture and clearly express the salient characteristics of the system.     Sudoku is more than a dumb square grid of numbers.   Here are some Sudoku-specific features:

• An empty board is fully determined by a single value, it's "order", which for a 9x9 board is 3.
• The board is viewable in terms of rows, columns and blocks.
  • Each row, column and block has exactly order*order cells, e.g. for order = 3, each row, column and block has 9 cells.
  • Each board has exactly order*order rows, columns and blocks.
• Each cell is a member of exactly one row, one column and one block.
  • No rows share the same cell.   Likewise, no columns or blocks share cells.  This forces the square matrix layout  of rows, columns, and orderxorder sub-matrix of blocks if one were to display the rows, columns and blocks where each cell is only shown once.
• The rules of Sudoku stipluate that the value in any given cell has very specific constraints:

  • The valid values are 1...order*order (inclusive), e.g. for order=2, the allowed values are [1, 2, 3, 4]

  •  Any valid value in a cell cannot appear in another cell in the row, column or block to which that cell belongs.   Conversely, each row, column or block must contain every valid value exactly once.

Notice how rows, columns and blocks are "homomorphic", that is they are exactly the same abstractly and structurally in the above feature descriptions.   Nowhere does it say that rows are horizontal, or columns are vertical or that the blocks are arranged in a square sub-matrix -- that's strictly a result of trying to display each cells only once in our visual representation of the board.

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

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 

Your assignment is to implement:

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. 

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.