The Illusion of Fata Morgana

Advanced methods and approaches for solving Sudoku puzzles

Postby champagne » Tue Oct 07, 2008 11:37 pm

David P Bird wrote:As an AIC puritan I consider a node to be a Boolean condition that can either be true or false which can be linked by inferences (but I'll accept edges).


This is somehow funny. This is not the way I started, but this is exactly the final definition of a "tag".

For Allan, "tagging" is clearly belonging to the coloring family. I wanted a specific word for the same reasons some wanted "strong inference" instead of "strong lnk". The word coloring had been extensively used for as different tolls as "forcing chains" , AICs ....

I looked for a specific word and came to "tag" which was short and not to far from the coloring underlying concept.

at that time a "tag" could be

. a candidate
. a group of candidates belonging to two "units", "sets".

I think I would have been better inspired choosing a specific word instead of "group" which is, in a wider scope, any set of candidates among which one at most is valid. In fact I am only interested by tagged groups, so I can manage it.

In Allan process, I have been in trouble for sure due the the confusion on "node", but the use of "set" for any of {row;column;box,cell/Node} makes it a forbidden usefull word for discussions.

Nothing really important, and likely to late to change anyway.

champagne
champagne
2017 Supporter
 
Posts: 5610
Joined: 02 August 2007
Location: France Brittany

Postby champagne » Wed Oct 08, 2008 1:39 am

Hi Allan,

I worked on your process to build potential set/link sets patterns. I got good results that I’ll share with you in PM. I don’t think many others are interested in that part of your concept which is more dedicated to computers trying to simulate players looking for relevant patterns.

What seems important to me is that you came to the strategy to look for “dense logic”, and this is certainly what players do. When strmckr says “I have a flavor of …” It relates to some form of ”dense logic” he identified.

I have seen at least one player applying on candidates of the same digit something not formalized, but very similar to your permutation process. I am sure that using your “sets/link sets” rules he would have been more convincing that this was pure logic.,

Just to summarize quickly where I am with the focusing phase on floors 1;3;6 of FataMorgana


Global view gave :17 clearings out of 112 sets.

Building groups of sets following your guidelines, I found:

A strong incentive to look first the clearing of 23r4c2 (loop FM1) with about 65 sets at the moment against 25 in your loop. This means a “slim fast” program seems unavoidable but likely based on the same criteria as you used in the first part (reduction on the number of permutations, number of extra candidates eliminated…)

A maximum of permutations exceeding 3000 in the worst situation,

An interesting 68 sets group giving clearings not including 24r4c2.

I’ll sent you detailed data on these preliminary results


champagne
champagne
2017 Supporter
 
Posts: 5610
Joined: 02 August 2007
Location: France Brittany

Postby Allan Barker » Wed Oct 08, 2008 5:07 am

Champagne wrote:Building groups of sets following your guidelines, I found:

A strong incentive to look first the clearing of 23r4c2 (loop FM1) with about 65 sets at the moment against 25 in your loop.


Good work! This all sounds very correct now. I also found that FM loop 1 is a very strong attractor (it wants to come out first). I have 59 sets before my "slimfast" and then get the 25 sets.

Champagne wrote:This means a “slim fast” program seems unavoidable but likely based on the same criteria as you used in the first part (reduction on the number of permutations, number of extra candidates eliminated…)


Some kind of slimming is necessary. Retesting one set at a time will work except for the toughest problems. I will get you a description of my "perma_strip" algorithm. It works without fully retesting each set, but cannot completely avoid complexity.

Champagne wrote:A maximum of permutations exceeding 3000 in the worst situation,


I got 12454 permutations max, which is unusually high, but I started with more sets. 3000 is usually a max for most monster work. Even really tough puzzles can have 10 to 100 permutations. A factor of 2 or 4 is almost nothing.

Champagne wrote:An interesting 68 sets group giving clearings not including 24r4c2.


This seems consistent with FM. Starting from loop 1, then adding a few more sets can produce several different solutions.

I will take a look at your data.

Allan
Allan Barker
 
Posts: 266
Joined: 20 February 2008

Postby StrmCkr » Wed Oct 08, 2008 5:53 pm

What seems important to me is that you came to the strategy to look for “dense logic”, and this is certainly what players do. When strmckr says “I have a flavor of …” It relates to some form of ”dense logic” he identified.

I have seen at least one player applying on candidates of the same digit something not formalized, but very similar to your permutation process. I am sure that using your “sets/link sets” rules he would have been more convincing that this was pure logic.,


am i to surmise i found something but couldnt display it in some formalized logic sence? but it was valid??
Some do, some teach, the rest look it up.
User avatar
StrmCkr
 
Posts: 624
Joined: 05 September 2006

Postby Allan Barker » Wed Oct 08, 2008 8:01 pm

Did you node this?

Jeff's Forcing chains: Terminology and Definition thread wrote:Node - a cell or a group of cells joining 2 links in a chain propagation. A node is multi-valued and may contain any number of candidates.

SuDoPedia wrote:Node A node is an item in a chain or loop. It can be a cell, a candidate or a complex structure like an Almost Locked Set.
The nodes are connected with links or edges.


I think Jeff's intent was to define node, and other terms, with respect to forcing chains, nice loops, etc, and his set of definitions has served as a backbone to Sudoku ever since.

All that is fine. However, the idea that nodes are cells is probably the main source of confusion between traditional views and other perspectives like dimensionless logic or 3D. When "cell" nodes are applied to 3D, they are sets. Then by symmetry, row, column, and box sets also become nodes leading to a confused picture where links can be nodes and nodes can be links.

Nice loops, below, make a good example. In 3D, color bars are strong sets and white bars are weak sets. Labels are relative to the traditional 2D grid perspective where some candidates and links are lumped together. Left, continuous nice loop, right, discontinuous nice loop.

Image

Edit: combined images, touchup.
Last edited by Allan Barker on Thu Oct 09, 2008 1:35 am, edited 1 time in total.
Allan Barker
 
Posts: 266
Joined: 20 February 2008

Postby ronk » Thu Oct 09, 2008 4:11 am

Allan Barker wrote:When "cell" nodes are applied to 3D, they are sets.

As applied to Sudoku, 2-D graph theory has vertices (nodes) at the intersections of rows and columns. Lines between vertices are called edges (links).

The cell term was originally used in lieu of node. Then node was adopted for "one or more cells" so as to incorporate grouped candidates, e.g., Almost Locked Sets and single-digit groups. The inference term was adopted in lieu of link because conflicting definitions were already established for both strong link and weak link.

Jeff's work was heavily influenced by David Eppstein's paper on "Nonrepetitive Paths and Cycles in Graphs with Application to Sudoku" - 20 Jul 2005. Although quite dated, I recommend reading the Introduction and section "3 Sudoku" to anyone who hasn't already done so.

Eppstein's examples were either wholly bilocation graphs or wholly bivalue graphs. AFAIK Jeff and a handful of others were primarily responsible for combining the bilocation and bivalue concepts on one graph ... and it's from this that Nice Loops were born.

All the above is a long-winded introduction to saying that "3-D Sudoku" should have strong ties to 3-D graph theory. Unfortunately, no one has done so ... ala the Eppstein paper above. I'm certainly not qualified to do so, but I do have some strongly held notions ...

As applied to Sudoku, 3-D graph theory would have vertices (nodes) at intersections of the number, row and column dimensions (nrc*)... and any line between any two vertices would still be an edge (link). *Since many people are accustomed to writing (3)r2c5 or 3r2c5, "nrc" is better than "rcn".

Then every cell (intersecting all 'n') and every 'nr', 'nc' and 'nb' intersection is a "linkset." Your "set" becomes "strong linkset" and your "linkset" becomes "weak linkset."

David P Bird, using the 3-D point-of-view I agree that a candidate is a node.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby ttt » Mon Oct 27, 2008 5:47 am

Hi Allan & champagne,
As manual solver, for Allan’s first move of Fata Morgana – great idea, I like to present it based on [(13)=(16)=(36)]r5c46, it’s not difficulty for presenting but hard for nice. I’ll present it by that way later…
For Tungsen Rod: based on [(15) (17) (57)]r56c6 is not only r4c45<>5, but also r56c5<>5.

BTW, I don’t see anything relate to SK loop on your deductions (or I missed something… Vodka is good for eyes…:D ?)

ttt
ttt
 
Posts: 185
Joined: 20 October 2006
Location: vietnam

Postby champagne » Mon Oct 27, 2008 6:09 am

ttt wrote:Hi Allan & champagne,
BTW, I don’t see anything relate to SK loop on your deductions (or I missed something… Vodka is good for eyes…:D ?)

ttt


Hi ttt

Allan has an extended definition of SK loop. I agree with you, this is not a SK loop:D

Nothing important. It is a nice move and something players can handle.
champagne
2017 Supporter
 
Posts: 5610
Joined: 02 August 2007
Location: France Brittany

Postby Allan Barker » Mon Oct 27, 2008 5:01 pm

ttt wrote:For Tungsen Rod: based on [(15) (17) (57)]r56c6 is not only r4c45<>5, but also r56c5<>5.


ttt, thanks, it seems I found a partial solution, which happens some times. I went back and found this (loop) that eliminates all
four 5s. I post the diagram and images because the loop is interesting. It has a rank of 5 (8 sets + 13 linksets) but all the triplets increase the rank to 0 in the center box linkset to eliminate al other fives. A very clean example of rank. You probably have a simpler way, I would be very interested to compare because I don't think humans think to much about rank (takes HCMC vodka ??)

These are not SK loops, but I don't know what to call them as a class, so I just say SK like. What they seem to have in common is they are rank 0 or have a rank 0 part. After the loops are removed, rank 0 is rarely seen in monsters until the end.

Code: Select all
TUN2 26 Nodes, Rank 5:
     8 Sets = {1r248 7r248 56n6}
     13 Links = {1c367 7c367 2n5 4n37 8n4 157b5}
     --> (5b5) => r4c4<>5, (5b5) => r4c5<>5, (5b5) => r5c5<>5, (5b5) => r6c5<>5


1R8:                186===========================183============184 
                     |                             |              |   
1R2: 125============126============127             |              |   
      |              |              |              |              |   
1R4:  |              |   144=======147C=147C======143A=143A       |   
      |              |   145             |              |         |   
      |              |    |              |              |         |
6N6:  |   766H=766H=166G=166G=566        |              |         |   
      |    |    |    |    |    |         |              |         |   
5N6:  |   756F=756F=156E=156E=556        |              |         |   
      |    |    |              |         |              |         |
7R4:  |    |   744=============|========747D=747D======743B=743B  |   
      |    |   745             |              |              |    |   
      |    |                   |              |              |    |   
7R2: 725==726==================|==============|=============723   |   
           |                   |              |                   |   
7R8:      786==================|=============787=================784 
                               |
                               X = r4c45<>5, r56c5<>5.
'=' strong set, '|' weak link
 Note: 766H=766H is same candidate in 2 weak links, i.e., triplet, weak corner


Note: White-sets are linksets, Black white-sets are rank 0 linksets.
Thunbs to grid images:
ImageImage
Allan Barker
 
Posts: 266
Joined: 20 February 2008

Postby ronk » Mon Oct 27, 2008 6:14 pm

Allan, I suggest using the linkset handles as column headers ... as shown below. I can figure them out, but having the headers already there would help ... at least a little. (I assume you're not generating these by hand.:) )
Code: Select all
     2N5  7C6  7B5  1C6  1B5  5B5  1C7  4N7  7C7  1C3  4N3  7C3  8N4

1R8:                186===========================183============184 
                     |                             |              |   
1R2: 125============126============127             |              |   
      |              |              |              |              |   
1R4:  |              |   144=======147C=147C======143A=143A       |   
      |              |   145             |              |         |   
      |              |    |              |              |         |
6N6:  |   766H=766H=166G=166G=566        |              |         |   
      |    |    |    |    |    |         |              |         |   
5N6:  |   756F=756F=156E=156E=556        |              |         |   
      |    |    |              |         |              |         |
7R4:  |    |   744=============|========747D=747D======743B=743B  |   
      |    |   745             |              |              |    |   
      |    |                   |              |              |    |   
7R2: 725==726==================|==============|=============723   |   
           |                   |              |                   |   
7R8:      786==================|=============787=================784 
                               |
                               X = r4c45<>5, r56c5<>5.
'=' strong set, '|' weak link
 Note: 766H=766H is same candidate in 2 weak links, i.e., triplet, weak corner
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby Allan Barker » Mon Oct 27, 2008 10:01 pm

ronk wrote:Allan, I suggest using the linkset handles as column headers ... as shown below. I can figure them out, but having the headers already there would help ... at least a little. (I assume you're not generating these by hand.:) )


OK, easy, I have printed them before. Thanks for filling this one in.
Allan Barker
 
Posts: 266
Joined: 20 February 2008

Postby champagne » Mon Oct 27, 2008 10:13 pm

Hi ttt Allan... and strmckr,

I knew that strmckr had some "flavouring" about tugston rod and Platinium Blonde.
Reading Allan post, I had the temptation to check what is the "flavouring" of my solver regarding theese two.

Code: Select all
000000007020400060100000500090002040000800600600900000005003000030080020700004001#Tungston Rod    #


Code: Select all
34589 4568  34689  |12356 123569 15689 |24    1389  7   
3589  2     3789   |4     13579  15789 |1389  6     389 
1     4678  346789 |2367  23679  6789  |5     389   24   
--------------------------------------------------------
358   9     1378   |13567 13567  2     |1378  4     358 
2345  1457  12347  |8     13457  157   |6     13579 2359
6     14578 123478 |9     13457  157   |12378 13578 2358
--------------------------------------------------------
2489  1468  5      |1267  12679  3     |4789  789   4689
49    3     1469   |1567  8      15679 |479   2     4569
7     68    2689   |256   2569   4     |389   3589  1   

floors157 is the only active group (seen by my solver) combining three floors
I found 29 valid permutations this seems to be an order of magnitude for pattern leading to good results (same in Fata Morgana)

Active sets were (65)
Code: Select all
N:.........................................X........X..............................
R:XX.XXXXX............................XX.XXX.XX..........XXXXXXX...................
C:.XXXXXXX............................XX.XXX.XX..........XXXXXXX...................
B:.XXXXXXX............................XX.XXX.XX.........XX.XXX.XX..................
  1        2        3        4        5        6        7        8        9   

Cells/Nodes with extra candidates (not used)
Code: Select all
HCxx.xxx.x.x.x.xxx...xxxxx...x.xxx.x.xxxx.x..xx.xx.x.xxx.x.xx.xx...xx.xx.x...xx..x.

And the possible clearing (still Allan duty to find relevant loops)
Code: Select all
5: r1c146 r2c6 r4c45 r5c159 r6c59 r8c6 r9c5
7: r3c36r7c7
NE.............x....................................................x..............


Allan loop found
5r4c45 5r5c5 5r6c5

for sure, there are many other possibilities



Code: Select all
000000012000000003002300400001800005060070800000009000008500000900040500470006000 platinium blonde

Code: Select all
35678 34589 34679 |4679   5689   4578   |679    1      2     
15678 14589 4679  |124679 125689 124578 |679    56789  3     
15678 1589  2     |3      15689  1578   |4      56789  6789 
------------------------------------------------------------
237   2349  1     |8      236    234    |23679  234679 5     
235   6     349   |124    7      12345  |8      2349   149   
23578 23458 347   |1246   12356  9      |12367  23467  1467 
------------------------------------------------------------
1236  123   8     |5      1239   1237   |123679 234679 14679
9     123   36    |127    4      12378  |5      23678  1678 
4     7     5     |129    12389  6      |1239   2389   189   

nothing before combinaison of four floors and only one active

Code: Select all
floors4679  permutations =49 (not that high)
N:...X..X....X...X.................................................................
R:...........................XX.XXXX...........XXXX.XXX.XXXX.XXX..........XXXXX.X.X
C:............................XXX.X.XX.........X.XXX.XXXX.XX.XXXX..........XXXX.XXX
B:...........................XX.XXX..X.........XXX.XXX.XXXXX.X.XX.........XXXX.X.XX
  1        2        3        4        5        6        7        8        9       
HCxxx.xx...xx.xxx.x.xx..xx.xxxx..xxxx...xx.x.xxxxxxx.xxxx...xxxxx..xx.x.xx...xx.xxx

but several possibilities that can explain the "flavouring" of strmckr.

Code: Select all
4: r4c8r5c46r6c2
6: r6c57
7: r12c1r4c7r6c17r8c68
9: r12c5r7c7r9c57
NE..x.........x.....................x...x.........x............xx..................
champagne
2017 Supporter
 
Posts: 5610
Joined: 02 August 2007
Location: France Brittany

Postby Allan Barker » Tue Oct 28, 2008 5:44 am

A must see

Champagne,

Congratulations, this is the world's first rank 29 elimination, with 20 sets and 49 linksets. It eliminates 16 candidates.

Image

Code: Select all
TUXX 75 Nodes, Rank 29:
     20 Sets = {56n6 1b234678 5b124689 7b124689}
     49 Links = {1r1245678 5r1245689 7r2345678 1c2345678 5c1245689 7c2345678 2n5 4n37 8n4 157b5}
     r1c1<>5, r1c4<>5, r1c6<>5, r2c5<>3, r2c5<>9, r2c6<>5,
     r4c4<>5, r4c5<>5, r5c1<>5,
     r5c5<>5, r5c9<>5, r6c5<>5, r6c9<>5,
     r8c4<>6, r8c6<>5, r9c5<>5


However, what you gave me for Tungsten Rod is 3 complete floors + 2 N cell sets. This does not cause any eliminations. I added 4 more linksets to make eliminations. So far, none of your set groups cause eliminations, I must always add more N sets. Maybe your output is missing them.

This 'super loop' still contains all the sets from the 3 floors, the super loop is probably 3 loops combined using some of the same sets.
Allan Barker
 
Posts: 266
Joined: 20 February 2008

Postby ronk » Tue Oct 28, 2008 5:54 am

Allan Barker wrote:A must see
Code: Select all
TUXX 75 Nodes, Rank 29:
     20 Sets = {56n6 1b234678 5b124689 7b124689}
     49 Links = {1r1245678 5r1245689 7r2345678 1c2345678 5c1245689 7c2345678 2n5 4n37 8n4 157b5}
     r1c1<>5, r1c4<>5, r1c6<>5, r2c5<>3, r2c5<>9, r2c6<>5,
     r4c4<>5, r4c5<>5, r5c1<>5,
     r5c5<>5, r5c9<>5, r6c5<>5, r6c9<>5,
     r8c4<>6, r8c6<>5, r9c5<>5

Color me skeptical. I don't think it's possible for a "minimal rank 29" constraint set to yield that many eliminations ... and there's a strong likelihood that it's masquerading for a yet-to-be-defined "complementary" structure with much lower rank -- maybe even rank 0.

That's my WAG for this month.:)
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby champagne » Tue Oct 28, 2008 7:03 am

Allan wrote:However, what you gave me for Tungsten Rod is 3 complete floors + 2 N cell sets.
This does not cause any eliminations. I added 4 more linksets to make eliminations.
So far, none of your set groups cause eliminations, I must always add more N sets.
Maybe your output is missing them.



Again, what I am doing is just testing all permutations for a given group of sets.
I have no guaranty that this fit with a sets/linksets construction.
Nothing to object if you need additional nodes to conclude in a sets/linksets view.
Anyway, your cells/Nodes added are either in the list NE of nodes allowing exclusion or in the list of nodes HC;
Nodes HC should be used in the final step to come to the lowest number of permutations and the highest list of assignments/eliminations.

Is it really a surprise if some linksets are not requested to validate permutations??



Allan wrote:This 'super loop' still contains all the sets from the 3 floors, the super loop is probably 3 loops combined using some of the same sets.


I guess so. I made meantime an additionnal check. It seems that only N56 and N66 can not be erased in a "brutal" permutations analysis.
Each of the other sets of the group can be suppressed giving still eliminations.
What I intend to do as next step is to start a stets/linksets constructions starting from that "core" situation;

In Platinium Blonde, the core is r12c7, two nodes as well.


ronk wrote:Color me skeptical. I don't think it's possible for a "minimal rank 29" constraint set to yield that many eliminations ...
and there's a strong likelihood that it's masquerading for a yet-to-be-defined "complementary" structure with much lower rank -- maybe even rank 0.


agreed for smaller "sets/linksets" patterns, but skeptical in my turn toward the concept of a complementary structure.
champagne
2017 Supporter
 
Posts: 5610
Joined: 02 August 2007
Location: France Brittany

PreviousNext

Return to Advanced solving techniques