Universal Elimination Pattern for hard puzzles

Everything about Sudoku that doesn't fit in one of the other sections

Re: Universal Elimination Pattern for hard puzzles

Postby eleven » Fri May 10, 2013 11:22 am

So maximum 6 "truths" with (overall) 3 numbers per step ? That would be a nice result indeed.
eleven
 
Posts: 1534
Joined: 10 February 2008

Re: Universal Elimination Pattern for hard puzzles

Postby logel » Sun May 12, 2013 4:48 pm

Here you get finally an elimination example with some steps derived from planes and a full solution to make the picture complete.
It took some time to trim the full solution to (almost) human readable.

The chosen puzzle is the one eleven suggested. Its the one at the top of the hardest list.

Hidden Text: Show
Code: Select all
SUDOKU 98.7.....7.....6....6.5.....4...5.3...79..5......2...1..85..9......1...4.....3.2.
....
START P2_1 @ 9r9c3 IX=224 ##### +A
APPLY P2_1: S_9r9c3 E={943,963,982,983,992,193,493,593,995}
APPLY P2_1: T_N4C3B1 B1=[4c3] T={431} C={413,423} D={493}
APPLY P2_1: S_9r8c6 B1=[9r8] T={926,936,286,686,786,886} C={986} D={982,983}
APPLY P2_1: S_9r6c2 B1=[9c2] T={362,562,662,968} C={962} D={982,992}
APPLY P2_1: S_9r2c5 B1=[9c5] T={325,425,825,928,929} C={925} D={995}
APPLY P2_1: S_9r4c9 B1=[9r4] T={939,249,649,749,849} C={949} D={943}
APPLY P2_1: S_9r3c8 B1=[9c8] T={138,438,738,838} C={938} D={928,968}
APPLY P2_1: T2_N7R7C8B9_N7R6C6 B2=[7c6|7c8] T={779} C={766,768,776,778,788} D={738,786}
APPLY P2_1: PLANE_C3+C4 B6=[r4c3|r6c3|r8c3|1c4|2c4|3c4] T={513} C={124,...,284} D={943,963,983}
APPLY P2_1: T_N5R2B1 B1=[5b1] T={528,529} C={522,523} D={513}
APPLY P2_1: PLANE_C3+C4 B6=[r4c3|r6c3|r8c3|1c4|2c4|3c4] T={523} C={124,...,284} D={943,963,983}
APPLY P2_1: S_5r2c2 B1=[5b1] T={122,222,322,582,592} C={522} D={513,523}
APPLY P2_1: PLANE_N1+N2 B5=[r4c3|1c4|2c4|1b1|2b1] T={283} C={113,...,284} D={122,222,943}
APPLY P2_1: S2_R68C3_N35C3 B2=[r6c3|r8c3] T={313,323} C={363,563,383,583} D={963,283,983}
APPLY P2_1: T_N3R3B1 B1=[3b1] T={334,337,339} C={331,332} D={313,322,323}
APPLY P2_1: PLANE_N3 B3=[3r5|3c3|3c7] T={315} C={317,351,352,355,363,383,387} D={313,323,337}
APPLY P2_1: S_3r2c4 B1=[3b2] T={124,224,424,824,329,364} C={324} D={315,325,334}
APPLY P2_1: S_3r5c5 B1=[3c5] T={351,352,455,655,855} C={355} D={315,325}
APPLY P2_1: T2_N1R3C3B1_N1R4C4 B2=[1c3|1c4] T={131,132} C={113,123,134,143,144} D={124,193}
APPLY P2_1: S2B_R6C13_N35R6B4 B2=[3r6|5r6] T={661,861} C={361,561,363,563} D={362,562,364}
APPLY P2_1: T_N1C3B1 B1=[1b1] T={143} C={113,123} D={122,131,132}
APPLY P2_1: S_2r4c3 B1=[r4c3] T={213,223,241,247,251,252} C={243} D={143,943}
APPLY P2_1: S_2r5c9 B1=[2r5] T={219,229,239,659,859} C={259} D={251,252}
APPLY P2_1: T_N2R3B1 B1=[2b1] T={234,236,237} C={231,232} D={213,222,223}
APPLY P2_1: T_N6C8B6 B1=[6b6] T={678,688} C={658,668} D={649,659}
APPLY P2_1: S_2r2c6 B1=[2r2] T={216,126,426,826,276} C={226} D={222,223,224,229}
APPLY P2_1: S_8r2c9 B1=[r2c9] T={828,837,839,899} C={829} D={229,329,529,929}
APPLY P2_1: S_2r8c4 B1=[2c4] T={281,282,684,884} C={284} D={224,234}
APPLY P2_1: S_2r1c7 B1=[2b3] T={117,317,417} C={217} D={219,229,237,239}
APPLY P2_1: S_7r3c9 B1=[r3c9] T={737,799} C={739} D={239,339,839,939}
APPLY P2_1: T_N6R8B7 B1=[6r8] T={671,672,691,692} C={681,682} D={684,686,688}
APPLY P2_1: T_N8R9B8 B1=[8b8] T={897} C={894,895} D={884,886}
APPLY P2_1: S_3r1c9 B1=[3b3] T={519,379} C={319} D={317,329,337,339}
APPLY P2_1: S_3r8c7 B1=[3c7] T={381,382,383,787,887} C={387} D={317,337}
APPLY P2_1: S_5r1c8 B1=[5b3] T={118,418,588} C={518} D={519,528,529}
APPLY P2_1: S_5r9c9 B1=[5c9] T={591,699} C={599} D={519,529}
APPLY P2_1: S_6r7c9 B1=[r7c9] T={675,676} C={679} D={379,779}
APPLY P2_1: S_8r8c8 B1=[8b9] T={858,868,788} C={888} D={887,897,899}
APPLY P2_1: S_3r6c3 B1=[3c3] T={361,563} C={363} D={313,323,383}
APPLY P2_1: S_5r8c3 B1=[r8c3] T={581} C={583} D={283,383,983}
APPLY P2_1: S_7r8c2 B1=[7r8] T={772,682,792} C={782} D={786,787,788}
APPLY P2_1: S_6r8c1 B1=[r8c1] T={641,651} C={681} D={281,381,581}
APPLY P2_1: S_6r5c2 B1=[6c2] T={152,656,658} C={652} D={662,672,682,692}
APPLY P2_1: S_1r9c2 B1=[r9c2] T={171,172,191,197} C={192} D={592,692,792,992}
APPLY P2_1: T_N6R4B5 B1=[6r4] T={664,666} C={644,645} D={641,649}
APPLY P2_1: S_4r5c8 B1=[r5c8] T={428,456,467,468} C={458} D={658,858}
APPLY P2_1: S_6r6c8 B1=[6b6] T={768} C={668} D={649,658,659}
APPLY P2_1: S_1r7c8 B1=[1r7] T={778} C={178} D={171,172}
EMPTY P2_1: [7c8] D={738,768,778,788}

