The Hidden Logic of Sudoku

A new conceptual framework for solving Sudoku puzzles with pure logic

 
Denis Berthier

First edition: May 2007

Second edition: November 2007




Online Supplements


The Strategic Level






© Denis 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 (confluence, ...).

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 criteria.

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- cell, ...)

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 priorities

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.

Type component:
Consider the following partial ordering of the various types of chains I have been considering:
Code:

xy hxy :             xyz hxyz                 : xyzt hxyzt     : nrczt
            : nrc                           : nrcz                          : nrczt
            :             xyt hxyt                                          : nrczt             
            : nrc                           : nrct                           : 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.


Length 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 SudoRules):
- 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 nrczt-braids.

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 length
     xyz before hxyz before nrcz of the same length
     xyzt before hxyzt before nrczt of the same length
     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
             tP, 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 or bilocation).
Notice that, although it seems natural, this may not be a very good strategy. Sometimes it is easier to eliminate candidates that are not bivalue.

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 ORACLES

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 solution.
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 a solution.
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: http://www.sudoku.com/boards/viewtopic.php?t=5995&start=120).


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.

SER:
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.

Ordinary T&E:
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 braids.

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 T&E(NRCZT-WHIPS).















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