The Illusion of Fata Morgana

Advanced methods and approaches for solving Sudoku puzzles

The Illusion of Fata Morgana

Postby Allan Barker » Sat Sep 20, 2008 8:09 am

Image

Fata Morgana

It was recently pointed out that the puzzle Fata Morgana, FM, stumps logic solvers that can solve Golden Nugget, and that FM is much harder to solve using grid solvers based on backtracking and even Algorithm X. Contrary to this, FM is easily solved with a freeform set logic solver, which rates the puzzle as only a medium monster. It initially seems that this difficulty is more illusionary than real, like a mirage or a fata morgana (cool name). Like a mirage however, the illusion can only be seen from certain perspectives. Obviously something is different about this puzzle, but what?

It is of course interesting to understand anything that can cause such trouble for different solving methods. The anomaly also asks the question what does it mean to say a puzzle is difficult?


Fata Morgana compared to Golden Nugget and Easter Monster

Although not necessary, it's helpful to include Easter Monster in the comparisons. The 3 puzzles, GN, EM, and FM are first compared using two different kinds of grid solvers, one of which uses backtracking with simple Sudoku moves, and the other uses a cover process similar to Algorithm X. Not only is FM very difficult, but GN is left as the easiest of the three.
Code: Select all
                      Backtrack  Algorithm X'

    Fata Morgana        191        129          arbitrary operations
    Easter Monster       72         47          arbitrary operations
    Golden Nugget        49         46          arbitrary operations

Set Logic solutions to these puzzles show exactly the opposite trend. The charts below show the relative difficulty of each move for solutions of GN and FM. Difficulty is based on both the number of strong sets required (blue) and the total number of nodes (red). Fata Morgana is obviously much easier and this is true of the entire solution path, not just some moves. (Easter Monster, not shown, is in between the two as far as difficulty)

Golden Nugget

Image

Fata Morgana

Image

Step by step rating of different methods

Grid solvers only show the work required to solve a puzzle. However, one way to see what's happenging is use the grid solvers after each elimination and then compare the work each solver does to solve each grid. The graphs below compare each method for all three puzzles. Comparing the first seven grids is enough to find part of the answer, which is that the anomoly is present only for the first 3 moves of FM. EM shows a slight anomaly for the first 2 moves and GN has none. Therefore, the first moves are casuing the problems but not for the set solver. As indicated in the graphs both EM and FM have initial SK loops but these loops are not the real problem. The numbers from each solver are arbitrary units, which are not related between solvers.

KEY: red = FM, green = EM, yellow = GN.

Backtracking
Image

Algorithm X'
Image

Set Solver
Image

The anomaly and SK loops

A look at FM and EM logic reveals that the true anomaly in not becasue SK loops are present but becasue the loops in FM have no bivalue sets (see logic below). In fact, the FM loops are somewhat smaller that the EM loops yet cause the puzzle to be several times more difficult. Most likely, some solvers could have difficulty solving a large structure made entirely of sets with 3 or more candidates. The role of the SK loop may be only to prevent the solver from finding other solution paths. Node designations are not included below, the path structure that a solver must follow is more important.

Fata Morgana, first SK loop A symbolic set logic diagram for the first of 3 SK loop eliminations. The logic has 11 strong sets all of which have 3 candidates. The second SK loop (not shown) has 14 strong sets, all of which have 3 candidates. ( = strong set, | weak set, * node, A, B, etc. triplet node)
Code: Select all
   A===============B================C
  / \             / \              / \
 /   \       ____/   \_____       /   \
|     |     |              |     |     |
*==*==|==*  |              |     |     |
*  |  |  |  |              |     |     |
|  |  *==*==|==*           |     |     |
|  |  |     |  |           |     |     |
|  *==*=====|==|==*        |     |     |
|     |     |  |  |        |     |     |
|     |     *==*==|==*     |     |     |
|     |     |  |  |  |     |     |     | 
|     |     *==|==*==|==*  |     |     |
|     |     |  |  |  |  |  |     |     |
|     |     |  |  |  *==*==*     |     |
|     |     |  |  |        *     |     |
|     |     |  |  *========|=====*==*  |
|     |     |  |           |     |  |  |
|     |     |  *===========|==*==*  |  |
|     |     |              |  |  |  |  *
|     |     |              |  *==|==*==*
|     |     |____     _____|     |     |
 \   /           \   /            \   /
  \ /             \ /              \ /
   D===============E================F