REDUCTION
REDUCE: S_9r9c3 T={943,963,982,983,992,193,995} C={} D={}
REDUCE: S_9r8c6 B1=[9r8] T={686,786,886} C={986} D={982,983}
REDUCE: S_9r6c2 B1=[9c2] T={662,968} C={962} D={982,992}
REDUCE: S_9r2c5 B1=[9c5] T={325,928,929} C={925} D={995}
REDUCE: S_9r4c9 B1=[9r4] T={649} C={949} D={943}
REDUCE: S_9r3c8 B1=[9c8] T={738} C={938} D={928,968}
REDUCE: PLANE_C3+C4 B6=[r4c3|r6c3|r8c3|1c4|2c4|3c4] T={513,523} C={124,...,284} D={943,963,983}
REDUCE: S_5r2c2 B1=[5b1] T={122,222,322,592,529} C={522} D={513,523}
REDUCE: PLANE_N1+N2 B5=[r4c3|1c4|2c4|1b1|2b1] T={283} C={113,...,284} D={122,222,943}
REDUCE: S2_R68C3_N35C3 B2=[r6c3|r8c3] T={313,323} C={363,563,383,583} D={963,283,983}
REDUCE: T_N3R3B1 B1=[3b1] T={334,337} C={331,332} D={313,322,323}
REDUCE: PLANE_N3 B3=[3r5|3c3|3c7] T={315} C={317,351,352,355,363,383,387} D={313,323,337}
REDUCE: S_3r2c4 B1=[3b2] T={124,224,329} C={324} D={315,325,334}
REDUCE: T2_N1R3C3B1_N1R4C4 B2=[1c3|1c4] T={131,132} C={113,123,134,143,144} D={124,193}
REDUCE: T_N1C3B1 B1=[1b1] T={143} C={113,123} D={122,131,132}
REDUCE: S_2r4c3 B1=[r4c3] T={213,223,251,252} C={243} D={143,943}
REDUCE: S_2r5c9 B1=[2r5] T={219,229,239,659} C={259} D={251,252}
REDUCE: T_N2R3B1 B1=[2b1] T={234,237} C={231,232} D={213,222,223}
REDUCE: T_N6C8B6 B1=[6b6] T={688} C={658,668} D={649,659}
REDUCE: S_8r2c9 B1=[r2c9] T={899} C={829} D={229,329,529,929}
REDUCE: S_2r8c4 B1=[2c4] T={684,884} C={284} D={224,234}
REDUCE: S_2r1c7 B1=[2b3] T={317} C={217} D={219,229,237,239}
REDUCE: T_N6R8B7 B1=[6r8] T={672,692} C={681,682} D={684,686,688}
REDUCE: T_N8R9B8 B1=[8b8] T={897} C={894,895} D={884,886}
REDUCE: S_3r8c7 B1=[3c7] T={787,887} C={387} D={317,337}
REDUCE: S_8r8c8 B1=[8b9] T={788} C={888} D={887,897,899}
REDUCE: S_7r8c2 B1=[7r8] T={682,792} C={782} D={786,787,788}
REDUCE: S_6r5c2 B1=[6c2] T={658} C={652} D={662,672,682,692}
REDUCE: S_1r9c2 B1=[r9c2] T={171,172} C={192} D={592,692,792,992}
REDUCE: S_6r6c8 B1=[6b6] T={768} C={668} D={649,658,659}
REDUCE: S_1r7c8 B1=[1r7] T={778} C={178} D={171,172}
REDUCE: CONTRA B1=[7c8] T={} C={738,768,778,788} D={738,768,778,788}

