The Hidden Logic of Sudoku
A new conceptual framework
for solving Sudoku puzzles with pure logic
First edition: May 2007
Second edition: November 2007
The Strategic Level
Berthier. All the material in this page and the pages it gives
access to are the property of the author and may not be
re-published or re-posted without his prior written permission.
1) THE STRATEGIC LEVEL
In "the concept of a resolution rule" page,
I sketched my general framework, based on first order logic, in
which I defined the general concept of a resolution rule, some
properties a resolution rule can have (reversibility, composability,
...) and some properties a set of resolution rules can have
In several other pages (including the "xyt-chains", the
"hidden-chains" and "the fully supersymmetric chains", I defined
several specific types of chains with the associated resolution
rules (elimination theorems). I showed that some types of resolution
rules subsume other types.
All this constitutes what I call the pure logic level.
But there is nothing in all this that tells the player: in such
circumstance, look preferentially for such or such pattern.
This is the type of question that can be raised at the level I shall
call the strategic level.
The strategic level is the
level where different heuristic ways of using resolution rules can
be defined. At this level, I speak of heuristics instead of logic
because, contrary to the resolution rules at the logic level, the
"strategic rules" at this level have no absolute validity. They
should somehow try to take the players experience into account to
guide the resolution process (each step of which is still justified
by a resolution rule). The difficulty is that different players are
likely to use very different heuristics.
For a given set of resolution rules, there can be many different
strategies. I shall soon give examples for nrczt- theories.
The purpose of this page is therefore to explore the different ways
one could define resolution strategies.
(Notice that the word "strategy" here is not used in the sense of a
"solving technique" or of a "resolution rule" which it is
unfortunately sometimes given in the sudoku litterature.)
A strategy can be based on priorities put on the various rules;
priorities themselves can be based on the types of the patterns, on
their size (their length for chains) and on other objective
A strategy can also be based on ways of focusing the search on
trying to eliminate some candidates (chosen according to criteria
that remain to be defined, such as: in a bivalue rc-, rn- cn- or bn-
As not much is known at this level (I mean, much is known in an
intuitive form by players, but not much is known in a well
conceptualised form), it may be the case that this page will not
lead us very far. But who knows in advance?
2) A FEW STRATEGIES FOR
THE NRCZT THEORIES
The purpose of this section is not to tell any human player how to
use the various resolution rules I have been considering: they can
be used freely, in any order. And they can be mixed with any other
rule you like.
The purpose of this section is to define a few formal strategies
that can be used by either a human or a computer solver. This is
very far from being exhaustive.
Such strategies will seldom be used in a strict manner by a human
solver, which tends to be more opportunistic; but they may somehow
guide his search.
Contrary to a human solver, a computer solver needs to make
systematic choices and will have to choose some predefined strategy
(it may have several, but it can use only one at a time).
2.1) Strategies based on rules
As chains are the main solving tool for hard puzzles, they can be
considered as the backbone of a hierarchy.
As chains/whips/braids have both a type and a length, chain rule
priorities can be based on both.
Consider the following partial ordering of the various types of
chains I have been considering:
xyzt hxyzt : nrczt
As this partial ordering is based on subsumption relations, defining
priorities that do not respect it would be equivalent to
de-activating some of the rules. E.g. if nrczt is given the highest
priority, then no other type of chain will be found.
component: shorter length gives higher (at least not lower)
priority. Any other choice would be irrational (not as an
opportunistic choice but) as a systematic preference.
Given these two basic components, there remain many ways of
combining them into chain rule priorities. Indeed, any full ordering
compatible with the mathematical product of these two partial
orderings is valid.
Other patterns (not chains): insert them in the chain hierarchy.
There may be lots of ways to do so. In SudoRules default strategy,
the insertion of Subset rules (Naked, Hidden and Super-Hidden) is
done just before the xy-chains on the same number of cells.
example 1 (type preference): all the xy and hxy before all the nrc,
before all the nrct, before all the nrczt (the length is not taken
into account); whips before braids.
example 2 (length preference, which is the default ordering in
- all chains of any type of length n before all chains of any type
of length n+1
- for a given length: xy before hxy before xyt before hxyt before
xyzt before hxyzt before nrc before nrct before nrczt-whips before
example 3 (3D penalty):
xy before hxy before xyt before
hxyt before xyzt before hxyzt and any 2D chain of length n before
any 2D chain of length n+1
nrc before nrct before nrczt and any 3D
chain of length n before any 3D chain of length n+1
for the 3D chains of length n, put them all
after all the 2D cahins of length n+P (P is the 3D-penalty) and
before all those of length n+p+1
example 4 (t penalty and z penalty) :
xy before hxy before nrc of the same length
xyt before hxyt before nrct of the same
xyz before hxyz before nrcz of the same
xyzt before hxyzt before nrczt of the same
any chain of length n with the t-exetnesion
between any chain of length n+tP without it and any chain of length
n+tP+1 without it
any chain of length n with the z-exetnesion
between any chain of length n+zP without it and any chain of length
n+zP+1 without it
any chain of length n with the t- and z-
exetensions between any chain of length n+ztP without it and any
chain of length n+ztP+1 without it
zP and ztP are the z-, t- and ztP penalties, with ztP > tP and
ztP > zP.
example 5 (t penalty, z penalty and 3D penalty) :
Combine examples 3 and 4.
All these strategies can be applied in SudoRules.
Notice that, if instead of considering a backbone built on the
xy-to-nrczt family, one tried to define a backbone based on ALS and
their Hidden counterparts (HALS or AHS) and their Super-Hidden
counterparts (SHALS, not currently used in AICs, AFAIK), one should
also introduce two parameters (length of the chain and size of the
ALSs) and define how they should be combined.
2.2) Strategies based on focusing
on some candidate
Basic principle: choose a candidate, say z, and try to eliminate it
by all available means before you try another candidate.
Notice that this can be combined with any of the previous
strategies, restricted to patterns with z as a target.
The main difficulty here is, how to choose the focus on a candidate?
I have already given an example: focus on candidates that are
bivalue in either of the rc-, rn-, cn- or bn- spaces (i.e. bivalue
Notice that, although it seems natural, this may not be a very good
strategy. Sometimes it is easier to eliminate candidates that are
Merely focusing on candidates would be easy in SudoRules. But what's
missing is heuristic rules saying on which candidate(s) it is
interesting to focus.
2.3) Strategies based on symmetries
One can also try to exploit symmetries in the entries.
As this is very specific and I have no experience with this, I just
mention it as a possibility.
3) STRATEGIES BASED ON
In this section, I'll consider various kinds of high level
strategies. I call them high level because they deal with the choice
of the resolution rules one will use in the resolution process, not
in the specific ways these rules may be be used. Such high level
strategies can be combined with any of the strategies mentioned in
my previous posts.
These strategies are based on various oracles, i.e. on external
knowledge about a puzzle that is given together with the puzzle.
There may be different sorts of such knowledge.
The most common sorts are the existence of a solution or the
uniqueness of a solution. I mention them here because they are good
examples of oracles, but I won't consider them further.
Just remember that resolution rules are valid for any set of
entries, independently of the existence or the uniqueness of a
When a puzzle is solved using resolution rules, both the existence
and the uniqueness of the solution is automatically proven.
When uniqueness is guaranteed, one can use U-resolution rules, i.e.
rules relying on the axiom of uniqueness of a solution.
Strangely enough, no one has ever proposed an E-resolution rule,
i.e. a rule that would explicitly rely on the axiom of existence of
When a puzzle with no solution is dealt with, the fact that the
entries are contradictory may generally be proven with resolution
rules; but proving contradiction may be as hard as solving a puzzle
(see the example I gave here:
Another kind of oracle that I've already considered is the knowledge
that a set of candidates is a backdoor. I've used this knowledge
abour EasterMoster to guide the search for a solution based on
nrczt-chains plus T&(NRCZT) and using my notion of a strong
T-backdoor. See here.
Here are now two other oracles one could consider: SER and being
solvable by T&E.
If I know the SER of a puzzle is not greater than 9.3, then I know
experimentally that it is very likely (but it is not certain) that I
can find a solution with nrczt-whips. So I'll first look for a
solution that uses only whips and doesn't rely on braids. This is
consistent with the idea of preferring chains over nets.
If I know that a puzzle is solvable by T&E but its SER is
greater than 9.3, then, using my equivalence theorem between T&E
and nrczt-braids, I know that it is solvable by braids and it is
unlikely to be solvable by whips. Unless I have some reason (such as
SER less than 9.5 and special symmetries) to think that it may
nevertheless be solvable by whips, I'll try directly a solution with
Iterated T&E at depth 2:
If I know that a puzzle is not solvable by T&E, then I know it
is exceptionally hard but it is neverthelss solvable by T&E at
depth 2 (at least this is true for all known puzzles) and I know
this is equivalent to being solvable by T&E(NRCZT-BRAIDS). I
don't know whether it is solvable by T&E(NRCZT-WHIPS) but I'll
first try with whips instead of braids, because I haven't yet found
a puzzle that is not solvable by T&E(NRCZT-WHIPS) and, whichever
result I find, it will teach me something about being solvable by
Home(The Hidden Logic of Sudoku)