The concept of a RESOLUTION RULE and its applications

Advanced methods and approaches for solving Sudoku puzzles

Postby denis_berthier » Mon Nov 10, 2008 3:01 am

eleven wrote:
denis_berthier wrote:As a result, to solve a cell that may have different values in different solution grids, some form of trying every possibility is needed.
No, not always. Some time i had fun with solving some multisolution puzzles manually, at least when at the end i got a nice deadly pattern with 10 or 12 cells. Of course its kind of poor, when mighty resolution rules cant solve this one without guessing:
Code: Select all
 +-------+-------+-------+
 | . 7 . | 3 5 1 | 4 8 6 |
 | 3 4 1 | 8 6 9 | 5 7 2 |
 | 8 6 5 | 2 4 7 | 1 3 9 |
 +-------+-------+-------+
 | 1 3 4 | 9 2 8 | 7 6 5 |
 | . 8 . | 5 7 6 | 3 1 4 |
 | 7 5 6 | 4 1 3 | 9 2 8 |
 +-------+-------+-------+
 | 5 2 8 | 7 3 4 | 6 9 1 |
 | 4 1 7 | 6 9 2 | 8 5 3 |
 | 6 9 3 | 1 8 5 | 2 4 7 |
 +-------+-------+-------+

Yes? So, how do you find a value of the first cell if you don't try one of the remaining possibilities?
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

Postby eleven » Mon Nov 10, 2008 3:31 am

Well i know this most trivial deadly pattern, therefore i also know, that there are exactly 2 solutions with 2 and 9 swapped in the diagonals. Is this new for you ?
eleven
 
Posts: 1535
Joined: 10 February 2008

Postby denis_berthier » Mon Nov 10, 2008 3:45 am

eleven wrote:Well i know this most trivial deadly pattern, therefore i also know, that there are exactly 2 solutions with 2 and 9 swapped in the diagonals. Is this new for you ?

When I've reached this point, I'm so stupid that I see two possibilities for the first cell, each of which immediately leads to a solution. I need no deadly pattern.

The good question would have been: if you meet this pattern while solving a grid, what do you do?
What I do: I decide to change my grid provider.
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

Postby eleven » Mon Nov 10, 2008 3:50 am

denis_berthier wrote:I need no deadly pattern.
But you need guessing and others not. Wasn't that we talked about ? And probably you would stop after the first solution, not knowing what the provider did.
eleven
 
Posts: 1535
Joined: 10 February 2008

Postby denis_berthier » Mon Nov 10, 2008 3:56 am

eleven wrote:
denis_berthier wrote:I need no deadly pattern.
But you need guessing and others not. Wasn't that we talked about ? And probably you would stop after the first solution, not knowing what the provider did.

Right, but conceptually this remains guessing. It's just that you can optimise your guessing algorithm: the second solution is obtained straightforwardly frim the first.
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

Postby eleven » Mon Nov 10, 2008 4:16 am

denis_berthier wrote:Right, but conceptually this remains uessing.

No, only in your concept. It means nothing more than knowing and recognizing a trivial pattern.

Myth said, that your rules depend on the uniqueness of the puzzle, otherwise they produce nothing (or a single solution found with guessing). Given this, i cannot see any reason, why not all uniqueness methods are welcome there. Why this reduction to "constructive" methods and proofs ? Uniqueness patterns jump into your eyes, once you know them. And e.g. you know, this must be 3 then.
But you dont use that, because its not constructive. I cannot understand that.
eleven
 
Posts: 1535
Joined: 10 February 2008

Postby denis_berthier » Mon Nov 10, 2008 4:45 am

eleven wrote:
denis_berthier wrote:Right, but conceptually this remains guessing.

No, only in your concept. It means nothing more than knowing and recognizing a trivial pattern..

... which no player will ever find because valid puzzles satisfy the uniqueness assumption.
eleven wrote:Myth said...

See my answer to Myth.

If you want to discuss uniqueness, Glyn has opened a thread for this. Please do it there.
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

Postby DonM » Mon Nov 10, 2008 11:38 am