RESULT: B32=[r2c9|r4c3|r6c3|r8c3|r9c2|
     1r7|2r5|3r5|6r8|7r8|9r4|9r8|
    1c3|1c4|2c4|3c3|3c4|3c7|6c2|7c8|9c2|9c5|9c8|
    1b1|2b1|2b3|3b1|3b2|5b1|6b6|8b8|8b9]

This elimination pattern is large and consists of 32 base lines even after stripping off unnecessary parts. I do not claim that this is the smallest one (in terms of number of base lines). After assuming 9r9c3 any found only steps with 6 base lines or less were used. As singles, pairs are directly implemented, steps with planes only appear when all possible direct steps are exhausted. The first step with a plane set is:
Code: Select all
PLANE_C3+C4 B6=[r4c3|r6c3|r8c3|1c4|2c4|3c4] T={513} C={124,...,284} D={943,963,983}

After checking that candidate 513 is not member of any valid permutation of the candidates in columns C3+C4, the process looks for minimal pattern. This is done by finding odd loops inside C3+C4 starting from 513 and returning. If the loops cover a set of base lines, an elimination pattern is found. Patterns with more than 6 base lines are ignored according to the intended goal.
The step sequence continues and another pattern with 5 base lines from the two number planes N1+N2 is used. Beyond the single plane elimination from plane N3 there are only steps with at most two baselines.
The following reduced sequence is not necessary to assure solvability, but aggegates the level-one eliminations to a direct elimination. It is used as a cross check.