Easter Monster, first SK loop: A symbolic set logic diagram for the first of 2 SK loops eliminations. The logic has 16 strong sets of which 4 are bi-value. The second EM SK loop is much smaller. ( = strong set, | weak set, * node)
Code: Select all
*==*
|  |
|  *==*==============*
|  |  |              |
|  *==*===========*  |                         
|  |  |           |  |
|  *==*==*        |  |                         
|        |        |  *========*==*
|        |        |           |  |
|        |        *===========*==*             
|        *==*==*              |  |
|           |  |              |  |
|           *==*===========*  |  |
|           |  |           |  |  |
|           *==*========*  |  |  |             
|              |        |  |  |  *===========*
*==============*        |  |  |  |           |
                        |  |  *==*==*        |
                        |  |        |        |
                        |  |        *==*==*  |
                        |  |           |  |  |
                        |  *===========*==*  |
                        |              |  |  |
                        *==============*==*  |
                                          |  |
                                          *==*


Intrinsic difficulty (complexity), thoughts

Unlike a mirage, it's hard to explain away FM's difficulty as completely artificial. It is also hard to maintain that it is all real. Surely, some solvers look for initial bi-value sets or maybe even require them. However, Algorithm X is not restricted in such a way. Perhaps the only safe thing to claim is that each puzzle must have an intrinsic difficulty.

Rating puzzles by a set of rules like SE seems (to me) to work surprisingly well, and a precisely defined set of resolution rules may work even better. However, here lies the real illusion as FM demonstrates, any (reasonable) set of rules will work well when referenced only to itself. Two sets of rules can have significant differences yet each set is internally consistent. The only point I make is that intrinsic difficulty has intrinsic value (hah, can't argue with that!). Ultimately, human experience comes into play, which can be different from either rule based or intrinsic scales.

Edit: 1)put labels on diagrams. 2) Key to graphs

Allan
Last edited by Allan Barker on Sat Sep 20, 2008 3:48 pm, edited 3 times in total.
Allan Barker
 
Posts: 266
Joined: 20 February 2008

Re: The Illusion of Fata Morgana

Postby champagne » Sat Sep 20, 2008 8:43 am

Allan Barker wrote:
Code: Select all
   A===============B================C
  / \             / \              / \
 /   \       ____/   \_____       /   \
|     |     |              |     |     |
*==*==|==*  |              |     |     |
*  |  |  |  |              |     |     |
|  |  *==*==|==*           |     |     |
|  |  |     |  |           |     |     |
|  *==*=====|==|==*        |     |     |
|     |     |  |  |        |     |     |
|     |     *==*==|==*     |     |     |
|     |     |  |  |  |     |     |     | 
|     |     *==|==*==|==*  |     |     |
|     |     |  |  |  |  |  |     |     |
|     |     |  |  |  *==*==*     |     |
|     |     |  |  |        *     |     |
|     |     |  |  *========|=====*==*  |
|     |     |  |           |     |  |  |
|     |     |  *===========|==*==*  |  |
|     |     |              |  |  |  |  *
|     |     |              |  *==|==*==*
|     |     |____     _____|     |     |
 \   /           \   /            \   /
  \ /             \ /              \ /
   D===============E================F




Hi allan,

I can guess from your drawing that you found a loop using sets with three candidates.

I am not sure a lot of us will identify that as a SK loop. Shoul find another name.

You will not be surprised if I say I would be glad to have the list of sets (and maybe linksets) you used.

If this is a rank 0 , it confirms the feeling I had that your rule for rank 0 can handle situations we don't catch with AICs net and basic stuff



champagne

edit:

