...

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.

...

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:

  • Wiki Markup
    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.  

(In the support class, the Sudoku grid is modeled by an array of Rows. The Row class contains an ArrayList of HashSets, one HashSet of Integers for each square from that row. The HashSet contains possible values for the square.

...