Page History

...

Milestone 2 Due: Friday 22 April 2011 at 9:59:59 am 

Tip: Out of Memory Error 

    Try the following:  Go to Edit/Preferences/Micellaneous/JVMs and add the -Xss64M option to the "JVM Args for Interactions JVM" line to increase th amount of memory used.

The Sudoku Game

Sudoku is a 9x9 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 x 9 puzzle grid can be seen as divided into 9 sub-grids of size 3x3. 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:

...

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

...

• 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 order2 cells, e.g. for order = 3, each row, column and block has 9 cells.
  • Each board has exactly order2 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 order^2 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 MarkupThe valid values are {{1...order{}}}{{{}{^}2{^}}} (² (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.

...

Note:  Your Sudoku solver should be able to solve a completely blank puzzle (all dashes, not empty)!

Programming Tips

Updating the View

At the end of the reduceBoard and solve methods, be sure to add the line

...

 final int[] x = new int[]{0};

final ICell[] aCell = new ICell[]{ new Cell() }; 

Wiki Markup An anonymous inner class can thus access these variables by using the array syntax:   {{x\[0\]}} and {{aCell\[0\]}} An anonymous inner class can thus access these variables by using the array syntax:   x[0] and aCell[0]

You may find that in order to keep track of several properties as you loop through cells and cell sets, that you may need to create multiple one-element array values.

...

1. Keep references to BOTH the original board and the cell you found.
2. Get an array copy of the values in the cell.  Cell.getValueArray() makes a copy.  You can use this array to loop over.
3. In your loop:
   1. Clear the contents of the cell.  This will mutate your original board!
   2. Set the value of the cell to the desired test value.
   3. Make a copy of the orignal board.  
   4. Solve the copy of the board -- you will need to set the current board to the copy.   Don't mess up the original board!
   5. Repeat with the next test value if no solution or quit if you find a solution.

...

• Milestone 1
  • reduceCellSet (15 pts)
  • reduceBoard  (15 pts)
  • solve -- partical solution for easy puzzles that have no irredicible states. 
• Milestone 2
  • findMinChoiceCell (15 pts)  -- Be sure to describe what your heuristic is trying to do in some comments accompanying your code!   Simply picking the first or a random cell will NOT garner full credit!
  • solveIrreducibleBoard (20 pts)
  • solve - full solution (20 pts)

...

 Your code must work for ANY order puzzle!   (To within machine limits, of course.) 

Testing Procedures

...

The supplied code contains a simple test routine that gives you examples on how to instantiate a {{GameModel}}, {\[Board}} and test them.

It is reasonable to test your code by the following process:

...

The supplied code does NOT contain a full suite of test boards!  

 

Extra credit

If you are attempting an extra credit task, put a note to such at the top of your GameModel class. If you don't, the staff might not see it and grade it.

(10 pts) Incorporate the supplied GeneratePuzzle utility capability into the main Sudoku solvesolver, both in the view and the model, to enable the user to generate and solve any of the 50,000 supplied puzzles. .   Remember that the view and the model MUST be kept separate--the only way they can communicate is via IModelAdapter and IViewAdapter, their respective adapters.    Neither GameFrame nor GameModel may contain a reference to the other!      (It is actually possible to add this feature without modifying GameModel at all, though you are not required to do this.)

(10 pts) 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?

...

Submit via Owlspace a .zip file containing the entire HW11 folder, including all the support code and data.  Don't forget to add as header to the GameModel class, your names and idsIDs.   Be sure to mention if you did any extra credit tasks too.