The full solution is here: http://www.logelium.de/zap/chdry_L5W6R.txt

All candidate are assumed in order from top left to bottom right. If a step sequence ends with "EDEAD", no elimination with any plane pair Nx+Ny, Rx+Ry, Cx+Cy, Bx+By or Nx+Ny+Nz is found. Then the sequence is run again ignoring eliminations with more than 6 base lines. This also ends with "EDEAD" if there is no continuation. Although the puzzle is the same as for the above elimination example, you will not find the above step sequence in the full solution. The example comes from an attempt to solve with plane pairs only, that does not solve completely. With additional plane triples of three number planes the puzzle becomes solvable and other eliminations are found earlier.
Some level-one sequences are very long, but each step of the sequence is of 6 base lines ore less. That was the only goal.
User avatar
logel
 
Posts: 55
Joined: 29 April 2012
Location: Germany

Re: Universal Elimination Pattern for hard puzzles

Postby logel » Sun May 12, 2013 5:38 pm

denis_berthier wrote:After re-reading our old discussion in the other thread, I think I better understand the "max 3 planes, max 6 base-lines".

Within each call to T&E(X6,3), each (local) elimination is based on a pattern that can only involve 6 CSP-variables/2D-cells/base-lines p1q1, ..., p6q6 where:
1) each pi and qi are a digit, a row, a column or a block (so that piqi is some rc, rn, cn or bn 2D-cell)
2) and there are 3 planes, i.e. 3 objects o1, o2, o3 of type digit, row, column or block such that each of p1q1, ..., p6q6 has its pi or qi equal to one of o1, o2, o3.

Can you confirm?
If this is wrong, then I've completely misunderstood your approach.

What's still totally unclear - and this is essential for evaluating the strength of your result - is:
Within a fixed call to T&E, the p1q1, ..., p6q6 can of course be different for each (local) elimination. But can the o1, o2, o3 be different or are they a constant of each T&E call?


I try to understand what "constant" could mean in your question. With each step in the T&E sequence various plane sets will be used.
A single plane selection is by far too limited to produce a contradiction sequence.

I feel "3 objects o1, o2, o3" is a bit too abstract. Maybe an example explains better:
Consider the plane tripel N1+N2+N3 consisting of all candidates with number 1 or 2 or 3. This plane triple is governed by these constraints / CSP variables:
    all rows of number 1,2,3
    all colums of number 1,2,3
    all boxes of number 1,2,3
    cells containing at least two candidates of number 1,2,3
The cells connecting the single number planes are important, because the cell constraints restrict the permutations of the number planes. The set of all valid permutations of the plane triple can be seen as the set of all multiple solutions of the partial puzzle in N1+N2+N3. All candidates appearing in none of the permuations ( partial solutions ) are subject for elimations. But if we look only for elimination with 6 or less base lines, only some (maybe none) of them can be used. Only the above stated base lines can determine an elimation of the plane triple N1+N2+N3. Addionally a connecting cell call only serve as base line if the cell is "naked" (only 1,2,3).
If the potential of eliminations from N1+N2+N3 is exhausted, so other planes, plane pairs/triple are used in later T&E steps.

Another example of a plane pair R1+R5:
    rows 1 for all numbers
    rows 5 for all numbers
    all cells in row 1 and 5
    all colums of any number with intersections in row 1 and 5 (connection)
Altough plane pairs/triples of row/column/box planes are less powerful in finding eliminations, they seem necessary for the size-6-goal.
Hope that answered your question. Also see the example just posted.
User avatar
logel
 
Posts: 55
Joined: 29 April 2012
Location: Germany

Re: Universal Elimination Pattern for hard puzzles

Postby eleven » Sun May 12, 2013 7:03 pm

