The Hidden Logic of Sudoku

Denis BERTHIER

First edition: May 2007

Second edition: November 2007




Frequently Asked Questions




This is an ordered list of questions and answers about my book.

You can send your questions at my address (my_first_name dot my_last_name atsign int-edu dot eu).
Any question should have as subject the single world "HLS-Q" - otherwise it may be considered as spam.
But, please, before sending any question, check that the answer is not already in this file.
Disclaimer:
    - This is NOT a blog.
    - I do NOT promise any individual answers. Rather, your question will appear (maybe rephrased) in the proper section of this file.


1) Questions about the book itself


Q: In your book, you say that "Sudoku is fundamentally a three dimensional problem". Why then don't you introduce 3D-patterns, such as 3D-chains of types corresponding to those of the 2D-chains you have defined?
A: The main reason is that the rules defined in the book are intended for human solvers and that detecting chain patterns in 3D space would be very difficult (at least for me). My approach is therefore to approximate 3D space by several 2D perspectives of it (the rc-, rn- and cn- spaces), giving rise to graphical representations on which the patterns can easily be seen.

Q: In the second edition, you do introduce 3D-chains. Doesn't it contradict your previous answer?
A: After the first edition was published, I found a natural 3D extension of the 2D chains introduced previously. This extension reveals the full power of the supersymmetries defined in the first edition. Puzzles that couldn't be solved with 2D chains can now be solved with 3D chains (most of the time, with short 3D chains).
But this doesn't change what was said previously about 2D chains: they are easier to spot than 3D chains. One can therefore continue using them before resorting to 3D chains.


Q: Many of your rules are based on the auxiliary rn, cn, and bn representations. Do you plan to provide tools for generating them from the standard rc-representation?
A: 1) Let me remember first that these representations are really useful only for puzzles classified at least at level L4, and that they should not change the way one solves the easiest puzzles (e.g. most of those appearing in newspapers).
     2) Although it may be tedious to generate these representations by hand, it is conceptually very straightforward and with some training it can be quite fast.
     3) I have written a very simple step-by-step method for doing this. You can find it on the Web pages dedicated to the online supplements.
     4) About computerised tools that would implement it, I don't know yet. Anyone willing to do it…
     5) Ruud has implemented these spaces in his last release of his Sudocue solver.


Q: Aren't the rn, cn and bn representations a purely abstract thing, with no practical use?
A: 1) On the contrary, they will allow you to solve many puzzles you could not solve without them.
     2) Generating these representations is very simple (see previous question).
     3) Using them cannot be easier. In these two auxiliary representations, the patterns you have to look for are exactly those you already look for in the standard representation and that do not rely on the constraints on blocks.
     4) Using these representations and looking for a limited number of familiar patterns on them is much more effective than looking for a multiplicity of rare exotic patterns on the standard representation.


Q: In addition to the well-known xy-chains, you introduce the notion of an xyt-chain. Are these new chains really useful in practice?
A: 1) Yes. Many puzzles that cannot be solved with xy-chains can be solved with xyt-chains. See chapter XXI for details.
     2) Yes. Detecting an xyt-chain is a little more difficult than detecting an xy-chain, but it remains much easier and much more effective than rying to detect lots of rare exotic patterns.
     3) Yes. As the chain length increases, the number of xy-chains decreases much faster than the number of xyt-chains.
     4) Yes. They can be combined with the auxiliary representations to give rise to hidden xyt-chains, allowing still more puzzles to be solved.


Q: Most of the examples in your book are also proofs of independence results. I understand this may be important in theory, but why do you insist that it is useful in practice?
A: 1) The book contains a hundred of indepence results, all of the following form: "rule R cannot be reduced to (is not subsumed by) a given set of rules T", where the rules listed in T are simpler than R (here "simpler" refers to the order I have defined on the set of resolution rules).
     2) A result of this kind is very useful in practice because if rule R was a consequence of the other rules in T, then looking for instances of R after you have searched your grid for instances of rules in T would be wasting your time.
     3) As an example, I prove that XYT3 (the rule for xyt3 chains) is subsumed by the rules for Interaction, Naked-Triplets and XY3. It means that you do not have to look for xyt3 chains.
     4) Conversely, I prove that the above property does not extend to longer xyt-chains, which means that, even if you have looked for xy13-chains, you are not dispensed with looking for xyt13-chains. (Of course, since xyt-chains subsume xy-chains, you may skip the search for xy-chains).
     5) As an example of a different kind, I prove that, given BSRT, the Basic Sudoku Resolution Theory defined in chapter IV, xy- (or xyz-) chains with loops are subsumed by xy- (or xyz-) chains without loops. Similarly, given BSRT plus the Interaction rules, c-chains with loops are subsumed by c-chains without loops. What does this mean in practice? As long as xy-, xyz- and c- chains are concerned, you should not allow them to have loops. You therefore have to look only for patterns much simpler to find than those in which loops would be allowed.
     6) To conclude this, independence results are very important, in theory and in practice. This is why a major part of the book is dedicated to them (nearly all the examples are independence results).


Q: Your book deals only with the standard 9x9 Sudoku puzzles. Do you plan to address variants?
A: 1) Definitely no - at least, not myself.
     2) But the book provides all the necessary logical means for doing so.
     3) As for the software (SudoRules), it already has the structure for dealing with (standard) puzzles of any size (but it does not have specific rules for them, such as rules for Quintuplets or larger subsets).
     4) In the future, I may have students projects on some extensions or variants.
     5) Anybody interested in this, please contact me.


Q: Why does a Professor spend his precious time on such a futile problem? (As you may have guessed, this is from one of my students)
A: 1) This is a very good question. Thanks for asking.
     2) As I explain in the Conclusion, Sudoku is NP-complete, which means that it is mathematically equivalent to a lot (a few thousands) of non-futile well-known problems, such as the famous travelling salesman. It is therefore a very popular example of these problems.
     3) As suggested in the Prologue, there is a gap between the purely logical aspects of the game and all the unsaid psychological aspects tied to its usual spatial presentation. At the present time, I don't have much to say about this. But this doesn't make the problem less titillating for Cognitive Science.


Q: Do you plan to write a French version of your book (you guessed right: this is from a French colleague)
A: At the  present time, I have absolutely no plan for this: I like writing in French, I like writing in English, but I hate translating. But, if a publisher is interested in doing it…



2) Questions about the online supplements


Q: Do you plan to issue regularly lists of puzzles corresponding to the various levels of your classification?
A: 1) Definitely no. I'm not running a Sudoku company.
     2) On another page, in the online supplements, you can find lists corresponding to the three databases used in the book. These lists are just  another presentation of the global classification results given in the same page, but in a form from which you have direct access to the puzzles at each level.
     3) Until you have solved by hand all the puzzles in these lists (a total of 56,628), I have time for doing lots of other things.
     4) Remember that my classification is about the most complex rule needed to solve a puzzle. It is NOT about the whole resolution path. Within any given level, resolution paths may be of very different complexities. There are several examples of this in the book.



3) Questions about the SudoRules solver


Q: Do you plan to make your SudoRules solver widely available (under GPL or other license)?
A: At the present time, I don't know. A minimum pre-condition for this would be writing a users guide, which I haven't done yet - being the only writer and only user.

Q: Do you plan to put on your Web pages an online solver built on SudoRules?
A: At the present time, I don't know. If I find someone for writing the Java interface…




Home(The Hidden Logic of Sudoku)         Home(Denis Berthier)


(last update: October 30, 2007)