A Sudoku Hint-Provider program. It's purpose is to allow one to enter a Sudoku game with as many squares filled in as are known, and it will either provide hints for solving or completely solve the game. The application is delivered as a java(2) jar file, and to run it you will need to open a Run->cmd console in Windows or use a Terminal in Mac. The first step in trying it is to download it to a location on your computer, then to run it.
- Download it using the link in the next section. You might download it to your desktop so it is easy to see / find.
- In the console window, cd to the directory where the jar file exists and run the command:
java -jar hint.txt
Notes:
- Yes, this is really a 'jar' file, not a txt file, so you will not be able to read it in Notepad. Even with the inappropriate extension, it will still function as a file Java can use. Unfortunately my web hosting service, in their infinite wisdom, has changed their policy and my site is no longer able to serve .jar files. I can still serve Microsoft documents capable of transmitting viruses, but not useful applications. Go figure.
- You will need to have java installed on your computer.
- This is not a professional quality product - sorry. If there is widespread interest in its use, I could improve it.
- If you try to use this and have any problems, email me and i will help or fix them.
- The jar file does contain the source code for this application. It isn't professional quality, but I include it for those who might be concerned about it doing something unfriendly.
|
How to use the Hint-Provider application.When the application first starts, it will expect you have a game board in mind and is ready to accept the known cell settings. It accepts them a row at a time. For each row you can just enter a string with the digits, using a 0 for an "empty" cell. Intervening spaces are thrown away. If at some point there are only empty cells remaining in the row, you do not have to enter the trailing 0s - it will assume that. Consider the game displayed on the right. The following strings would enter the cell settings in the program:
0000002 [trailing 0s not needed]
800 000 501 [intervening spaces discarded]
000480609
90200704
and so on entering all 9 rows
Note that if on startup you do not want to enter a game's cell settings, you can jump out of the "entry" phase by just entering a single decimal point for a row.
| |
After the known cell settings have been entered for 9 rows, the Hint-Provider will give its first hint (not shown in the image at the right), print out the current board position, and show the command prompt Sudoku>.
First we explain the commands and displays so you can use the tool. Later we explain the underlying philosophy, since our approach to Sudoku may be different than yours.
At the command prompt, you can always enter help to get a list of commands. And to leave the application, quit or exit will do.
The display command prints out the current board as shown. What are those funny symbols displayed? Within the application's view of a current game there are
- some cells with SETTINGS - those which you have input that a certain cell holds a given digit
- the remaining cells which have a list of POSSIBILITIES - that is a list of digits that may still be possible for that cell
| |
More commandsWhen you set the value of a target cell to a certain digit, the Hint-Provider will automatically remove
that digit as a possibility for all the other cells in the target
cell's row, column, and block. So far, so good. Later when the solve command is used,
various patterns will also remove additional possibilities from various cells. At
any point, a cell will either be Set because you have declared it to have that
digit, or have a list of possibilities.
Which gets us to the funny symbols shown after the display command.
- a '.' indicates a cell has just one possible value
- a ':' indicates a cell has just two possible values
- a '#' indicates a cell has just 3 possible values
You may have also mentally figured out the possibilities for a cell, and you can ask Hint-Provider to show its list for a given cell with the poss command. This command needs to specify the row and column of the cell being requested, so poss 2 8 in our example shows the Hint provider has {3, 7} as the remaining possibilities.
When you determine via logic that a target cell has to be a particular digit, then you use the set command which requires specifying the row, column, and digit to set the cell to.
There is also a setRow command which allows you to specify a row and list of cell values, the same as you could do during startup. This might be handy if you aborted the startup input, and later wanted to enter a game configuration.
There are also save and load commands, which save the current game so you can load it and continue later.
|
Give me a hint!After getting so far in a particular game, we may need a hint. (In fact we usually play the game up to the point of needing a hint before taking the time to enter it in the Hint-Provider.) This is where the solve command is used; it will find some pattern in the cells that implies that possibilities can be eliminated in other cells. But the solve command works differently depending on a couple settings in Hint-Provider
- singleStep When singleStep is set to true, then solve will find the first pattern that pares down possibilities, and will stop at that point. If singleStep is set to false, then solve will keep solving as long as it can find patterns to pare down possibilities, hopefully stopping when all the unset cells are left with one possibility. When Hint-Provider starts, singleStep is set to true, and unless you use the command singleStep false, it will just find one pattern at a time.
- trace on or off. When solve finds a way to pare down possibilities, it will tell you why it pared them down if trace is set to on; otherwise it will say nothing. When Hint-Provider starts, trace is set to on, so as solve finds ways to eliminate possibilities, it will tell you why it is doing so.
If you simply want to solve a game after entering it, set singleStep false and trace off and solve. However, if at that point you use the display command, it will show you all the cells you initially set, and the other cells with a decimal point (ie they have one possibility), but won't show you what that possibility is. In this scenario, use the show command - it is like display except it there is only one possibility for a cell, it is displayed, not the decimal point.
So now you should be able to load a given game, check possibilities, use solve to get hints or completely solve the puzzle.
|
The Patterns Hint-Provider looks for
If you are interested in the specific patterns Hint-Provider looks for to eliminate possibilities, we document them in the following sections to help make some sense of the hints it provides. Using six patterns, Hint-Provider is usually able to eliminate possibilities in cells until there is only one possible digit per cell. Hint-Provider does not check all possibilities to find a solution - it tries to use logic in the form of these patterns. They seem to be sufficient to solve all 'Evil' puzzles we've tried at www.websudoku.com
|
|
Pattern #1. In Group G, there is only one cell that can be set to ...Explanation.
This pattern that says for a given row, column, or block, if digit A has been removed as a possibility from all cells in that group except one, then that is the cell where it belongs -- and all other possibilities for that cell should be eliminated.
Example.
In Row 1 there is only one cell that can be set to 3
Here Hint-Provider, looking at Row 1, saw there was only one place where 3 could reside.
| |
|
|
Pattern #2. Because cell at R,C can only be D, the cell in ... cannot have that possibilityExplanation.
If all the possibilities for a cell except one have been eliminated, then that should be the final choice for that cell. The implication is that any other cells in the target cell's block, row, and column which still have that digit as a possibility, should remove it as a possibility, since it will be set in the target cell. (If you had made the necessary deductions and seen there was only one possibility for the cell, most likely you would have used the set command, rather than asking for a hint with the solve command. The set command automatically removes that digit from the possibility lists of other cells in the same block, row, and column, which is what this pattern is doing.)
| |
Example.
Because cell at Row 5,Col 4 can only be 7 the cell in Row 4 of the same column cannot have that possibility.
This is saying that although the user did not set the cell at 5,4, it can only be 7, so 7 is being removed as possibilities for other cells in the column.
|
Explanation.
This
pattern is detected when the only possible occurrences of a digit in
one group happen to fall completely within a second grouping.
In
our example, the only place that a 4 can appear in Row 2 is in columns
2 and 3 -- both of which are within Block 1 (for our purposes, the
blocks are numbered left to right, top to bottom). There cannot be a 4
in Row 2, Column 8 because there is a 4 elsewhere in Column 8. Nor can
there be a 4 in Row 2, Columns 3-4 because there is a 4 at Row 3,
Column 4.
So this tells us that because Row2 needs a 4, there
will be on in Column 2 or 3. From this we can conclude that within
Block 1, 4 will not be a possibility in Row 1, Columns 1-3, so it is
removed as a possibility in each of those cells.
The general
principle here is that if the only possible settings for a digit within
a row (or column) happens to be within a single Block, then that digit
cannot appear in other places in that block other than that row or
column.
Similarly if within a block, the possibilities for a
particular digit are within a single row (or column), then because that
digit has to appear within that block, it cannot appear in the row (or
column) outside that block.
| |
Example.
Because of setting 4 in Row 2 Blk 1 it is not a possibility for cell at Row 1 and Col 1
Because of setting 4 in Row 2 Blk 1 it is not a possibility for cell at Row 1 and Col 2
Because of setting 4 in Row 2 Blk 1 it is not a possibility for cell at Row 1 and Col 3
|
Pattern #4. Cell at R, C is one of N cells ... that can accommodate settings: ...Explanation.
Consider a row in which digits A and B are only possibilities in Columns 3 and 7. That means that digits A and B are not possibilities in any of the other columns in that row. Since we are considering two digits and two cells, we can conclude that no other digits are possible in columns 3 and 7 -- if some other digit were allowed into column 3 or 7, then there wouldn't be enough places to put A and B in that row. Therefore, if we consider a couple of digits in a group (row, column, or block) and there are only two possible cells where they could appear, then we can eliminate all other digit possibilities from those cells. Similarly, if we are considering 3 digits A, B, and C and there are only 3 cells that can contain them, then those 3 cells can eliminate any other digit possibilities.
| |
Example.
Cell at Row 1, Col 2 is one of 2 cells that can accommodate settings:2 4
Cell at Row 6, Col 2 is one of 2 cells that can accommodate settings:2 4
Focusing on Column 2, of the open cells in rows 1, 4, 6, and 8, the digits 2 and 4 are only possibilities in rows 1 and 6, so that's where they will end up. But this fact allows us to remove digits 5 and 7 as possibilities in these cells.
|
Pattern #5. In Group X, Settings [...] can only appear in cells [...] so other possibilities....Explanation.
This is similar but slightly quirkier than pattern #4. Pattern #4 said that if you were looking for combinations of 2 or 3 digits, and the possible cells for the group consisted of only 2 or 3 cells, then all non-members of the group could be eliminated from those 2 or 3 cells. With Pattern #5 this notion is extended for groups of more than 2 cells. Consider the case for a given row that the digit 1 is a possibility only in columns 1 and 2; digit 2 is a possibility only in columns 1 and 3; and digit 3 is a possibility only in columns 2 and 3. We can conclude that the digits 1,2,and 3 will end up in columns 1-3, and all other possibilities can be eliminated -- even tho 1,2, and 3 are not all possible in all 3 cells.
Example.
In Col 4 Settings [7, 8, 6]
can only appear in cells [cell at Row 6 Col 4, cell at Row 5 Col 4, cell at Row 9 Col 4]
so other possibilities in those cells are eliminated
In
this example, Column 4 has unsolved cells at Rows 1,2,3,5,6, and 9.
Considering the possible cells for digits 6,7, and 8, they are only
possible in rows 5,6, and 9 so that is where they will end up. So
because of this, digits 1,2, and 4 can be removed from the
possibilities list in Column 4, rows 5, 6, and 9.
| |
|
|
Pattern #6 in GROUP cells [...] handle settings [...]Explanation.
This pattern (courtesy the 2006 Scientific American article on Sudoku), says that if you consider, for example, a subset of 3 cells in a Group (row, column, or block), and the total number of possible settings in those 3 cells is just 3, then those 3 possibilities will have to end up in that subset, which also implies those settings cannot be possible in any other cells in the block
Example.
Pattern #6 in Col 3 cells [cell at Row 3 Col 3, cell at Row 4 Col 3, cell at Row 5 Col 3] handle settings [2, 4, 6]
6 is not possible in cell at Row 6 Col 3
4 is not possible in cell at Row 8 Col 3
Because,
in Column 3, settings 2,4, and 6 will be found in rows 3,4, and 5, we
can eliminate 6 as a possibility in Row 6; and eliminate 4 as a
possibility in Row 8.
| |
when all else fails...If a game gets to the point where where none of the previous 6 patterns are useful, then the hint provider will look for cells which have only two possibilities. The Hint Provider will then try one or the other of the possibilities and see if it would lead to a contradiction. If a guess leads to a contradiction, then it can be eliminated as a possibility.
|
|