logel wrote:...If a step sequence ends with "EDEAD", no elimination with any plane pair Nx+Ny, Rx+Ry, Cx+Cy, Bx+By or Nx+Ny+Nz is found...

Would you please finally say, what you mean with "max. 3 planes" ? Is it that, one of Nx+Ny, Rx+Ry, Cx+Cy, Bx+By or Nx+Ny+Nz ?
...but each step of the sequence is of 6 base lines ore less. That was the only goal.

Now with or without "max. 3 planes" (for all puzzles in the hardest list) ?

However, a quick view showed some nice eliminations in your output.
Concerning "Champagne dry" the best area to attack it seems to be the almost 59's and 68's in c3 and c4 (r4689), with common "extra candidates" 1234.
eleven
 
Posts: 1534
Joined: 10 February 2008

Re: Universal Elimination Pattern for hard puzzles

Postby logel » Sun May 12, 2013 9:17 pm

hi eleven
eleven wrote:So maximum 6 "truths" with (overall) 3 numbers per step ? That would be a nice result indeed.


The term truth coming from xsudo is not exactly the same as base line I am using. I think base line is what Alan called native truth, just to be precise. In all common examples only native truth appear, so we probably talk about the same thing.

"Maximum 6 base lines (truth) with 3 numbers per step" was what I hoped for, but I proved that it is not possible with some hard puzzles. Of course "three numbers per step" means that each step can have 3 different numbers.
Its even impossible to solve with "any number of base lines with 3 numbers per step" generally.

This negative result motivated me to look for other conditions for the steps, restricted as possible, but powerful enough to solve all in the hardest list. So I added steps restricted to 2 or 3 rows/columns/boxes and their base lines (truth). I found that all except ~300 are solvable with "maximum 6 base lines of ( 2 numbers OR 2 rows OR 2 columns OR 2 boxes ) per step". The rest were solvable with set of three such planes, but a handful also needed special ones like "2 boxes and one row". So the final result was "it works with steps of 6 base lines (truth)", but was a bit disappointing too.

eleven wrote:E.g. if - after trying (placing) the target candidate - there is an ALS xz elimination with an almost triple and an almost quad. How many "baselines" does that count ? Or a 6 cell bivalue chain ?
And "max 3 planes" means what ? Why does the example only need max. 3 planes, and what would be an example of 4 planes ?

A sequence with ALS steps with "an almost triple and an almost quad" count 3 and 4 base lines, if these are the only steps. A straight chain of 6 linked bivalue cells counts 6.

Why not 4 planes? I did not try yet. Probably needs much more computation time. And I do not expect to solve with 5 base lines (truth) per step. I also observed that you need less steps until contradiction if you allow 7 base lines per step. But its only an observation, not enough data to be sure about. Even more compelling is the decrease of the number of necessary contradiction sequences until only direct eliminations solve the rest, if you allow 7 or 8 base lines per step. Although my goal was not producing "simple" solutions (by whatever terms), using steps with 6 base lines is not at all a golden path to simple solutions.


PS: I also use the term base set for the set of all base lines of an elimation pattern. Xsudo use base set sometimes synonym for truth. Maybe confusing too.
User avatar
logel
 
Posts: 55
Joined: 29 April 2012
Location: Germany

Re: Universal Elimination Pattern for hard puzzles

Postby eleven » Sun May 12, 2013 11:05 pm

Can i formulate it this way:

The "base lines" either refer to the (still possible) candidate placements in a cell [though line is a really bad name for it] or the possible placements of a single digit (number) in a row, a column or a box.

When you say, that a candidate is eliminated by 6 baselines, then it means, that placing the candidate leads to a contradiction in these baselines (i.e. they cannot be fulfilled together), after the same digit in the candidates' units (row, column, box) is killed in the baselines.

And planes are restrictions to these baselines, N planes means, that they either only have N digits or they are covered by only N units.


And you have solved all puzzles in the hardest list with eliminations of candidates, which were assumed and then proven false, by consecutive elimination steps, which maximum needed 6 baselines and 3 planes. Did i get it ?
eleven
 
