Homework 11: Sudoku Solver
Milestone 1 Due: Mon. 18 April 2011 at 9:59:59 am
Milestone 2 Due: Friday 16 22 April 2010 2011 at 9:59:59 am
...
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 9*9 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 * 9 puzzle grid can be seen as divided into 9 sub-grids of size 3*33x3. 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 3x3 sub-puzzles
Sudoku Sudoku is not limited to 9x9 boards. An "order" for a Sudoku puzzle can be defined, and thus a Sudoku puzzle is an order^2 order
2
x order^2order
2
matrix. A regular Sudoku puzzle is this order = 3
. The above rules can be generalized to any order. This is Rice, so our system should be able to handle any order of Sudoku puzzle.
...
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! (You only have to find one solution, if one exists however, not all solutions.)
Supporting Code Download
The support code provided contains a DrJava project and , some sample puzzle boards and a few simple Junit teststest. The code download is coming "Real Soon Now" ...
Download the code here: HW11.zip
Full Javadocs are available in the supplied code in the docs
folder. Simply open the index.html
file in your browser.
...
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
order*order
2
cells, e.g. fororder
= 3, each row, column and block has 9 cells. - Each board has exactly
order*order
rows2
rows, columns and blocks.
- Each row, column and block has exactly
- 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
order
^2
sub-matrix of blocks if one were to display the rows, columns and blocks where each cell is only shown once.
- No rows share the same cell. Likewise, no columns or blocks share cells. This forces the square matrix layout of rows, columns, and
- The rules of Sudoku stipluate that the value in any given cell has very specific constraints:
- unmigrated-wiki-markup
- The valid values are {{
1...order
*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.
- The valid values are {{
...
A "board" is therefore a set of three {{Vector<ICellSet>}}s 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!
...
See the code details wiki page for explanations of the return types of the reduction and solving methods of GameModel
.
Supporting Code Details (click to go to next wiki page)
Running the Application
Starting the program:
...
- .In DrJava, right-click the {{
GeneratePuzzleApp
} class and select "Run File" to start the utility. - Select a file from the drop-list (yes,
4,txt
is missing--broken link on the download page). The higher the number, the harder the puzzles. - Each file contains about 10,000 puzzles. Use the number spinner to choose or type a puzzle number from 1-10,000 (approx.). Specifying "0" as the index will cause the utility to randomly select a puzzle.
- Click the
Generate
button and the puzzle will appear in the main display area of the utility. - Click the
Save
button to save the generated puzzle in a format that the Sudoku solver application can now read.
...
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
...
This will update the view with the mutated board. (Note that the {IViewAdapter.setCellViews()
}} wants the cells in the format of the blocks, not the rows, because that's how the screen is laid out.)
...
Define your variable as a one-element array.
For instance: {{ Wiki Markup
Code Block |
---|
final int |
...
[ |
...
] x = new int |
...
[ |
...
] |
...
{0 |
...
}; |
...
final ICell |
...
[ |
...
] aCell = new ICell |
...
[ |
...
] |
...
{ new Cell() |
...
}; |
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\]}} Wiki Markup
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.
...
- Keep references to BOTH the original board and the cell you found.
- Get an array copy of the values in the cell.
Cell.getValueArray()
makes a copy. You can use this array to loop over. - In your loop:
- Clear the contents of the cell. This will mutate your original board!
- Set the value of the cell to the desired test value.
- Make a copy of the orignal board.
- Solve the copy of the board -- you will need to set the current board to the copy. Don't mess up the original board!
- 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)solveIrreducibleBoard
(20 pts)solve
- full solution (20 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)
You are also required to have complete unit tests for the above You are also required to have complete unit tests of those methods. (15 pts)
Javadocs are already complete in the supplied code. If you add any fields, methods or classes, complete Javadocs will be expected for them. It is suggested that you do some level of Javadocs for your anonymous inner classes, if only to help keep things straight in your own head.your own head.
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:
- Instantiate a
GameModel
using the supplied dummyIViewAdapter
object. - Load a test output puzzle into the model and then save a reference to model's current board -- this is your reference output board
- Load a test input puzzle into the model.
- Run your desired operation.
- Get a reference to the model's current board -- this is the test output board.
- Use
assertEquals
to compare the output board to the reference board.
It is highly recommended that you start testing with 2x2 boards. Carefully construct SIMPLE boards that will test just the feature in question.
After you are satisfied with your tests on 2x2 boards THEN move on to 3x3 boards. Note: testing irreducible boards with choices that lead to unsolvable boards may be impossible on a 2x2 board.
The supplied code does NOT contain a full suite of test boards! Milestone 1:
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, to enable the user to generate and solve any of the 50,000 supplied puzzles. 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.