eleven wrote:
denis_berthier wrote:Right, but conceptually this remains guessing.

No, only in your concept. It means nothing more than knowing and recognizing a trivial pattern.

Myth said, that your rules depend on the uniqueness of the puzzle, otherwise they produce nothing (or a single solution found with guessing). Given this, i cannot see any reason, why not all uniqueness methods are welcome there. Why this reduction to "constructive" methods and proofs ? Uniqueness patterns jump into your eyes, once you know them. And e.g. you know, this must be 3 then.
But you dont use that, because its not constructive. I cannot understand that.


I'll take this a step further and in doing so, I submit that the point here is not one about uniqueness, but the definition of sudoku itself. Interest in sudoku exploded very quickly in 2005, but it was very simply defined at the time and the failure to make uniqueness a part of that definition turned out to be counterproductive. No one wants to solve this type of puzzle if the solution they find is not the one & only, unique solution. It's true of Sudoku; it's true of Kakuro; it's true of crosswords.

Unfortunately, there isn't an International Sudoku Society that can legislate these things, but, no matter: The definition of this puzzle game has been effectively amended just as if it had been the original definition. There are hundreds of Sudoku books, dozens of sites offering puzzles, umpteen puzzle packs being sold. All of them assume uniqueness; many explicity guarantee uniqueness. Bottom line: IMO, every discussion of sudoku, practical or theoretical should assume uniqueness or it isn't sudoku (as we know it today) being discussed.
Last edited by DonM on Mon Nov 10, 2008 10:20 am, edited 1 time in total.
DonM
2013 Supporter
 
Posts: 475
Joined: 13 January 2008

Postby Red Ed » Mon Nov 10, 2008 1:11 pm

Fine as an everyday rule of thumb, Don. But it can be instructive to understand if/when certain techniques generalise to multi- or zero-solution "puzzles". For example, I found it a pleasant surprise that UR1.1 could be used in the multi-solution case.
Red Ed
 
Posts: 633
Joined: 06 June 2005

Postby DonM » Mon Nov 10, 2008 2:30 pm

Red Ed wrote:Fine as an everyday rule of thumb, Don. But it can be instructive to understand if/when certain techniques generalise to multi- or zero-solution "puzzles". For example, I found it a pleasant surprise that UR1.1 could be used in the multi-solution case.


NP. I understand that people might like to experiment just for giggles, but I'm putting it out there that IMO there is no basis for the impression still given by more than one that uniqueness is still some sort of discretionary part of sudoku as practised today. If uniqueness is not going to be assumed in any discussion then that should be specifically mentioned and if it is, then we are on notice that it is Sudoku 2005 being discussed.
DonM
2013 Supporter
 
Posts: 475
Joined: 13 January 2008

Postby denis_berthier » Mon Nov 10, 2008 9:04 pm

Remember that Glyn opened another thread to discuss uniqueness: http://forum.enjoysudoku.com/viewtopic.php?t=6448

I can't see how uniqueness in itself could be a topic for debate in my framework. Everyone is free to adopt or reject it as he likes:
- there are the standard Sudoku axioms (constraints in cells, rows, columns and blocks). Resolution rules are consequences of these axioms.
- and there is the assumption of uniqueness, which is independent of the previous axioms. If one adopts it, I've long ago defined the notion of an U-resolution rule, which is a consequence of the standard axioms + the assumption of uniqueness (and not of the standard axioms alone).

Personally, I seldom use uniqueness because I prefer to prove it and I think it is the job of the puzzle provider to propose puzzles that can be solved using only the Sudoku axioms.
Last edited by denis_berthier on Mon Nov 10, 2008 8:24 pm, edited 3 times in total.
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

Postby denis_berthier » Mon Nov 10, 2008 11:06 pm



To complement my previous post about the assumption of uniqueness being a matter of choice.
It's not only a matter of theory. It may be fun to reject or relax it.
It may be fun to look for isolated sub-puzzles that lead to different solutions.
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

Postby denis_berthier » Wed Nov 12, 2008 12:15 am



