The Hidden Logic of Sudoku
This is an ordered list of questions and answers about my book.
First edition: May 2007
Second edition: November 2007
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.
- 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
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
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
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
3) Yes. As the chain length increases, the
number of xy-chains decreases much faster than the number of
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
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
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
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
Q: Do you plan to issue regularly
lists of puzzles corresponding to the various levels of your
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
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)
(last update: October 30, 2007)