Posts: 1534
Joined: 10 February 2008

Re: Universal Elimination Pattern for hard puzzles

Postby denis_berthier » Mon May 13, 2013 6:09 am

logel wrote:Hope that answered your question. Also see the example just posted.

Sorry, but the main ambiguity remains and I don't think one should have to browse what is mainly a (manually cleaned) T&E(2) listing for finding the answer.
My question was simple and I expected a simple answer. So let me cut it into two pieces, with only binary answers.

Your resolution path is a sequence of eliminations of candidates C1, C2, ... (forgetting the Singles).
Each elimination Ci is done by a call to a T&E(X3,6) procedure based on Ci, i.e. in which Ci is assumed to be true - where X3,6 is some set of patterns restricted in some way by two parameters 3 and 6 (how the restriction is done is not the topic of this question).
Do you agree with this? Possible answers: True/False
If False, forget the sequel, I'm completely lost and I give up.

My next question bears on ONE of these eliminations: Ci, i fixed.
This Ci is itself a sequence of eliminations Ci,j (again forgetting the Singles) [of course, these eliminations don't apply to the initial puzzle; they are local to Ci].
When you say that patterns used for the elimination of Ci (i.e. for each Ci,j step) are restricted to 3 "planes", do you mean that the 3 "planes" are the same for all the Ci,j (i fixed) or that they can be different for different Ci,j (i.e. different j's, i fixed).
Possible answers: same/different.
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

Re: Universal Elimination Pattern for hard puzzles

Postby logel » Tue May 14, 2013 10:54 pm

eleven wrote:Can i formulate it this way:

The "base lines" either refer to the (still possible) candidate placements in a cell [though line is a really bad name for it] or the possible placements of a single digit (number) in a row, a column or a box.

When you say, that a candidate is eliminated by 6 baselines, then it means, that placing the candidate leads to a contradiction in these baselines (i.e. they cannot be fulfilled together), after the same digit in the candidates' units (row, column, box) is killed in the baselines.

And planes are restrictions to these baselines, N planes means, that they either only have N digits or they are covered by only N units.


And you have solved all puzzles in the hardest list with eliminations of candidates, which were assumed and then proven false, by consecutive elimination steps, which maximum needed 6 baselines and 3 planes. Did i get it ?


Thats what it is. Correct.

About the term line: What would be better?
If you visualize an elimination with xsudo in 3D mode, you find the line objects drawn as straight lines in the 3D model (besides the special problems with boxes). Also the term plane is anologous to the geometric planes in the 3D model.
User avatar
logel
 
Posts: 55
Joined: 29 April 2012
Location: Germany

Re: Universal Elimination Pattern for hard puzzles

Postby logel » Wed May 15, 2013 1:00 am

denis_berthier wrote:Your resolution path is a sequence of eliminations of candidates C1, C2, ... (forgetting the Singles).
Each elimination Ci is done by a call to a T&E(X3,6) procedure based on Ci, i.e. in which Ci is assumed to be true - where X3,6 is some set of patterns restricted in some way by two parameters 3 and 6 (how the restriction is done is not the topic of this question).
Do you agree with this? Possible answers: True/False
If False, forget the sequel, I'm completely lost and I give up.

True
denis_berthier wrote:My next question bears on ONE of these eliminations: Ci, i fixed.
This Ci is itself a sequence of eliminations Ci,j (again forgetting the Singles) [of course, these eliminations don't apply to the initial puzzle; they are local to Ci].
When you say that patterns used for the elimination of Ci (i.e. for each Ci,j step) are restricted to 3 "planes", do you mean that the 3 "planes" are the same for all the Ci,j (i fixed) or that they can be different for different Ci,j (i.e. different j's, i fixed).
Possible answers: same/different.

same
But now I am confused because the alternative answer "different" makes no sense to me. Moreover you said
denis_berthier wrote:This Ci is itself a sequence of eliminations Ci,j

Although this is not wrong, it does not conform to the leading idea. In the in initial post I gave arguments that all (constraint driven) eliminations can be expressed by a set of baselines. So each step Ci should be specified by some base lines. T&E is one method among others to find the baselines of an elimination. Also the listing shows no T&E(2), its all T&E(1) including all failed sequences. So I feel there is still something odd.

You can apply eliminations derived from planes or plane sets at the global level or on T&E(1) level. Its always the same procedure.
I give an example at global level to simplify the context. The solver uses only planes and plane pairs.
Code: Select all
000400100080020090007005006400001700090000030002000008000090020005300000010007004

APPLY ROOT: S2_R4C49_N29R4 E={544,644,844,549}
APPLY ROOT: PLANE_N2 B3=[2r1|2r4|2r9] T={231} D={}

+------------------------+------------------------+------------------------+
|23569   2356    369     |4       3678    3689    |1       578     2357    |
|1356    8       1346    |167     2       36      |345     9       357     |
|139     234     7       |189     138     5       |2348    48      6       |
+------------------------+------------------------+------------------------+
|4       356     368     |29      3568    1       |7       56      29      |
|15678   9       168     |25678   45678   2468    |2456    3       125     |
|13567   3567    2       |5679    34567   3469    |4569    1456    8       |
+------------------------+------------------------+------------------------+
|3678    3467    3468    |1568    9       468     |3568    2       1357    |
|26789   2467    5       |3       1468    2468    |689     1678    179     |
|23689   1       3689    |2568    568     7       |35689   568     4       |
+------------------------+------------------------+------------------------+

+------------------------+------------------------+------------------------+
|                        |4                       |1                       |
|1               14(*)   |1                       |4                       |
|1       4               |1       1               |(4)       4             |
+------------------------+------------------------+------------------------+
|4                       |                1       |                        |
|(1)             1       |        4       4       |4               1       |
|1                       |        4       4       |4       14(*)           |
+------------------------+------------------------+------------------------+
|        4       4       |1               4       |                1       |
|        4               |        14*     4       |        1       1       |
|        1               |                        |                4       |
+------------------------+------------------------+------------------------+
APPLY ROOT: PLANE_N1+N4 B4=[1r6|4r2|1c3|4b6] T={151}  D={}
APPLY ROOT: PLANE_N1+N4 B4=[1r6|4r2|1c3|4b6] T={437} D={}
APPLY ROOT: CONN_N1+N4 B4=[1r6|4r2|1c3|4b6] T={323,623}  D={}
APPLY ROOT: CONN_N1+N4 B4=[1r6|4r2|1c3|4b6] T={568,668}  D={}

Skipping the first two eliminations, a pair and a 3-queue, the first diagram shows the situation afterwards. The second shows the plane set N1+N4 with only numbers 1,4 and *. The star symbol indicates that the cell contains more candidates, otherwise the contraint in the cells containing both 1 and 4 would be wrong. The second diagram constitutes a sudoku-like puzzle where the usual methods can be applied to find eliminations.
From the initialisation phase (skipping how this is done) I know that the N1+N4 puzzle has 16 "multiple solutions" from the start. The two eliminations until now did not change this. To avoid confusion with the global solution they are called valid permutations. One of the 16 valid permutations is matching the unique final solution of the whole sudoku. The candidates 1r5c1 and 4r3c7 are not part of any of the 16 valid permutations and therefore not part of the final solution. This check is done by simple comparison (without any T&E) and very cheap even if the number of permutations is larger. The candidates marked by stars in the cells r2c3 and r6c8 are also elimination candidates, because another permutation check verifies that either 1 or 4 is true for all valid permutations. So the N1+N4 planes generates 6 eliminations (put in parenthesis). Theres is no elimination for all other candididates inside N1+N4.
Up to now nothing is known about the size of these eliminations. As all eliminations are determined by a set of baselines the size is determined after finding the base set. This can be accomplished by T&E after setting the eliminmation candidate true or like in this case by mapping on a traditional pattern. All six eliminations are bound in a nice loop of size 4.
There are various possible base sets: B4=[1r6|4r2|1c3|4b6] or [1r6|4r2|1c3|4c8] or [1r6|4r2|1b1|4c8] or [1r6|4r2|1b1|4b6] ...

Next planes:
Code: Select all
APPLY ROOT: PLANE_N2+N9 B3=[r4c4|2r9|9r3] T={991}  D={544,644,844}
APPLY ROOT: PLANE_C7+C8 B7=[r3c8|r4c8|r9c8|2c7|4c7|6c7|8c7] T={688}  D={437}

The plane pair N2+N9 has only 9 valid permutations and produces 1 elimination of size 3. The plain pair C3+C8 has 73 valid permutations and and elimination of size 7. In this case the baselines are determined by a T&E sequence.
After this point none of the 36 single plains and none of the 126 plaine pair can justify any more eliminations. One can now switch to plane triples or to T&E(1) using the same permutation tables. All valid permutations are generated only once and reused with all sequences. The number of valid permutations of plane sets can only shrink with candidates eliminated. In this example the total number of valid permutations of all plane sets is 251355.
User avatar
logel
 
Posts: 55
Joined: 29 April 2012
Location: Germany

Re: Universal Elimination Pattern for hard puzzles

Postby denis_berthier » Wed May 15, 2013 2:38 am

Hi logel,

Thanks for your answer. The T&E(X3,6) result is now compatible with what I had understood in the other thread.

There are still three points:
- as you've accepted that the CSP-variables/2D-cells/base-lines should be given at the start, can you re-write your definition of a pattern accordingly?
- can you give an idea of what's the main difference with Allan's approach (if any)?
- how do you think your approach would scale up to any puzzle if you gave up using a T&E layer?
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

Re: Universal Elimination Pattern for hard puzzles

Postby logel » Mon May 20, 2013 11:52 pm

Hi Denis, its time for a little summary.
denis_berthier wrote:Thanks for your answer. The T&E(X3,6) result is now compatible with what I had understood in the other thread.

There are still three points:
- as you've accepted that the CSP-variables/2D-cells/base-lines should be given at the start, can you re-write your definition of a pattern accordingly?

The definition of universal pattern needs re-writing and was not well explained too. The discussion brought new insights. So another definition version should come along with more results. No need to hurry.
denis_berthier wrote:- can you give an idea of what's the main difference with Allan's approach (if any)?

To be true, I never fully understood Allan's approach. Besides the use of base sets as main property of eliminations there is not much in common. I remember Allan's statement some years ago about the strategy to chose the next elimination. He said he is looking for "interesting" eliminations. That means his approach is mainly pragmatic. In contrast I try follow a systematic strategy and go for completeness, at least for partial aspects. Computation time is not first priority.
denis_berthier wrote:- how do you think your approach would scale up to any puzzle if you gave up using a T&E layer?

T&E layer is always a fall back method only, if all else fails. Although its possible to reengineer T&E layer to direct eliminations, the effort to sort out reasonable small eliminations from T&E is huge. Direct eliminations from plane triples achieve little on very hard puzzles. 4-plane-sets are already very difficult to analyze completely. But I still have some more promising ideas, although it always ends with more time than expected to implement the ideas.
User avatar
logel
 
Posts: 55
Joined: 29 April 2012
Location: Germany

Re: Universal Elimination Pattern for hard puzzles

Postby denis_berthier » Tue May 21, 2013 6:26 am

Hi logel,

logel wrote:
denis_berthier wrote:- as you've accepted that the CSP-variables/2D-cells/base-lines should be given at the start, can you re-write your definition of a pattern accordingly?

The definition of universal pattern needs re-writing and was not well explained too. The discussion brought new insights. So another definition version should come along with more results. No need to hurry.

Clarifying your definition doesn't require more results. But if that's your decision, we'll wait.
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

Previous

Return to General