obviously this is not a rank 0 diagram, so it will raise another point. What is the objective difficulty of that diagram.:D Without your help, I think all of us will have strong diffiulties to understand it and the kind of clearings that can be done out of it.
champagne
2017 Supporter
 
Posts: 5653
Joined: 02 August 2007
Location: France Brittany

Postby ttt » Sat Sep 20, 2008 9:26 am

Hi Allan,
Congratulation…!
It seems that you become to present your deduction by 2D. IMO, the presenting by 2D is more clear & elegant than others...:D

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

Postby Allan Barker » Sat Sep 20, 2008 10:00 am

ttt,

ttt wrote:IMO, the presenting by 2D is more clear & elegant than others...

Thanks. Actually, I learned from your 2D logic diagrams. I think they can be more clear because there are no spacial dimensions like in 2D and 3D grid drawings.:idea:
Allan Barker
 
Posts: 266
Joined: 20 February 2008

Postby Allan Barker » Sat Sep 20, 2008 10:42 am

champagne wrote:I am not sure a lot of us will identify that as a SK loop. Shoul find another name.

You will not be surprised if I say I would be glad to have the list of sets (and maybe linksets) you used.

If this is a rank 0 , it confirms the feeling I had that your rule for rank 0 can handle situations we don't catch with AICs net and basic stuff


Tomorrow I will fully document both EM and FM loops. They are definitely the same phenomenon but have some logical difference, EM's are symmetric while FM's are anti-symetric. EM's sets are all rank 0 while FM's are rank 0 loops with some rank 1 sets. (this is not important). Maybe Steve K can help.

Also, don't forget rank 1. A skyscrapper and a discontinuous nice loop are both rank 1 patterns.
Allan Barker
 
Posts: 266
Joined: 20 February 2008

Postby champagne » Sat Sep 20, 2008 10:51 am

Allan Barker wrote:
Tomorrow I will fully document both EM and FM loops.

They are definitely the same phenomenon but have some logical difference, EM's are symmetric while FM's are anti-symetric. EM's sets are all rank 0 while FM's are rank 0 loops with some rank 1 sets. (this is not important). Maybe Steve K can help.

Also, don't forget rank 1. A skyscrapper and a discontinuous nice loop are both rank 1 patterns.


It didn't sound as rank0, but I have still a lot to learn. I thought it was more than rank 1 and I'll read in detail how you account the rank set by set.

I agree with "ttt" remark. These diagrams (with the list of sets) give a quick idea of how it works and how hard it can be.

Sleep well

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

Postby StrmCkr » Sat Sep 20, 2008 8:51 pm

nice catch allan. and congrates on posting it first:)

glade you found a way to show it i would have flaied alot and made no sence either..

same loop is applicable to
Tungston rod, and platiumn blonde.
Some do, some teach, the rest look it up.
User avatar
StrmCkr
 
Posts: 627
Joined: 05 September 2006

Postby Allan Barker » Sun Sep 21, 2008 1:59 am

I have included better details on the FM and EM loops including sets and PM grids. Full details one all three loops can now be found on these two webpages.

Fata Morgana Loops
Easter Monster Classic SK Loop

The second loop is more complex but based on all the same ideas as the first. A clear understanding of the first makes the second one easier. To a layer focus on the bottom part of the first (3D) image below. The upper two layers are the same except that the first is anti-symmetric and the second is symmetric wrt the bottom layer.

Champagne, I will add a better description later.

Allan

First Loop in FM

Image

