-
Notifications
You must be signed in to change notification settings - Fork 15
SE121 FAQ
This page answers frequently asked questions about the Sudoku Explainer, a step-by-step Sudoku solver and explainer written in Java 5.
Sudoku Explainer - the step-by-step Sudoku solver
Some interesting Sudokus for exploring the solving techniques
Equivalence between Naked Sets, Hidden Sets and Fishy patterns
Sudoku on Wikipedia - The free encyclopedia
Sudoku Susser - another Sudoku solver
Sudoku Assistant/Solver - another Sudoku solver (in Javascript)
Sudoku Players' Forums
Sudoku Programmers' Forums
Have a look at the description of Wikipedia:
http://en.wikipedia.org/wiki/Sudoku
There is no clear answer to this question, because:
- Some techniques are special cases of other techniques, or generalization of other techniques. An X-Wing for instance, is a special case of Bidirectional X-Cycle, and a Naked Pair is a special case of Bidirectional Y-Cycle.
- Some techniques can be viewed as either one or many techniques. For instance, the Hidden Pair can be viewed as one technique, or as three if we consider that it can occur on a row, column or block. Hidden Single, Pair, Triplet and Quad can also be viewed as four different techniques, or as a single generic one, the Hidden Set.
- Some techniques are completely different, but they give equivalent results. Examples are the Naked Sets and Hidden Sets. On a row, column or block with, for example, 7 empty cells, a Naked Quad is equivalent to a Hidden Triplet, and a Hidden Quad is equivalent to a Naked Triplet.
The Sudoku Explainer has about 30 different solving techniques. But other classifications are possible and would lead to more, or less techniques, and the same semantics.
Good question. Each solving technique has its own history, and usually the name is given by the first guy who finds it. For instance, because when it was discovered, it really looked like a swordfish, the Swordfish solving technique got this name. But it usually do not look like a swordfish at all. The same is true for many other names of solving techniques. The Sudoku Explainer uses standard names whenever possible, at least for most of the simple solving techniques.
Unfortunately there is no real standard on the terminology of some advanced solving techniques. The Sudoku Explainer uses names which might be completely different on other solvers. The following list shows some equivalence between some names used in the Sudoku Explainer and other commonly used names:
- Bidirectional X-Cycles are also known as X-Cycles, contiguous X-Cycles, Fishy Cycles, Coloring, Bilocation cycles.
- Bidirectional Y-Cycles are also known as Y-Cycles, contiguous Y-Cycles, XY-Chains, Forcing Loops, Bivalue cycles.
- Forcing X-Chains are also known as X-Chains, discontiguous X-Cycles, Turbot Chains, Coloring.
- Some Forcing Chains are also known as Y-Chains, discontiguous Y-Cyles (the Sudoku Explainer does not put them in a special category).
- Bidirectional Cycles and Forcing Chains in general, are also known as Nice Loops.
- Forcing Chains and Dynamic Forcing Chains are also known as Forward Implication Chains, 3D Medusa.
- BUGs type 1 are also known as BUGs.
- Unique rectangles and loops of types 2, 3 and 4 are sometimes classified in more categories: 2, 2B, 2C (or 5), 3, 3B, 4 and 4B.
Note that there might be small variations in the exact definition of a solving technique among existing solvers.
The following solving techniques (among other) are not implemented and not already covered by the implemented techniques:
- Forcing nets (Forcing Chains with bifurcations)
- Tabling
- Backtracking (aka brute-force or guessing)
- BUG-Lite (Generalized Unique Loops)
- Magic Cells
- Subset Counting
- Dancing links
- Finned Fishes
- etc
Due to the great activity on the Sudoku forums, new techniques are found regularly, so this list is certainly far from being complete.
Pointing is a solving technique. In general, it is necessary to write down every possible candidates in all empty cells in order to apply it. But while playing by hand, I discovered that in some cases it is possible to apply this technique without writing the candidates: when the technique directly reveals an Hidden Single.
This is the idea of the Direct Pointing, Direct Claiming and Direct Hidden Pair techniques: they are special cases of Pointing, Claiming and Hidden Pair in which a Hidden Single immediately follows. Because it is not necessary to write down candidates to discover these cases, they are rated lower than the Naked Single. For the same reason, applying one of these techniques will set the Hidden Single, but not remove other candidates in the empty cells.
The Sudoku Explainer also implements Direct Hidden Triplets, with difficulty between Naked Single and (general) Pointing. Thus, a Sudoku with a difficulty less than 2.6 can be solved without writing down candidates in empty cells. A Sudoku with difficulty less than 2.3 can be solved without "thinking" candidates.
In theory: no, because none of the solving techniques it uses can be proven to solve every Sudokus. In practice, when the version 1.2 of the Sudoku Explainer was released (November 2006), there was no Sudoku it could not solve. But in the future somebody may eventually find a Sudoku harder than all the previous ones that the Explainer will eventually fail to solve. This already happend to version 1.1 and version 1.2 had to be extended with a new solving technique.
Note that this only applies to Sudokus that have exactly one solution. The Sudoku Explainer cannot solve Sudokus with more than one solution. Also note that by "solve", it is meant "solve step by step and explain each step". The brute-force solver available in the menu is proven to solve any Sudoku, but it only gives the final solution.
There are multiple reasons:
- Hints whose outcomes are already covered by simpler hints are not displayed by default. Uncheck the filter checkbox to display them anyway.
- Even when hints are not filtered, the Sudoku Explainer will not search for useless hints, that is, hints that are always covered by simpler hints. For example, on a row with 7 empty cells, naked quads and hidden quads are not searched because there would automatically be an equivalent hidden triplet or naked triplet. Many similar small filters are applied.
- The "Get All Hints" button will not include hints involving implication chains (Forcing Chains and Bidirectional Cycles) if at least one simpler hint can be found. But the "Get Next Hint" button can be used to complete the list.
- Finally, Forcing Chains and Bidirectional Cycles whose outcomes are already covered by simpler Forcing Chains or Bidirectional Cycles are always filtered out. This prevents a lot of uninteresting chains to show up, such as long chains which are just simpler chains extended with useless links.
- Also note that the Options->Solving Techniques menu allows you to disable individual solving techniques. Due to the filters, a disabled technique may or may not be discovered as another, enabled technique.
No, for the following reasons:
- There is no standard way of rating the difficulty of the solving techniques. The rating used by the Sudoku Explainer is not perfect; and many other solvers and players may have other ratings.
- Some Sudokus can be solved either by a single, very hard technique, followed by trivial steps; or by multiple techniques of average difficulty. Which solution is the simplest? The Sudoku Explainer would choose the latter, but the former might be considered simpler in some cases.
- Using its rating, which is not perfect, the Sudoku Explainer uses a "greedy" strategy: it always choose the simplest rule at any given points, without thinking about the next solving steps. This strategy has two limitations:
- Sometimes, a simple technique is used, but is useless to solve the Sudoku, because it is always followed by an unavoidable, more difficult one; and the Sudoku can be solved with the more difficult one only. In practice, this means that some steps given by the Sudoku Explainer are sometimes useless. This is not a real problem, because only steps easier than the hardest one can be useless, but not the hardest step itself.
- On rare cases, failure to spot and apply a difficult pattern (because a simpler technique is applied) may make the difficult pattern to disappear, and the Sudoku to require an even more difficult technique. This can only occur with the two "unstable" patterns: Unique Rectangle/Loops and BUGs.
- The algorithm used for Dynamic Forcing Chains has some limitations: it may return a Forcing Chains with multiple small sub-chains instead of an equivalent single long chain, even if the long chain is smaller than the sum of the lengths of the small sub-chains. Also, implications that appear in multiple chains are counted multiple times when analyzing the difficulty.
The difficulty of a Sudoku is rated by the hardest solving technique that is required to solve it. This is not necessary the best rating scheme, and many other solvers might use different rating for some solving techniques (see previous question).
More precisely, the Sudoku Explainer uses the following difficulty ratings of the solving techniques:
- 1.0: Last value in block, row or column
- 1.2: Hidden Single in block
- 1.5: Hidden Single in row or column
- 1.7: Direct Pointing
- 1.9: Direct Claiming
- 2.0: Direct Hidden Pair
- 2.3: Naked Single
- 2.5: Direct Hidden Triplet
- 2.6: Pointing
- 2.8: Claiming
- 3.0, 3.2, 3.4: Naked Pair, X-Wing, Hidden Pair
- 3.6, 3.8, 4.0: Naked Triplet, Swordfish, Hidden Triplet
- 4.2, 4.4: XY-Wing, XYZ-Wing
- 4.5 - 5.0: Unique rectangles and loops
- 5.0, 5.2, 5.4: Naked Quad, Jellyfish, Hidden Quad
- 5.6 - 6.0: Bivalue Universal Graves
- 6.2: Aligned Pair Exclusion
- 6.5 - 7.5: Bidirectioal X-Cycles and Y-Cycles
- 6.6 - 7.6: Forcing X-Chains
- 7.0 - 8.0: Forcing Chains, Bidirectional Cycles
- 7.5 - 8.5: Nishio
- 8.0 - 9.0: Cell/Region Forcing Chains
- 8.5 - 9.5: Dynamic Forcing Chains
- 9.0 - 10.0: Dynamic Forcing Chains (+)
- > 9.5: Nested Forcing Chains
It seems that the difficulties 1.2, 1.5, 1.7 and >= 2 correspond to the degrees 1, 2, 3 and 4 of some newspapers. Note that many solvers are rating Naked Singles easier than Hidden Singles (which is reasonable when candidates are always visible). According to some sources, "diabolical" Sudokus are those that are not solvable without trial and error. But there is a great controversy on what "trial and error" means.
The Sudoku generator uses the following levels:
- Easy: difficulty 1.0 to 1.2 (can be solved using Hidden Singles in blocks only)
- Medium: difficulty 1.5 (requires Hidden Singles in rows or columns)
- Hard: difficulty 1.7 to 2.5 (can be solved without writing down candidates)
- Fiendish: difficulty 2.6 to 6.0 (can only be solved by writing down candidates, but does not require Forcing Chains)
- Diabolical: difficulty 6.2 or more (can only be solved with Forcing Chains)
Note that many solvers and generators place Naked Single before Direct Pointing, Direct Claiming and Direct Hidden Pairs, unlike the Sudoku Explainer.
Yes it is! A backtracking algorithm, also called "brute-force" solver, can solve any Sudoku in less than a second on today's computers. This algorithm is used by the "Solve" menu of the Sudoku Explainer to quickly show the solution. The goal of the Sudoku Explainer is not just to solve a Sudoku, but to explain each solving step. This implies that only techniques that match the way a human solves a Sudoku, and that can be explained, are implemented. Solving all Sudokus using such techniques only is a much more challenging task. See above the question "Can the Sudoku Explainer really solve all Sudokus?".
Why does the Sudoku Explainer not look like the screenshot on my computer ?
The Sudoku Explainer allows you to change its appearance, or "look & feel". By default, the Sudoku Explainer uses the appearance that matches the appearance of other applications. To change the appearance, use the menu Options -> Look & Feel. The screenshot has been taken with the Metal look & feel.
The Sudoku Explainer is freeware, and its author is lazy. Do not expect new features, and even bug fixes, to be implemented.
| Last update: 2006-11-27 |