Sudoku Applet Directions
Sudoku Applet Source
Sudoku Applet Issues
Sudoku Application Directions
Sudoku Application Source
Sudoku Pruning Algorithms
A Sudoku puzzle consists of an area divided into a 9-by-9 grid of squares that is further subdivided into 9 blocks each 3-by-3. To solve the puzzle, one must enter the digits from 1 to 9 in such a way that each row, each column, and each block contains the nine digits exactly once.
The puzzle constraints are quite clever because they may be used in opposite ways. On one hand, one can argue that a digit cannot appear in a row or column or block because it already appears there. On the other hand, as a row or column or block fills up, one can argue that a digit must appear in a particular cell because it must appear somewhere and other possibilities may be ruled out. These observations may be generalized into pruning algorithms that eliminate multiple possibilities. The pruning algorithms we supply are powerful but are not complete in the sense that we cannot guarantee that all digits that are in fact impossible will be found and pruned.
The essence of a Sudoku puzzle is that certain cells of the puzzle are filled with digits in advance in such a way that the puzzle has a unique solution. The solution may hopefully be found by the use of logic that eliminates possibilities. In the worst case one may need to guess a digit and push forward to either reach a solution or obtain a contradiction. In the latter case, one must remove those digits entered since making the guess. When using a puzzle with pencil and paper this often requires erasing the entire puzzle and starting over since it is hard to remember precisely which digits have been entered since making the guess.
This software is intended as a Sudoku Helper that can assist with hints when you are stuck and that can support the process of guessing with backtracking when necessary. As a user, you may choose when to display hints and what algorithms if any to use to prune the hints. Once you have looked at the hints, it is the most fun to clear the hints and resume reasoning on your own.
The software supports the notion of freezing. At any point when you believe the digits entered so far are accurate, you may Freeze the puzzle in that state so these digits may not be changed. You may want to freeze often when doing a difficult puzzle. Each freeze is considered as a distinct step so if you discover that you make a mistake in freezing then you may Thaw just the last Freeze step. You may also thaw everything if you have made a complete hash of the puzzle.
To support guessing with backtracking, we recommend that you Freeze just before a guess. Then you can make the guess and proceed to follow up its logical consequences. If you discover a contradiction then you can use the command Remove Back to Last Freeze. This command will take you back to the point where you made your guess and you are ready to try an alternative.
The ability to undo a series of steps following a guess was the reason for building this Sudoku Helper as I became rather tired of erasing Sudoku puzzles printed on paper.
Click on one of the 81 cells in the puzzle that is active (beige) rather than frozen (light blue). The cell will be highlighted with a red border. Press one of the keys 1 to 9 to enter that digit and press 0 or space bar to make the cell empty.
To get to a cell, you may click on it with the mouse, or move to the cell using the 4 cursor-arrow keys. The arrow keys skip frozen cells.
When a digit is entered or removed from a cell, underneath an algorithm is run to construct the trivial hints, that is, a list of what digits values remain possible for the empty cells after a trivial application of the basic constraints derived from the Sudoku rules.
The trivial hints may be pruned via pruning algorithms that reduce the possibilities further.
The button Show Hints shows the current state of the hints (after possible pruning).
The button Clear Hints hides the display of the hints.
The button Reset Hints resets the hints to the trivial hints and then displays the hints.
The check box Show Hints Automatically? determines whether or not to show or clear the hints after digit data is entered or deleted.
The check box Prune Hints Automatically? determines whether or not to automatically prune the hints after digit data is entered or deleted. If this box is checked, then the hints will be shown regardless of the setting for the check box Show Hints Automatically?.
There are three check boxes that determine which set of three pruning algorithms will be used during any pruning process.
The pruning algorithms will be discussed below.
The buttons Prune Once and Prune Repeatedly allow you to invoke the pruning process manually and to decide whether to do one phase or many phases. The box next to Has Pruned? will turn red if some pruning did take place and turn white if no pruning actually happened.
The Freeze button will freeze any data cells that have been entered since the user began with an empty puzzle or since the last freeze. Each freeze is recorded internally independent of any earlier freeze. To undo the last freeze step, click the Thaw button. You can undo multiple freezes operations in reverse order by multiple thaw clicks. To unfreeze the whole puzzle, click Thaw All.
The Remove Back to Last Freeze button will remove all digits entered since the last freeze. This button is extremely useful if you have made a guess that has led to a contradiction and you want to remove all of the digits entered because of that guess.
The button Remove Everything button will clear the puzzle and give you a blank puzzle to start with.
The Java file:
SudokuModel.java
The Java file:
SudokuHint.java
The Java file:
SudokuApplet.java
The Java file:
SudokuBase.java
The Java file:
SudokuTable.java
The Java file:
SudokuBlock.java
The zip file with all applet source:
SudokuApplet.zip
The zip file with all applet compiled class files:
SudokuAppletClassFiles.zip
The applet tag in this page is as follows:
<applet code="SudokuApplet.class" archive="http://www.ccs.neu.edu/jpt/archive/2.4.0/lib/jpt.jar" width="920" height="680" > </applet>
The Sudoku Helper applet has been tested and works on three browsers under Windows XP and fails on one browser under Windows XP. I have received confirmation from others that the applet works on Mac OS X using Safari and also works on Linux.
The applet was compiled on the current Eclipse, 3.1.2, on Windows XP. I currently have 4 Java releases installed: 1.4.1_07, 1.4.2_11, 1.5.0_05, and 1.5.0_06. To maximize compatibility with installed browsers, I set Eclipse to compile the applet using Java 1.4 with the JRE setting of 1.4.1_07. Since this is the setting under which Java Power Tools 2.4.0 was earlier compiled, I did not think I could back up any further.
On Windows XP, the applet works under Internet Explorer 6.0, Firefox 1.0.7, and Netscape 8.1. The Java plugin for IE is set to Java 1.5 while the plugins for Firegox and Netscape are set to Java 1.4.2_11. Hence, the issue is not simply the vintage of the plugin. The version of Opera which fails is 8.51 and it claims to be using Java 1.5. The Opera failure is rather wierd. If you click a button first, the applet works. If however you click a cell and press a key to enter a digit, the applet frame either shrinks or the applet crashes.
On the Mac, I have had problems running the applet but I now believe that this is due to problems with my particular machine. I have received confirmation from others that the applet works on Mac OS X using Safari and also works on Linux.
The Sudoku Helper application adds file IO so that a puzzle entered by the user may be saved to disk in its initial state and in later states as the solution proceeds. This enables the user to pause during the solution of a puzzle and pick it up later.
The application version is illustrated by the screen snapshot below.
The puzzle shown as an illustration in the snapshot is puzzle #320 from The Original SUDOKU, Volume 1, Nikoli Publishing and Workman Publishing, 2005, which is an excellent book that I recommend.
As you can see, the application has 2 additional buttons that read Sudoku data from a file and save such data to a file. These buttons do not appear in the applet version of the Sudoku Helper program. In using the Sudoku Helper application, I find it convenient to save the state of a new puzzle to a file so I can call it up later. I may also save an intermediate state in case I have to stop playing with the puzzle and want to pick it up at another time.
Sudoku files are given the extension .sudoku. The file format is a simple text file with 9 lines of 9 digits. For instance, the puzzle above would be saved as the following text data:
070009004 600004080 800030090 000800070 001000400 030005000 050020001 020100005 300700060
The Java file:
SudokuModel.java
The Java file:
SudokuHint.java
The Java file:
Sudoku.java
The Java file:
SudokuBase.java
The Java file:
SudokuTable.java
The Java file:
SudokuBlock.java
The Java file:
StringableFileIO.java
The zip file with all application source:
SudokuApplication.zip
Note: The application requires the Java Power Tools library jpt.jar version 2.4.0.
Note: The file StringableFileIO.java will become part of
Java Power Tools in the next release of JPT.
Suppose you have a triplet of 3 rows or 3 cols that all pass through a row of blocks or a col of blocks. Then under certain circumstances, you can argue that some hints may be eliminated.
Here is an example:
1 2 3 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 7 8 9 ? ? ?
First:
The middle row in the block 2 can only contain
{ 1, 2, 3 } in some order.
The middle row in the block 1 can only contain
{ 7, 8, 9 } in some order.
Then:
The top row in the block 2 can only contain
{ 4, 5, 6 } in some order.
The bottom row in the block 1 can only contain
{ 4, 5, 6 } in some order.
Finally:
The top row in the block 3 can only contain
{ 7, 8, 9 } in some order.
The middle row in the block 3 can only contain
{ 4, 5, 6 } in some order.
The bottom row in the block 3 can only contain
{ 1, 2, 3 } in some order.
The Triplet algorithm generalizes this reasoning.
Consider the set of all hints for a row, a col, or a block that correspond to cells that are still empty.
Suppose there exist a hint set of size k such that there exist (k-1) other hint sets that are subsets of this hint set (a subset may be equal to the set).
Then, all k hints may be removed from any other hint sets for the same row, col, or block.
For example, if we have a hint set { a, b, c } and
two hint sets { a, b } and { a, c }, then we may
remove { a, b, c } from any other hint sets
for the same row, col, or block.
Suppose for some digit value d,
d turns out to occur as a hint in a
given row, or a given col, or a given block in just
one cell. Then that cell must have value
d even if
there are currently other hint values for that cell
since there is no other place for d to go.
Therefore, we can remove all other hints from that
cell and we can remove
d from all other cells in
the same row, or same col, or same block as the
cell in question.