Code: Select all
EX0a 36 Nodes, Rank 3:
     11 Sets = {136c2 136c5 136c8 5n46}
     14 Links = {16r1 3r2 136r5 6r8 13r9 4n2 6n8 136b5}
     --> (4n2) => r4c2<>2, (4n2) => r4c2<>4

  +-----------------------------------------------------------------------------+
  | 2458    247(6)  245678  | 126789  789(16) 1678    | 24589   248(1)  3       |
  | 2348    247(3)  1       | 23789   789(3)  5       | 6       248     249     |
  | 2358    9       2568    | 12368   4       1368    | 258     7       125     |
  +-----------------------------------------------------------------------------+
  | 12348   24(136) 2468    | 13678   78(136) 9       | 2347    5       12467   |
  | 7       24(136) 2469    | (136)   5       (136)   | 2349    24(136) 8       |
  | 1389    5       689     | 4       78(136) 2       | 379     (136)   1679    |
  +-----------------------------------------------------------------------------+
  | 145     8       457     | 1367    2       13467   | 3457    9       4567    |
  | 249     247     3       | 5       789(6)  4678    | 1       248(6)  2467    |
  | 6       247(1)  24579   | 13789   789(13) 13478   | 234578  248(3)  2457    |
  +-----------------------------------------------------------------------------+


Second Loop in FM.

Image

Code: Select all
E2z  42 Nodes, Rank 7:
     14 Sets = {136r3 136r7 136c2 136c8 5n46}
     21 Links = {136r5 136c4 136c6 3n46 4n2 6n8 7n46 36b1 1b3 1b7 36b9}
     --> (6b1) => r1c3<>6, (3b1) => r2c1<>3, (6r5) => r5c3<>6, (3r5) => r5c7<>3, (6b9) => r8c9<>6, (3b9) => r9c7<>3

  +-----------------------------------------------------------------------------+
  | 2458    247(6)  245678  | 126789  16789   1678    | 24589   248(1)  3       |
  | 2348    247(3)  1       | 23789   3789    5       | 6       248     249     |
  | 258(3)  9       258(6)  | 28(136) 4       8(136)  | 258     7       25(1)   |
  +-----------------------------------------------------------------------------+
  | 12348   (136)   2468    | 13678   13678   9       | 2347    5       12467   |
  | 7       24(136) 2469    | (136)   5       (136)   | 2349    24(136) 8       |
  | 1389    5       689     | 4       13678   2       | 379     (136)   1679    |
  +-----------------------------------------------------------------------------+
  | 45(1)   8       457     | 7(136)  2       47(136) | 457(3)  9       457(6)  |
  | 249     247     3       | 5       6789    4678    | 1       248(6)  2467    |
  | 6       247(1)  24579   | 13789   13789   13478   | 234578  248(3)  2457    |
  +-----------------------------------------------------------------------------+


Edit: Errata - the first code block with sets and PM grid was from the wrong elimination, now is correct.
Last edited by Allan Barker on Sun Sep 21, 2008 1:35 am, edited 1 time in total.
Allan Barker
 
Posts: 266
Joined: 20 February 2008

Postby champagne » Sun Sep 21, 2008 3:10 am

Allan Barker wrote:Champagne, I will add a better description later.


Hi Allan,

You made a great job. You can give us time to digest what you posted, waiting for precise questions.

For sure, I will come, if I don't find the answer alone or in your posts with the question I already raised : How do you account precisely the rank in each set of the first FM loop.

Your double entry table is "nearly perfect".
champagne
2017 Supporter
 
Posts: 5653
Joined: 02 August 2007
Location: France Brittany

Postby champagne » Sun Sep 21, 2008 6:49 am

Hi Allan,

First difficulty on my sde.

In your diagram for the first loop of FM, sets 136c5 are shown with three candidates.
In your map (and in mine as well), we have four. I had in mind that a set must include the entire lot of candidates.

Can you comment on that.

Thanks

champagne.

EDIT: adding one linkset N65 gives a new equilibrium, but it is now 15 linksets against 11 sets. May be it helps ...

Another point is that several candidates are not shown in linksets. If your final situation is rank 0, they should be eliminated as well.
champagne
2017 Supporter
 
Posts: 5653
Joined: 02 August 2007
Location: France Brittany

Postby Allan Barker » Sun Sep 21, 2008 8:47 pm

Hi champagne,

In your diagram for the first loop of FM, sets 136c5 are shown with three candidates. In your map (and in mine as well), we have four. I had in mind that a set must include the entire lot of candidates.