After the avalanche of posts in the past ten days, it seems necessary to recast the focus on the topic of this thread.
I'll therefore summarise here the formal framework I've defined to model the sudoku problem and the vague notion of a "pure logic" solution.

GENERAL FRAMEWORK

The mathematical backgound is fisrt order logic (FOL). For a logic game, that shouldn't be too surprising.
As there are other approaches to sudoku solving, there could be different frameworks (cover sets in Allan's approach, graph theory and colouring problems, ...) but I think FOL is the most natural one, the one closest to what players are used to do. This was already the inspiring idea in the first edition of my book and it has never changed: keeping the formal concepts as close as possible to the natural ones.

In this framework, there is a very limited number of basic concepts: cell, row, column, block, number, value, candidate. They shouldn't sound too unfamiliar.
All the other concepts are defined from the above basic ones: bivalue, bilocation, naked pair, hidden pair, swordfish, ...., nrc-link*, chain, many specific types of chains, .... This allows to give very clear and non ambiguous definitions (e.g. a degenerated quad consisting of 2 pairs is not called a quad).
A major aspect of the framework is that all the concepts used are purely factual: they describe a situation on a grid in terms of what can be observed. Patterns are observables, they are not defined in terms of what wants to do with them (as is the case with views centred on a supposed "inference level").

A resolution rule has the form "pattern => action",
where "pattern" is defined as a combination of factual concepts as those mentioned above
and "action is the assertion of value(s) and/or the elimination of candidate(s).
A resolution path is the application of a sequence of resolution rules, starting from a given puzzle and ending, hopefully, in a solution (or in a sate where no rule can be applied).
Once more, none of this this should be too unfamiliar for a player.

Of course, any concept, be it simple or complex (quad, nrc-link, nrczt-chain, ...) is always given both an easily understandable natural language definiton and a formal one in FOL.


AXIOMS

There are only the four axioms that have always been the sudoku axioms everywhere in the world since the beginning of Sudoku and that remain the constraints you can see in any newspaper or any puzzles book: only one value in each cell, only one occurrence of each number in each row, column, block.
These axioms satisfy symmetry and super-symmetry relations that can be exploited in the definition of the resolution rules.
Symmetry can also be exploited if one chooses to use the extended Sudoku board I've designed with the four rc, rn, cn and bn spaces.

Adopting rules based on the assumption of uniqueness is an option. For a player, uniqueness can only be an assumption: he has no control on it. Either he accepts this oracle or he doens't.


FAMILIES OF RESOLUTION RULES

Several times, I've mentioned that the rules I've been considering with particular attention can be classified into four large families:

1) the elementary constraints propagation rules or ECP: elimination of candidates via propagation of direct contradictions along rows, columns and blocks,
2) the basic interaction rules between rows and blocks and between columns and blocks: BI
3) the subset rules: Naked, Hidden and Super-Hidden (or fish) versions of Singles, Pairs, Triplets, Quads,
4) the xy-to-nrczt (xy, hxy, xyt, hxyt, xyz, hxyz, xyzt, hxyzt, nrc, nrct, nrcz, nrczt) family of chain rules (including chains, lassos and whips).
Of course, this doesn't imply that only these rules should be used. The framework is completely open to the addition of new rules.

I've already shown the unity of the subset rules through symmetry and super-symmetry. This group of rules can easily be extended with all the variants of fish that have been appearing in the past years.

I've also shown why all the rules in the xy-to-nrczt family can be considered as progressive and natural generalisations of the basic xy-chain rule. This includes nrc-chains, equivalent to the basic NLs or AICs (basic meaning "with no ALSs"). Although nrczt-chains subsume the whole family, the other chains are easier to find and should therefore not be forgotten. This family is thus organised in a pedagogical hierarchy.