136c5 all have 4 candidates. The 4th candidate is not visible because it is hidden behind other sets. I have changed the diagram and all 4 candidates can be seen. (I know the 3D screen shots can be troublesome because you cannot rotate them. I use this diagram so you can see the symmetry, which will be important for loop 2)

You are correct, a set must include all candidates, a linkset does not need to.

EDIT: adding one linkset N65 gives a new equilibrium, but it is now 15 linksets against 11 sets. May be it helps ...


Interesting idea. Going further, if you add 2 linksets n65 and n45, you can then remove the 3 box linksets 136B5 from the middle producing a fully covered (and beautiful) structure with 11 sets and only 13 linksets. However, this does not produce an elimination. It is the triplets in sets n54 and 56 the lead to the eliminations. (I know this because the logic analyzer tells me so)

Another point is that several candidates are not shown in linksets. If your final situation is rank 0, they should be eliminated as well.


If you look at the above (new) diagram you will see that 2 of the linksets are shaded black to indicate they are rank 0.The rest of the linksets are not. In loop 2 about half of the linksets are rank 0, not all. In EM, all linksets are rank 0.

Note: A key point is the symmetry, both eliminations have 3 identical layers. Layers 3 and 6 are symmetric, layer 1 is anti-symmetric to 3 and 6. FM seems to be a very special puzzle and these eliminations may even provide new logical insights. In other words, a challenging place to start thinking about solvers, but challenge is where all the fun is.

Allan
Allan Barker
 
Posts: 266
Joined: 20 February 2008

Postby champagne » Mon Sep 22, 2008 1:00 am

Allan Barker wrote:Hi champagne,
136c5 all have 4 candidates. ... I have changed the diagram and all 4 candidates can be seen....

You are correct, a set must include all candidates, a linkset does not need to.

EDIT: adding one linkset N65 gives a new equilibrium, but it is now 15 linksets against 11 sets. May be it helps ...


Interesting idea.


I have not seen that changes in the 2D diagramm which is much better for me to understand how it works.

Adding a linkset was not in my view just an "interesting idea".

If you add the missing candidates in the sets, the linksets in the 2D diagramm do not "span" the sets. At least that linkset must be added. If I am right, we then switch from a overall rank 3 (14-11) to an overalll rank 4 (15 -11) logic.

Allan Barker wrote:Going further, if you add 2 linksets n65 and n45, you can then remove the 3 box linksets 136B5 from the middle producing a fully covered (and beautiful) structure with 11 sets and only 13 linksets. However, this does not produce an elimination. It is the triplets in sets n54 and 56 the lead to the eliminations. (I know this because the logic analyzer tells me so)


I am sure you are right and that example gives me another feeling about the amount of work to be done after you have collected a full group of sets and lnksets.

Another important point is to catch the logic to "analyze" the diagram. This is anyway a good example.

I guess you can at least understand what your solver is doing and it would be very helpfull for all of us to have it decoded in the 2D updated diagram (including the three missing candidates).

I have a side question: I started thinking how to implement your rules. Up to now, I do not foresee a more performing way than trying each collection of "non overlapping sets". It would be poorly perlorming compared to a process based on AICs (especially with full tagging accelerator". Do you have a better way to do it?







Allan Barker wrote:
If you look at the above (new) diagram you will see that 2 of the linksets are shaded black to indicate they are rank 0.The rest of the linksets are not. In loop 2 about half of the linksets are rank 0, not all. In EM, all linksets are rank 0.

Again, if you can find a way to show ranks in the 2D diagram, it would be garte.


Allan Barker wrote:a challenging place to start thinking about solvers, but challenge is where all the fun is.


I will surely not start implementation on such patterns, but:

1) It s the first time my computer is defeated so if I intend to have rules complementary to mine, I must reach that stage,
2) To follow Tarek suspicion, I still don't know if this is a bug of my solver or a limit in my rules capabilities. I will not start checking that before I clearly understand the logic of your clearings,
3) This is a relatively simple examples (in 2D diagram) to catch the logic of rank counting with linksets triple points (no bifurcation, only linksets triples...)

Edit:

1) a small detail, the title in the page we reach following the link for EM loop is not correct.

2) Your 3D diagram shows two clearings in B51, which is correct for a rank0 linkset. In the 2D diagram, p441 is still missing. (but again why only that one is rank 0???).
champagne
2017 Supporter
 
Posts: 5653
Joined: 02 August 2007
Location: France Brittany

Postby champagne » Mon Sep 22, 2008 4:32 am

Hi Allan,

I am trying to catch your point.

The map

Code: Select all
 +-----------------------------------------------------------------------------+
  | 2458    247(6)  245678  | 126789  789(16) 1678    | 24589   248(1)  3       |
  | 2348    247(3)  1       | 23789   789(3)  5       | 6       248     249     |
  | 2358    9       2568    | 12368   4       1368    | 258     7       125     |
  +-----------------------------------------------------------------------------+
  | 12348   24(136) 2468    | 13678   78(136) 9       | 2347    5       12467   |
  | 7       24(136) 2469    | (136)   5       (136)   | 2349    24(136) 8       |
  | 1389    5       689     | 4       78(136) 2       | 379     (136)   1679    |
  +-----------------------------------------------------------------------------+
  | 145     8       457     | 1367    2       13467   | 3457    9       4567    |
  | 249     247     3       | 5       789(6)  4678    | 1       248(6)  2467    |
  | 6       247(1)  24579   | 13789   789(13) 13478   | 234578  248(3)  2457    |
  +-----------------------------------------------------------------------------+


Adjusted diagram for clearing logic with missing candidates in the set
(at least the way I did it. I suspect the computer used anothe span).


Code: Select all
p541A=============p541A=======p543B=============p543B=======p546C=============p546C
 |                 |           |                 |           |                 |
p451==p951==p151== |  ======== | ==============  |  =======  |  ============== | ==p651
 |     |     |     |           |                 |           |                 |      |
 |     |    p181==p581=========|=================|====p681   |                 |      |
 |     |           |           |                 |     |     |                 |      |
 |    p921========p521==p421   |                 |     |     |                 |      |
 |                 |     |     |                 |     |     |                 |      |
 |                 |    p423==p523==p223         |     |     |                 |      |   
 |                 |     |     |     |           |     |     |                 |      |   
 |                 |     |     |    p253==p953==p453   |     | ==============  | ==p653   
 |                 |     |     |           |    p653   |     |                 |      |   
 |                 |     |     |           |     |     |     |                 |      |   
 |                 |     |    p583========p983===|====p683   |                 |      |   
 |                 |     |     |                 |     |     |                 |      |   
 |                 |     |     |                 |    p686==p586========p886   |      |   
 |                 |     |     |                 |           |           |     |      |   
 |                 |    p426===|=================|==========p526==p126   |     |      |   
 |                 |           |                 |           |     |     |     |      |   
 |                 |           |                 |           |    p156==p856==p456 p656
 |                 |           |                 |           |                 |   
p561D=============p561D=======p563E=============p563E=======p566F=============p566F




and the new diagram after the three box linksets have been replaced by the linkset in Node 45.

Code: Select all

                  p541A=======p543B====================p546C
                   |           |                        |               
p451==p951==p151== |  ======== | ============= =======  |  =============p651
 |     |     |     |           |                        |                  |
 |     |    p181==p581=========|=================p681   |                  |
 |     |           |           |                  |     |                  |
 |    p921========p521==p421   |                  |     |                  |
 |                 |     |     |                  |     |                  |
 |                 |    p423==p523==p223          |     |                  |   
 |                 |     |     |     |            |     |                  |   
 P453  ============| === |     |    p253==p953=== |     | ==============p653   
 |                 |     |     |           |      |     |                  |   
 |                 |     |     |           |      |     |                  |   
 |                 |     |    p583========p983===p683   |                  |   
 |                 |     |     |                  |     |                  |   
 |                 |     |     |                 p686==p586========p886    |   
 |                 |     |     |                        |           |      |   
 |                 |    p426===|=======================p526==p126   |      |   
 |                 |           |                        |     |     |      |   
 P456  =========== |  ======== |   ===================  |    p156==p856== p656
                   |           |                        |                 
                  p561D=======p563E====================p566F=