The above rules are enough to solve almost any randomly generated puzzle (indeed, in several tens of thousands of randomly generated puzzles, I've met none that they couldn't solve).
From experiments with hundreds of puzzles taken from various forums, it appears that they are enough to solve puzzles upto SER=9.3. In particular, they are used daily by human players on the French sudoku-factory forum to solve puzzles at SER 9.1 to 9.3. They can probably solve any puzzle that any expert human player can solve and even much more.
All this shows that, in spite of the simplicity of the framework, it allows to define simple and very powerful resolution rules.
It is important to recall this, because the sequel will discuss more complex patterns and I want to make it clear that such patterns, especially braids, are not necessary but for exceptionally hard puzzles.


RULES FOR EXCEPTIONALLY HARD PUZZLES

Considering the current interest for exceptionally hard puzzles, I've recently extended my set of resolution rules in two directions. Notice that such powerful extensions don't require any change to the framework.

Firstly, I've generalised my idea of additional z- and t- candidates and I've introduced a very general principle, zt-ing, that allows to define new patterns and associated new chain rules from any family FP of basic patterns: zt-whip(FP). zt-whipping is a general method (more general than the classical almost-ing) for including in chains/whips any pattern having an associated resolution rule.
In essence, the generalisation to nrczt-whip(FP) consists of allowing the right-linking candidates of a whip to be whole patterns instead of mere candidates.

If one takes FP=ECP+NS+HS, one gets the ordinary nrczt-whips.
If one takes FP=ECP+NS+HS+BI, one gets the grouped or hinged nrczt-whips.
If one takes FP = ECP+NS+HS+BI+SubsetRules, one gets a new family of chain patterns, whip(ECP+NS+HS+BI+SubsetRules), more general than nrczt-chains, AICs with ALSs and than their grouped or hinged counterparts. Indeed, these whips contain any AAAALS, AHHHHS and any AAAAAA-Fish, with as many A's or H's as one wants.
These patterns are chains, in exactly the same sense as any nrczt-chain or any AIC. They can be considered as defining a new set of levels in the hierarchy defined by family 4.
Such generalisations of nrczt-chains have also already been used in the sudoku-factory forum (see solutions by Caravail, Abi and Christian Barrucchi) - although in these cases ordinary nrczt-whips were enough.


Secondly, with the introduction of nrczt-braids, I have added a fifth family, composed of a (relatively mild) kind of nets, still with some linear structure.
The above two extensions can be combined, leading to zt-braids(FP) for any family of patterns with associated resolution rules.
I've also shown the close relationship between braids and Trial-and-Error (T&E) - the standard T&E procedure (which is not itself a resolution rule) with no guessing and no recursion: for any family FP, any elimination that can be done by T&E(FP) can be done by some zt-braid(FP). For players who use T&E for hard puzzles, this should soften their pain when they read that T&E is the abomination. The only thing that remains the abomination in this framework is guessing.


All the above chain/whip/braid patterns have two very important properties (defined in detail in the first posts of this thread), helpful in practice for finding them:
- they are non-anticipative, i.e. the validity of a partial whip/braid depends only on the previous candidates (and it can therefore be checked on-the-fly)
- they are composable, i.e. partial whips/braids can be linked together to make longer ones, with obvious compatibility conditions at the junction.


* Added 11/13/08
Definition: two candidates n1r1c1 and n2r2c2 are nrc-linked if they are different and:
- either n1=n2 and the 2 rc-cells r1c1 and r2c2 "see" each other (i.e. are in the same row, column or block)
- or n1 <> n2 and r1c1 = r2c2

"nrc-linked" defines the purely factual situation corresponding to the existence of a direct contradiction between 2 candidates. It is the main super-symmetric auxiliary predicate built on the basic ones.
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

Postby aran » Thu Nov 13, 2008 11:29 am

Denis

A few observations for your consideration

1. nrcxyzt-whips in rc-space

It seems to me that search for these useful chains could be incorporated into a human hand solver's tool-kit with the following approach :
a) select a target elimination candidate (z) in a cell C
b) select a source bivalue S containing z nrc-linked to C
b) mentally remove z from all cells to which C is nrc-linked other than S

Objective : find an xyt chain sourced from S producing an empty cell nrc-linked to C and from which z was removed in step a).
=> C <z>