The last diagram is rank 2 with no triple point if I am right.

No chance to have any clearing out of it, I agree.

1) Am I right in the way I analyze the situation

2) If yes, I really need to understand how the computer clears the situation in the first diagram (or any other diagram he uses).

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

Postby Allan Barker » Mon Sep 22, 2008 7:00 am

Champagne, first point.

Now I understand. The small 2D diagram with green nodes is an on-screen editor to rearrange sets before printing a bigger 2D diagram. The candidates are in the bigger (ASCII code) 2D diagram. (See documentation just below about multiple nodes). The red color indicates more than 1 node. Very sorry for the difficulty. I do this only for multiple candidates in a single box/single line intersection. These usually make no difference to the set logic, and are similar to hinges. I'll have to think how to fix the on-screen editor display. Again, sorry, next post will 1) describe loop 1 elimination, 2) discuss solver and your point about analysis. Soon

Code: Select all
2D set/linkset diagrams - ASCII print version

[*] = a unique node, no id
[===p123===] node rcn notation
[===3r2c2===] node standard notation
[ p123A ] A, B, ... letters for same node in 2 or more sets/linksets (same letter)
[  = ] = strong set
[  | ] = weak set (can be strong set in puzzle)
[  + ] = continuation
   
    |
==p123==  2 or 3 nodes linking 1 box and 1 line set.
  p223
    |     

2D set/linkset diagrams - on screen editor

[green box] = unique node
[ * ] = more than 1 unique node at box/line intersection
[A, B] = same as above
[A (red] = 2 nodes at box/line intersection
[A(blue?)] = 3 nodes at box/line intersection


(I have updated EM page title, thanks)
Allan Barker
 
Posts: 266
Joined: 20 February 2008

Postby Allan Barker » Mon Sep 22, 2008 7:55 am

FM Loop 1 elimination based on inference sets

Step 1. Two sets, n54 and n56, and 2 linksets n42 and n68, each have 1 node in each of the 3 layers. Looking at digit level 6, see image below, if A (or B) is true then [C D] forms a strong inference set in linksets n42 and n68, (pink cubes), i.e., C or D must be true. Step 2. n54 and n56 must occupy A or B in any 2 of the 3 layers, therefore linksets n42 and n68 must be occupied by two SIS [C D] and [C' D']. Thus both n42 and n68 must be occupied, i.e., they are rank 0. See diagram for key to labels. In logic terms:

6r5c4 => 6r4c2|6r6c8 , 3r5c4 => 3r4c2|3r6c8 ,
6r5c4 + 3r5c4 => 6r4c2|6r6c8 + 3r4c2|3r6c8 => r4c2 <> 2, r4c2 <> 4

Image

FM Loop 1 elimination based on rank and zones, concept

The elimination can also be described in terms of rank and zones. All six nodes in sets n54 and n56 make triplets (each node is in 2 linksets). Two of the triplets must be occupied thus 13 of the 14 linksets are guaranteed to be occupied, and the rank everywhere must always be 1 or lower. An un-occupied triplet lowers the rank along its 'set' branch (1 of its 3 branches). Each triplet's branch will be along a different path but all paths will include linksets n42 and n68. Thus, n42 and n68 will always be in a rank 0 zone.

PS. Loop 1 and loop 2 of FM are very unique eliminations otherwise, they would not stump your solver and would not slow down the other grid solvers so much.

champagne wrote:The last diagram is rank 2 with no triple point if I am right.

No chance to have any clearing out of it, I agree.

1) Am I right in the way I analyze the situation

2) If yes, I really need to understand how the computer clears the situation in the first diagram (or any other diagram he uses).


Your thinking is all correct and very good, except for only the miss-information I gave you. Next: how my solver analyzes a logic block. I understand this is the most important part of the exercise.

Allan
Allan Barker
 
Posts: 266
Joined: 20 February 2008

Next

Return to Advanced solving techniques