2. A Paradox
let A be an xyt chain starting from a source bivalue (a,b)
=> your computer program has considered this chain regardless of whether it produces an elimination or not
Suppose there is xyt chain B of same length as A starting from the same source cell with its llc, rlc reversed : that is (b,a).
There may not be such a chain, but by supposition there is.
Assume that after examination by the program, neither chain produces an elimination.
That will be the end of the story within your rules.
But we know that any right link in either chain is strongly linked to any right link in the other chain.
Therefore when any right link of A is nrc-linked to any right link of B, there is elimination potential of two orders:
i) when the respective right-links are on the same digit
ii) when any non llr-digit in either cell is also a right-link in the other cell
The Paradox is this :
- these are potential eliminations which look to be easily available to your program
- you cannot accept them (so far as I can tell) because they have no formulation within your rules, or at a minimum not at that point in the process eg take the case where the respective cells have t candidates ie at least three candidates.
In other words, use of your rules generates opportunities for eliminations which you cannot accept because they are not "formulated" within the rules.
(Obviously B need not be same length as A, and the logic is valid whether there are eliminations or not).


I've also shown the close relationship between braids and Trial-and-Error (T&E) - the standard T&E procedure (which is not itself a resolution rule) with no guessing and no recursion: for any family FP, any elimination that can be done by T&E(FP) can be done by some zt-braid(FP). For players who use T&E for hard puzzles, this should soften their pain when they read that T&E is the abomination. The only thing that remains the abomination in this framework is guessing.

I still cannot see that this has any useful meaning (which is not at all intended to be disparaging about zt-braids)
aran
 
Posts: 334
Joined: 02 March 2007

Postby denis_berthier » Thu Nov 13, 2008 9:16 pm

aran wrote:1. nrcxyzt-whips in rc-space
It seems to me that search for these useful chains could be incorporated into a human hand solver's tool-kit with the following approach :
a) select a target elimination candidate (z) in a cell C
b) select a source bivalue S containing z nrc-linked to C
b) mentally remove z from all cells to which C is nrc-linked other than S
Objective : find an xyt chain sourced from S producing an empty cell nrc-linked to C and from which z was removed in step a).
=> C <z>

In rc-space, they are called simply xyzt-whips ;)
As a first approximation, it is not false, But mentally eliminating all the candidates nrc-linked to z may unduly eliminate potential left-linking candidates and you may miss some xyzt-chains.
If you want a better image of the z-candidate, just consider it as a 0-th right-linking candidate (with no previous left-linking one).

aran wrote:2. A Paradox
let A be an xyt chain starting from a source bivalue (a,b)
=> your computer program has considered this chain regardless of whether it produces an elimination or not
Suppose there is xyt chain B of same length as A starting from the same source cell with its llc, rlc reversed : that is (b,a).

Before I can answer, I need to know what is reversed.
If it is only a and b, then the resulting sequence of candidates may not even be a chain.
If it is the whole chain then it may not be an xyt-chain. (If it is, it is probably a mere xy-chain.)

aran wrote:
I've also shown the close relationship between braids and Trial-and-Error (T&E) - the standard T&E procedure (which is not itself a resolution rule) with no guessing and no recursion: for any family FP, any elimination that can be done by T&E(FP) can be done by some zt-braid(FP). For players who use T&E for hard puzzles, this should soften their pain when they read that T&E is the abomination. The only thing that remains the abomination in this framework is guessing.

I still cannot see that this has any useful meaning

Many players use T&E and purists usually look down on them.
My results show that any elimination done by T&E (the very precise form of T&E I've defined) can always be recast (and moreover in a constructive way) as a pattern-based elimination. The practical consequence is that using such form of T&E, you can't go beyond what the logic of resolution rules allows.
I was the first surprised by such results.

As braids are a very mild kind of nets (there is still a linear structure: candidates still form a sequence), another practical consequence is that, as soon as one accepts nets in a solution, one is not far from accepting T&E.
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

PreviousNext

Return to Advanced solving techniques