Full Tagging

Advanced methods and approaches for solving Sudoku puzzles

Postby champagne » Thu Nov 22, 2007 9:18 am

Hello Myth,

I just red your new post but I have a limited acces to the net for the time beeing.
Here is a comment I prepared for the previous one

Basically, nothing to add to your point. This is a perfect use of full tagging in "level 1+".

As far as I could see, you have often some equivalent AIC chains going thru ALSs/Acs, but this is not granted.

Use of "isolated tags" as yous did for 'x' and 'y' is a good way to explain the solution.
Skilled players would may be have skipped 'y' due to the fact that 5r2c9 is common to both sets.

Level 1+ is performing very well when the relevant candidates are tagged in level 1.
What you did here is requesting a better practice and subject to finding the appropriate weakness in the puzzle.

For the solver, this ends in a "clearing chain" [] xa Ax

Another usefull pattern is the following:

23A4B ___ ___ 2++ .... .... 2A+++

where the second '2' can be tagged 'B'



edit one second example

Myth wrote

Code: Select all
Ravel mailed me this real world example yesterday...

 *------------------------------------------------*
 | 5     2679  169  | 3  67  4  | 19   1267   8   |
 |#1x267 8    @13A6 | 5  67  9  |@1A3a 12467  46  |
 | 679   3679  4    | 1  8   2  | 5    67     369 |
 |------------------+-----------+-----------------|
 | 4     5     2    | 7  9   6  | 8    3      1   |
 | 69    69    7    | 8  3   1  | 4    5      2   |
 | 3     1     8    | 4  2   5  | 6    9      7   |
 |------------------+-----------+-----------------|
 |#1b67  367   5    | 9  4   8  | 2   @1B6    36  |
 |#1y2   24   #1x3a | 6  5   7  |#1b39 8      49  |
 | 8     469   69   | 2  1   3  | 7    46     5   |
 *------------------------------------------------*
 
r8c3<>1, r2c1<>1


As you stated later, in this case, r8c3 should be tagged 1A3a.

Thru groups tags, 1r8c3-A 1r12c3-a 1r2c1-A 1r78c1_a is part of the layer A,a.

This is in fact level 1.
champagne
2017 Supporter
 
Posts: 5742
Joined: 02 August 2007
Location: France Brittany

Postby champagne » Sat Jan 26, 2008 11:23 am

Denis BERTHIER introduced T chains.

I thought of introducing these chains in my process, fascinated by their density. Finally, I gave up for three main reasons:

- T chains are a subset of my process,
- Finding directly such chains would force me to introduce oriented chains, that do not exist in tagging process
- Transforming existing process in T chains does not bring additional value.

I will show very simply why T chains are a subset of existing process; however, it remains true that for highly sophisticated T chains, alternative paths would appear in my process.


Let us consider an example taken out of number 3 of the top 1465 list.


Code: Select all
7     126     8       |459   2459  2459  |3     1456  1259   
249   23      2349    |6     23459 1     |2479  4578  25789
5     1236    123469  |78    2349  78    |12469 146   129   
----------------------------------------------------------
189   4       1579    |3579  59    3579  |178   2     6     
3     1267    12679   |479   8     24679 |147   1457  157   
268   25678   2567    |1     2456  24567 |478   9     3     
---------------------------------------------------------
168   9       13567   |2     156   3568  |167   13678 4     
12468 12368   12346   |3489  7     34689 |5     1368  1289 
12468 1235678 1234567 |34589 14569 345689|12679 13678 12789 


Code: Select all
nrczt4-chain n9{r2c1 r4c1} - {n9 n5}r4c5 - n5{r2c5 r2c8} - n8{r2c8 r2c9} ==> r2c9 <> 9

AICs equivalent
#9r2c9   []5r1c89/5r1c456_5r2c5/5r4c5_9r4c5/9r4c1_9r2c1/9r2c9
   []5r2c9/9r2c9 []5r2c8/8r2c8_8r2c9/9r2c9

To make easier comparison, I change slightly the nrczt4-chain

Code: Select all
9r2c1_9r4c1/9r4c5_5r4c5/5r2c5 ??? 5r2c8/r2c8_r2c9  ==> r2c9 <> 9

I change as well the group of chains

Code: Select all
9r2c9/9r2c1_9r4c1/9r4c5_5r4c5/5r2c5   _5r1c456/5r1c89 || _5r2c8/8r2c8_8r2c9/9r2c9
  ___________________________________________/ 5r2c9  ||


We see what the equivalent form is for "???".

In that case, I don’t know exactly how DB establishes the strong link equivalent to “???”. This is due to the fact that the chain does not include the target.

In you include the target, we have nearly the standard case :

Following the second presentation, when you reach the ‘5’ in box 1, you have already cleared all of them but 5r2c8. If you go ahead with 5r2c8, you end up in a conflicting loop.

In the normal case, if you have a T chain, you always reach the first knot with only one valid candidate. This means that you have found AIC chains to clear other candidates. In the tagging process, this appears as a derived weak link.

In the next knot, the same rule will apply.

I mentioned that looking directly for T chains, you can find other paths than applying the tagging process. The reason is very simple. If the second knot for example is using the derived weak link established in a first step, this is seen as relatively complex by the solver and another chain can be found before.

If the chain is compulsory for the solution, no doubt, it will appear in both solutions.
champagne
2017 Supporter
 
Posts: 5742
Joined: 02 August 2007
Location: France Brittany

Postby champagne » Thu Jan 31, 2008 11:25 am

Hi Mike,

I'll try to clarify some of the points you raised. This post is mainly dedicated to complementary tagging

This is the last step in the up-to-date version of Easter Monster cracking.
I have reduced the tagging to used layers, you will see why.

Code: Select all
1      4B7b   458    |357B   389    56a8    |349    6A9a 2       
2b3B   9      3b7B   |4      1a6A   2B7b    |1A8a   5    6a8A     
5d8D   2B48   6      |1j2a3  389    1B25D8  |7      1a39 349     
--------------------------------------------------------------
48     5      1j48   |9      1B2b   3       |1a2B8j 6a7A 6A7a     
389    1a2j6B 3B89G  |2B6b   7      4       |35f8B9 1A2a 5F8a9   
2B36a9 2a6j7B 1B7b   |8      5      1b6B    |2j39   4    39     
----------------------------------------------------------------
7      1A8a   4G9g   |1a35   348    2a58    |6      2A3a 34q5f9G
5a6A   3      1a4q5d |1B2j7a 1j2B6a 9       |2a45q  8    4a7A     
45q89G 46a8   2      |356B7  34     56j7B8a |359    37a9 1   



The solver concludes simply as follow.

Code: Select all
#G   []1r4c7==8r5c9.a - 5r5c9.F = 5r7c9.f - 9r7c9.G []2r4c7==3r5c3.B - 9r5c3.G []8r4c7==2r6c7.j - 9r6c7 = 9r6c19 - (9r7c9 9r9c1).G
#a   []3r5c3==6r6c6.B - 6r1c6.a []9r5c3==9r7c9.G - 5r7c9.f = 5r5c9.F - 8r5c9.a []8r5c3 - 8r5c9.a
#q   []2r7c6==1r8c3.a - 4r8c3.q []2r2c6==2r3c2.B - 4r3c2.c = 4r3c9.C - 4r7c9.q []2r3c6 - 5r3c6.D = 5r3c1.d - 5r9c1.q


All seems perfect, nevertheless, if one has an accurate look on the tagging, all 'j' tags and some 'a' 'B' tags have no clear underlying strong/weak link logic.

Here is the puzzle I got having tagged a,b layers using bi values.


Code: Select all
1      4B7b   458  |357B   389    56a8   |349    6A9a 2       
2b3B   9      3b7B |4      1a6A   2B7b   |1A8a   5    6a8A     
58     2B48  6     |12a3   389    1B258  |7      1a39 349     
----------------------------------------------------------
48     5      148  |9      1B2b   3      |1a2B8  6a7A 6A7a     
389    1a26B  3B89 |2B6b   7      4      |3589   1A2a 58a9   
2B36a9 267B   1B7b |8      5      1b6B   |239    4    39     
----------------------------------------------------------
7      1A8a   49   |1a35   348    2a58   |6      2A3a 3459
5a6A   3      1a45 |127a   12B6a  9      |2a45   8    4a7A     
4589   46a8   2    |356B7  34     567B8a |359    37a9 1       


We are in a classical situation end of level one, no available clearing chain.

Complementary tagging is a tool used normally at that time by hand solvers.

Rule: If in two choices of same length all tags are identical but one, the last on is identical (trivial).

eg: cell r4c7 1a2B8?; column c3 1a1B1? => 1r4c3 and 8r4c7 same tag. We use 'j' as tag.
As well
. 6r9c6 'j'
. 1r8c5 'j' => 1r8c3 'B' => 2r8c5 'j' =>1r3c4 'j' => 3r3c4 'B' (not done by the solver)
. 8R5c7 'B' => 2r6c2 'a' => 6r6c2 'j'
. 2r6c7 'j'


Question: How did the solve find these tags.

The first one is very common and leads often to clearing AICs in "hard puzzles".
r4c57 is an ALS/AHS/AC easy to detect. 12b 12B8.
Counterpart is as well ALS/AHS/AC.
This defines a strong link 1/8 in r4c57 and r4c1389. 1r4c1 = 1r4c57 = 8r4c7 = 8r4c13 loop.

The solver got others 'j' tags thru the "memory" function.

In former steps, the solver has found Nice loops establishing

6r6c2==6r9c6
2r5c2==6r9c6
1r4c3==1r3c4
1r4c3==2r5c2
2r8c4==2r5c2

We will look at the first of these loops to comment on another typical situation
We were here far above

Code: Select all
1     47B8  345h8  |3567À  389g 5678  |34i89 36A9   2     
2B38  9     37b8   |4      1a26 267B  |1A38  5      36a8 
345H8 2b48  6      |1235   389G 1258  |7     1a39   34I89
---------------------------------------------------------
24c68 5     14C7z8 |9      126  3     |1a28  1267E  678   
389   1Í2Î6 389    |1Ê2Ë6Ì 7    4     |35d89 1M2È6É 35D89
2369  1267b 1379   |8      5    1L26  |239   4      367z9
---------------------------------------------------------
7     1j48  4589k  |1235   34f8 1258  |6     2E39   3459 
456j  3     1J45   |1267e  126  9     |2e45  8      457E 
4589K 46J8  2      |3567   34F8 567À8 |3459  37e9   1     



And this is the sequence followed by the solver to establish the loop
Note 6r5c2==6r9c4 is established earlier, we accept it as granted

#[]$e - 6r9c6 6r6c2.$E []6r9c2 - 6r9c6 []6r5c2==6r9c4 - 6r9c6
#[]6r6c2 - §Y 6r9c6.§y []6r9c2 - 6r6c2 []6r9c4==6r5c2 - 6r6c2

loop []$e - 6r9c6|# = §Y - 6r6c2|#

We have here an example of another rule:
- 6r9c6 is in weak link with 6r5c2 and 6r9c2.
- 6r9c6 forces 6r6c2 which we express in weak link form: 6r6c2 forms a weak link with any complementary set of 6r6c2
(6r6c169; 6r59c2; 6r46c1r5c2)

In the same way 6r6c2 forces 6r9c6.

It's clear that if 6r9c6=>6r6c2 and 6r6c2=>6r9c6, both have same tag.

Such very short loops are often establishing vicinity evidences for a human player.
For the solver, this is already a complex procedure. Although the sequence is very short, level 3 is needed.
I have no easy way to change priorities to meet human feeling of difficulty.

In the start of Easter Monster, we have about 60 of these vicinity evidences seen as Nice loops by the solver. This linked to the "memory function" contributes to the changes from first version.

Another point is the use of tags $e, §Y in the print. I could have replaced these tags by any of corresponding groups. I find more representative of the logic to keep the tag stressing on the fact that this is a canonical form for xxx force yyy.

Next post will answer your question on AC2 handling (I hope so).
champagne
2017 Supporter
 
Posts: 5742
Joined: 02 August 2007
Location: France Brittany

Postby Mike Barker » Fri Feb 01, 2008 4:08 pm

Thanks for the explanation - very understandable. The first type seems pretty straight forward. Although the second type may be based on nodes which are "close", it’s not clear when a hand solver might embark on trying to find such a tag, unless working both ends of the chain toward the middle. It is, however, a clever example of what is possible to systematically solve really tough puzzles.
Mike Barker
 
Posts: 458
Joined: 22 January 2006

Postby champagne » Fri Feb 01, 2008 4:47 pm

First answering to your interrogation:

For hand solver, these tools are mainly used when the puzzle blocks late. Then, the number of layers is relatively small, and you have clues looking at Choices already tagged. The search is normally limited to ternary choices.



Next step to answer your questions, main points regarding AC2/AAHS?.
I'll use the start of Easter Monster.

AC2 are normally m+2+x digits in m cells with m-2 digits known.
Here below

r2c13 is an AC2 2 cells, four digits nothing granted. m=2; x=0.
r2c5679 is an AC2 4 cells, 6 digits, 1;6 valid m=4,x=0;
r2c136 s an AC2 3 cells, 6 digits,7 valid m=3; x=1.

This excludes AC2 which are also ALS.

My first use of AC2 and AALS (end 2006 when puzzles resisting to my level 3 appeared)was a failure.

In the middle of 2007, I had the idea to consider couples of digits applied to such objects as "super candidates".
Having experienced with ACs that the most efficient ACs where very simple ones, I limited the field to x=0 objects.

With x=0, AC2 (AAHS) is also AALS and the counterpart is AC2/AAHS/AALS as well.
Another simplification: all these AC2 have six "super candidates"
eg: r2c13 digits 2378, super candidates (2&3) (2&7) (2&8) (3&7) (3&8) (7&8).
Other property: if (2&3) is considered for r2c13, then (7&8) is the corresponding "super candidate" for r2c5679, the complementary AC2.
In the tagging process, each "super candidate" has a corresponding "couple tag" processed like any other tag.
The list of possible super candidates for an AC2 is a Choice (one and one only valid) with all properties of other choices.
Each "super candidate" has "native weak links" reflecting the content.
eg: (2&3)r2c13 - 2r2c56 (2&3)r2c13 - 3r2c589 (2&3)r2c13 - 8r2c13 (2&3)r2c13 - 7r2c3

This has been enough to crack resisting puzzles (up to now). Following considerations have been added to find lighter solutions.

Thanks to Steve Kurthals, analyzing the SK loop, I introduced the Virus pattern.

A potential virus pattern is an AC2 belonging to two units. All Virus pattern I have seen have 2 cells.
r2c13 is a potential virus pattern: AC2; 2 cells; belonging to row 2 and box 1.

Potential virus pattern we can see here are
r2c13 r2c79 r5c46 r8c13 r8c79 r13c2 r79c2 r56c6 r13c8 r79c8
A potential virus pattern switches to a virus structure when you have 2 virus patterns belonging to the same unit sharing at least 2 digits.

r2c13.r2c79 is a virus structure. They belong to row 2 and share digits 3;8
Chaining Virus patterns is to my view the simplest way to establish the SK loop.
It gives an easy probe of associated clearings.


Code: Select all
1      47d8  345f78 |3567y  3689e  5678     |34h89   36i9  2     
2o38   9     37a8   |4      12368  1267A8   |1g38    5     36I8   
2345F8 2P48  6      |1235   12389E 1258     |7       1G39  34H89 
-----------------------------------------------------------------
2468   5     147x8  |9      124j6  3        |128     1267C 678   
234689 12468 13489  |1Í2Î6  7      1ê2ë4J6ì |1235b89 12369 35B689
2369   1267D 1379   |8      5      1Ç2È6É   |1239    4     367x9 
-----------------------------------------------------------------
7      1N48  14589k |1235   12348  12458    |6       2l39  3459   
456v   3     1M45   |12567c 1246   9        |2L45    8     457C   
45689K 46w8  2      |3567   3468   4567y8   |3459    37c9  1   



Aplying SK loop, we reach that point.

Code: Select all
1     47A8  345h8  |3567Ã 389f 5678  |34j89 36k9  2     
2g38  9     37a8   |4     126  1267A |1i38  5     36K8 
345H8 2G48  6      |1235  389F 1258  |7     1I39  34J89
-------------------------------------------------------
24b68 5     14B7Â8 |9     126  3     |128   1267D 678   
389   126   389    |126   7    4     |35c89 1Î26  35C89
2369  1267a 1379   |8     5    126   |1239  4     367Â9
-------------------------------------------------------
7     1l48  4589n  |1235  34e8 1258  |6     2o39  3459 
456m  3     1L45   |1267d 126  9     |2O45  8     457D 
4589N 46M8  2      |3567  34E8 567Ã8 |3459  37d9  1


At that point SK loop is like a circular fishbone with two parallel ways
(3&8)r2c13=>(1&6)r2c79=>....(2&7)r13c2=> loop
(2&7)r2c13=>(4&8)r13c2=>....(3&8)r2c79=> loop

all "super candidates" in one line have the same tag.
Most often the first step will be to prove that these two lines are not valid.
If proven, r2c13 will be reduced to (2|7) and (3|8) or {(2&3) (2&8) (3&7) (7&8)}.
Such a pattern leads to (2^7) and (3^8).

We see here another key property of AC2.
When you reduce the number of possible "super candidates" you have new properties.
Possible actions will be :
. creating strong links as here,
. forcing a candidate eg digits 1234 still valid (1&2) (1&3) (1&4) group candidate 1 is valid,
. vicinity analysis (no comments here, this will be a separate post)


In Easter Monster the two lines can be cleared easily:

The first one contains 2r5c2 and 2r5c8 which is impossible
The second one contains 2r2c5 and 2r8c5 ...

We have now the revised tagging including the strong links created.

Code: Select all
1     47A8   345g8  |3567y  389f 5678  |34i89 36h9   2     
2A38  9      37a8   |4      126  1267A |1h38  5      36H8 
345G8 2a48   6      |1235   389F 1258  |7     1H39   34I89
----------------------------------------------------------
24b68 5      14B7x8 |9      126  3     |128   1267D  678   
389   1Ì2Í6Î 389    |1É2Ê6Ë 7    4     |35c89 1Æ2Ç6È 35C89
2369  1267a  1379   |8      5    126   |1239  4      367x9
----------------------------------------------------------
7     1j48   4589k  |1235   34e8 1258  |6     2D39   3459 
456j  3      1J45   |1267d  126  9     |2d45  8      457D 
4589K 46J8   2      |3567   34E8 567y8 |3459  37d9   1


At that point, the solver discovers about 60 Nice loops establishing vicinity equivalences.
I’ll comment Vicinity Analysis in the next post
champagne
2017 Supporter
 
Posts: 5742
Joined: 02 August 2007
Location: France Brittany

Postby Mike Barker » Sat Feb 02, 2008 3:12 pm

I look at this post and AC2 seem so simple and somewhat amazing. If
Champagne: With x=0, AC2 (AAHS) is also AALS and the counterpart is AC2/AAHS/AALS as well ... This has been enough to crack resisting puzzles (up to now).
Champagne: Most often the first step will be to prove that these two lines are not valid ... In Easter Monster the two lines can be cleared easily


are even almost always true, then AC2 seem to make fast work of tough puzzles. Of course I look at your full solution to the Easter Monster and I'm not sure which is the bigger monster - the puzzle or the solution. Is this a simpler approach to what you presented in your solution or is the challenge in the vicinity analysis?
Mike Barker
 
Posts: 458
Joined: 22 January 2006

Postby champagne » Sat Feb 02, 2008 6:55 pm

The first part was already in the posted solution for Easter Monster. I just added comments.

As you could guess, the next step to go to lighter solution is vicinity analysis. I was slightly short in time, but I will post what I am preparing to-day, or to morrow. If I have the good feeling, The last version of Easter Monster I am working on is significantly better that the first one.

Regarding the two lines of Easter Monste loop, I have one example, tarek 191 where only one line is cleared.

For other reasons, I will publish it soon in full tagging examples.

In other puzzles having SK loop I studied, the two lines are cleared.
champagne
2017 Supporter
 
Posts: 5742
Joined: 02 August 2007
Location: France Brittany

Postby Mike Barker » Sat Feb 02, 2008 7:33 pm

Take your time. I had some free time this week, but that's over so I won't have much time to devout to Suduko.
Mike Barker
 
Posts: 458
Joined: 22 January 2006

Postby champagne » Wed Feb 06, 2008 10:56 am

Hi Mike ,

I continue comments on level 4 key points. This topic is focused on “Vicinity analysis”, (still using Easter Monster as example), and will include in an edit to come comments on typical patterns for Nice loops appearing immediately after in that version of Easter Monster.

“Vicinity analysis” is an issue I raised to speed up and simplify AC2 processing.

AC2 basic processing considers “super candidates”. Each time you can establish equivalence between a candidate and a super candidate, you improve chances to find a clearing.

The only process known by the solver to do that is AIC chains. It’s not performing very well.

Look at r2c13 r2c1=238 r2c3=378. Nobody would object that super candidate (2&3) means 2r2c1 3r2c3. This is a trivial “vicinity effect”. If you add that (3&8) is not valid, 3r2c3=>(2&3). This is a full equivalence much more important.

Catching the first fact is not very difficult. The second one appears in a wide variety of patterns. It’s normally easy to detect for a human being, you have to design it properly to have them found by the solver. Easter Monster last version will help to do it.

Using the basic process, the solver compensates thru Nice loops, but to late to follow the simplest cracking path. Memory function added recently diminishes the weakness, but there is still room for improvement.

In very specific situations, you can get directly equivalence between a candidate and a super candidate. It comes for example when you have an AC2 with a dual cell:

X=12 Y=234 (Y=2)=> (1&2) (1&2)=>(Y=2) 2Y has the same tag as (1&2)XY

It is essential to identify as soon as possible such equivalences if you are looking for short cracking sequences. It’s much easier to prove that a couple tag is not valid than to clear candidates. I you have not seen the equivalence, you cancel the couple tag, without clearing the candidate (or group of candidates). This leads to the boring long paths I have shown in “full tagging examples” first shot.

I am convinced that vicinity analysis will be a key issue for anybody willing to crack hardest puzzles without the help of a computer.


At the point where we left Easter Monster, the solver found 60 “vicinity effects”. Then three other sets of Nice loops came before starting clearing.

I will not give the entire list, but I will select representative examples.


Code: Select all
1     47A8   345g8  |3567y  389f 5678  |34i89 36h9   2     
2A38  9      37a8   |4      126  1267A |1h38  5      36H8 
345G8 2a48   6      |1235   389F 1258  |7     1H39   34I89
----------------------------------------------------------
24b68 5      14B7x8 |9      126  3     |128   1267D  678   
389   1Ì2Í6Î 389    |1É2Ê6Ë 7    4     |35c89 1Æ2Ç6È 35C89
2369  1267a  1379   |8      5    126   |1239  4      367x9
----------------------------------------------------------
7     1j48   4589k  |1235   34e8 1258  |6     2D39   3459 
456j  3      1J45   |1267d  126  9     |2d45  8      457D 
4589K 46J8   2      |3567   34E8 567y8 |3459  37d9   1


Just before going into details, I need 8r3c2 => A (or in chains 8r3c2 – ‘a ‘). Easy to show starting from cell r1c2.


r2c13 is the first AC2 analyzed. It brings interesting points. Don’t forget that (2&7) and (3&8) are cleared;
The solver found:

r2c13 1w: (2&3)==3r2c3 1y: (2&8)==8r2c3 1z: (3&7)==3r2c1 1x: (7&8)==8r2c1 (2&8)==8r3c9???

All of them are trivial for a human being but the last one. The solver uses the first step of “vicinity effect” I implemented giving for example
(2&8)=>8r2c3. and (7&8)=>8r2c1…..
8r2c3=>(2&8) is trivial if you remember that (3&8) is cleared. Same for others out of the last one.

You immediately see I guess that two Nice loop are based on (2&8).
The second equivalence (2&8)==8r3c9 uses the fact (see above) that 8r3c9=>’A’
Code: Select all
 []1w 8r2c79 - 8r3c9 []1x;1z – 7rc2.A  =  7r2c3.a  - 8r3c9  =>8r3c9 forces  1y
 []8r2c79.l  - 1y   []8r1c7 - 4r1c7.i = 4r3c9.I - 4r3c2  1y   => 1y forces 8r3c9



I would accept that this is "out of the scope" of trivial equivalences.
More interesting is the fact that we have two equivalences for (2&8).
As a matter of fact, the solver shows later (another loop in following steps) that 8r3c9==8r2c3.
This was granted here.

You can find equivalences to candidates of AC2 in

r8c79 (2&4)==4r8c9 (2&5)==5r8c9 (4&7)==4r8c7 (5&7)==5r8c7
r13c2 (2&4)==4r1c2 (2&8)==8r1c2 (7&8)==8r3c2 (4&7)==4r3c2
r79c8 (2&3)==3r9c8 (2&9)==9r9c8 (3&7)==3r7c8 (7&9)==9r7c8
r2c79 (6&8)==8r2c7 (1&8)==8r2c9 (1&3)==3r2c9 (3&6)==3r2c7
r13c8 (6&9)==9r3c8 (1&9)==9r1c8 (3&6)==3r3c8 (1&3)== 3r1c8
r8c13 (1&5)==5r8c1 (5&6)==5r8c3 (4&6)==4r8c3 (1&4)==4r8c1

r79c2 looks like r2c13

Code: Select all
r79c2    6i:(1&8)==8r9c2  6h:(6&8)==8r7c2 
6g:(1&4)==4r9c2   (1&4)4r1c3??  6j  :(4&6)==4r7c2  (4&6)==4r3c1???


Once again, several equivalences for the same “super candidate”. Moreover, I quite remember that 4r3c1==4r7c2 is a preliminary step in the clearing sequence of both.
Here is the way the solver found these equivalences.

Code: Select all
1)6g==4r9c2 [] 6i – 4r9c2  []6h;6j  6r9c2 – 4r9c2  => 4r9c2 forces 6g   6g forces 4r9c2 (trivial)
2)6g==4r1c3 []6h;6i  -  4r79c2 =  4r13c2 -  4r3c1 []6j  5r8c1 – 5r3c1 = 5r1c3 – 4r1c3 =>4r1c3 forces 6g
[]4r13c2 - 6g   []4r3c1 - 5r3c1  = 5r1c3 - 5r8c3  - 6g  =>6g forces 4r1c3


Code: Select all
3)6j==4r7c2 []  6g;6i  1r7c2 - 4r7c2  []6h – 4r7c2 =>4r7c2 forces 6j   6j forces 4r7c2 (trivial)
4)6j==4r3c1 []6h;6i 4r3c12 – 4r3c1 []6g  5r8c3 – 5r1c3 = 5r3c1 – 4r3c1 => 4r3c1 forces 6j
    []4r13c2 – 6j   []4r1c3 - 5r1c3 = 5r3c1 - 5r8c1 6j  => 6j forces 4r3c1


Still 2) and 4) may be limit to be included in a scope of “vicinity analysis”, but are much simpler that the first shot on Easter Monster.

I continue with two lots of equivalences:

r1c2r2c13 (3&8)==8r1c2 (2&8)==8r2c3
r1c2r2c1r3c2 (7&8)==8r3c2 (4&8)==8r2c1
r1c2r2c3r3c2 (4&8)==8r2c3 (2&8)==8r1c2
r7c2r8c13 (4&5)==4r7c2 (4&6)==4r8c3
r7c2r8c1r9c2 (1&4)==4r9c2 (4&8)==4r8c1
r7c2r8c3r9c2 (4&6)==4r7c2 (4&8)==4r8c3

r4c7r5c8 (2&8)==1r4c8 (2&6)==1r6c7
r1c23r3c1 (3&4)==8r2c1 (4&7)==8r3c2
r1c78r3c9 (8&9)==3r2c7 (6&9)==3r3c8
r12c7r3c9 (8&9)==3r1c8 (1&8)==3r2c9
r1c7r23c9 (8&9)==3r3c8 (6&8)==3r2c7
r1c7r3c89 (8&9)==3r2c9 (1&9)==3r1c8
r7c23r9c1 (5&8)==4r8c1 (1&8)==4r9c2

In both lots, all “single candidates” have already been seen. This establishes new equivalences in super candidates. In the second lot, the candidate does not belong to the AC2 itself, but to the complementary one..


I thought “vicinity effects” were over. If you accept a looping process, the following lot is interesting as well.


Code: Select all
1     47A8   345g8  |3567y  389f 5678  |34i89 36h9   2     
2A38  9      37a8   |4      126  1267A |1h38  5      36H8 
345G8 2a48   6      |1235   389F 1258  |7     1H39   34I89
----------------------------------------------------------
24b68 5      14B7x8 |9      126  3     |128   1267D  678   
389   1Ì2Í6Î 389    |1É2Ê6Ë 7    4     |35c89 1Æ2Ç6È 35C89
2369  1267a  1379   |8      5    126   |1239  4      367x9
----------------------------------------------------------
7     1j48   4589k  |1235   34e8 1258  |6     2D39   3459 
456j  3      1J45   |1267d  126  9     |2d45  8      457D 
4589K 46J8   2      |3567   34E8 567y8 |3459  37d9   1 


We consider first two AC2 and the way they are seen by the solver at that point.

Code: Select all
r1c23r3c1     8r2c1.€O: (3&4)  9h: (7&8)  8r2c3.£T: (3&7)  3r2c1.$M: (4&8)  8r3c2.§N: (4&7) 

Code: Select all
r1c2r2c3r3c2  8r2c3.£T: (4&8)  4r1c2.$E: (2&4)  8r3c2.§N: (3&8)  8r1c2.$G: (2&8)  9q: (3&4)


Out of preceding equivalences:
r1c23r3c1 (3&4)==8r2c1; (4&7)==8r3c2
r1c2r2c3r3c2 (4&8)==8r2c3; (2&8)==8r1c2

In r1c23r3c1, (3&7) r1c23r3c1==(4&8)r2c13r3c2<=>8r2c3; (4&8) r1c23r3c1==(3&7)r2c13r3c2<=>3r2c1
In r1c2r2c3r3c2 4r1c2.$E: (2&4) 8r3c2.§N: (3&8) are trivial

Now we show 9h: (7&8)r1c23r3c1==9q: (3&4)r1c2r2c3r3c2

Code: Select all
In r1c2r2c3r3c2     []8r2c3. £T - 9h   []48r1c2 - 7r1c2.A  9h  []  8r3c2.§N - 9h   9h=>9q
In r1c23r3c1       []8r2c3. £T - 9q   []38r2c1 - 2r2c1.A  9q  []8r3c2.§N - 9q   9q=>9h

If you look on the puzzle how expand (7&8)r1c23r3c1 and (3&4)r1c2r2c3r3c2 this is trivial.

You have similar patterns and results in
Code: Select all
r1c2r2c13  3r2c3.£R: (2&3)  €O: (4&8)  8r1c2.$G: (3&8)  8r2c3.£T: (2&8)  9i: (3&4) 
r1c2r2c1r3c2  9j: (3&4)  8r3c2.§N: (7&8) €O: (4&8)  8r1c2.$G: (3&8)  4r3c2.$N: (4&7) 
 9i: (3&4) r1c2r2c13==   9j: (3&4) r1c2r2c1r3c2   


Code: Select all
r1c78r3c9  9s: (3&6)  3r2c7.€N: (8&9)  3r3c8.&S: (6&9)  8r2c7.$S: (3&9)  3r2c9.€M: (6&8) 
r12c7r3c9  9z: (1&3)  3r1c8.&T: (8&9)  3r2c9.€M: (1&8)  3r3c8.&S: (1&9)  9r1c8.$W: (3&8) 
9s: (3&6) r1c78r3c9==9z: (1&3) r12c7r3c9


Code: Select all
r1c7r23c9  %a: (3&6)  3r3c8.&S: (8&9)  9r3c8.$T: (3&8)  3r1c8.&T: (6&9)  3r2c7.€N: (6&8) 
r1c7r3c89  %b: (1&3)  3r2c9.€M: (8&9) 3r2c7.€N: (1&8)  8r2c9.$V: (3&9)  3r1c8.&T: (1&9)   
%a: (3&6) r1c7r23c9  ==  %b: (1&3) r1c7r3c89


Code: Select all
r7c23r9c1  %i: (1&4)  4r8c1.§K: (5&8)  4r8c3.§J: (1&5)  5r8c1.€C: (4&8)  §L: (1&8) 
r7c2r8c3r9c2  §L: (4&5)  8r7c2.€H: (6&8)  §M: (4&6)  %r: (5&8)  4r8c3.§J: (4&8) 
 (1&4) r7c23r9c1 ==(5&8) r7c2r8c3r9c2


Code: Select all
r7c2r8c13  §M: (4&5)  4r8c3.§J: (4&6)  %j: (5&8)  4r8c1.§K: (4&8)  5r8c3.€G: (5&6) 
r7c2r8c1r9c2  §L: (1&4)  %k: (5&8)  4r8c1.§K: (4&8)  8r9c2.€D: (1&8)  §M: (4&5) 
%j: (5&8) r7c2r8c13 == %k: (5&8) r7c2r8c1r9c2


This ends what I have seen on "vicinity effets" in the start of EM. Its likely easy to introduce tem in the solver, but necessary to have a print showing used effects. As usual, this will be the toughest part of the task, balancing between to much information and lack of information.
champagne
2017 Supporter
 
Posts: 5742
Joined: 02 August 2007
Location: France Brittany

Postby champagne » Sun Feb 24, 2008 3:43 pm

VICINITY ANALYSIS

I explained earlier why this seemed to be a way to improve the solutions.
So, “vicinity analysis”, as “virus patterns” is a tool easy to handle and giving the capability to hand solvers to face harder puzzles.

“Virus patterns” have been somehow disappointing in the solver processing (out of SK loop identification). May be I did not use them properly.

“Vicinity effects” is in fact the replacement of a “couple tag” by a “candidate tag” when this is a trivial logic relation.

Here is the first row of “Ocean's New Year's present for ravel #2”

Code: Select all
479   6a789      45d789 |3589  357g    1      |6A89Ç  2       3E4e   


- r1c19 is an AC2.
- (3&4)r1c19 <=> 4r1c1.

We can apply the tag of “4r1c1” to “ (3&4)r1c19.”
In case some “couple tag” are invalidated, you find similar possibilities . The general rule is described here below in the puzzle Easter Monster after the SK loop has been cleaned and after it has been shown that (2&7)r2c13;(4&8)r13c2….. are not valid.:


Code: Select all
1     47A8   345g8  |3567y  389f 5678  |34i89 36h9   2     
2A38  9      37a8   |4      126  1267A |1h38  5      36H8 
345G8 2a48   6      |1235   389F 1258  |7     1H39   34I89
----------------------------------------------------------
24b68 5      14B7x8 |9      126  3     |128   1267D  678   
389   1Ì2Í6Î 389    |1É2Ê6Ë 7    4     |35c89 1Æ2Ç6È 35C89
2369  1267a  1379   |8      5    126   |1239  4      367x9
----------------------------------------------------------
7     1j48   4589k  |1235   34e8 1258  |6     2D39   3459 
456j  3      1J45   |1267d  126  9     |2d45  8      457D 
4589K 46J8   2      |3567   34E8 567y8 |3459  37d9   1   


We look at the AC2: r2c13. Are still valid (2&3) (7&8) (2&8) (3&7) .
We extend the four valid cases.

Code: Select all
(2&3)  2r2c1    3r2c3
(7&8)             7r2c3   8r2c1
(2&8)  2r2c1            8r2c3
(3&7)        3r2c1  7r2c3

No doubt

Code: Select all
3r2c3 <=> (2&3)   3r2c1 <=> (3&7)   8r2c1 <=> (7&8)   8r2c3 <=> (2&8)


For the time being, as here, the solver applies “vicinity effects” only in AC2 having two cells.

If in the expansion process one candidate appears only once, we have established a “vicinity effect” relation.

Other situations will come for sure, but this is enough to start.

These “vicinity effects” are establishing equivalences between a “couple tag” and a candidate. Equivalences between “couple tags” are normally seen during the tagging procedure. This is not so easy to follow. Nevertheless, this can be checked easily in hand processing.

Here after an example in “Ocean's New Year's present for ravel #2” just after the first fix r5c1=6. (easy step)

Code: Select all
479   6a789      45d789 |3589  357g    1      |6A89Ç  2       3E4e   
3     1j2è6A7é89 2789   |2f89  4       7G89   |5      1Å6a8   189á   
1l249 1289       245D89 |6     2F35    3589   |1j89   3e4E    7     
--------------------------------------------------------------------
279   23h78t9    1      |23459 2357    34579  |278    4P5i78  6     
6     4          23H7   |1k235 8       357    |127    9       125I   
5     2789       278v9  |1249  1M2ì6b7 46B79  |3      1478    124E8 
--------------------------------------------------------------------
8     1379       3ã4c79 |134C5 1356B   2      |16a7S9 13567   1359   
127   5          237    |138W  9       36b8   |4      136B7r8 12N38 
124C9 1239       6      |7     135     34c58U |12O89  1358    123589


At that point the solver establishes that “super candidates“
r5c36 (2&7);r5c37 (1&2);r5c49 (3&5);r5c367 (1&2);r5c469 (3&7);r5c479 (3&5)
are not valid.

For the solver all these “super candidates” have the same tag. You can easily check that if you start from any of these “super candidates”, others are there.

If A=>B and B=>A, you conclude A<=>B.

The solver does not work that way, and in that case, it finds the equivalence due to the specific pattern of the row 5.
As a matter of fact, it can happen that a human solver finds easily such equivalences and the solver not. Again some room for improvement.

I would now comment on “Virus patterns”. We have here a chain of virus patterns (as I defined them)

Code: Select all
r8c46 r79c5 r13c5 r2c46 r2c89  r13c7
3816  1635  3527  2789  8916  1689   


Other virus patterns exist but are not chained r5c79 r6c23 r8c13 r45c7.

Note: my definition of virus patterns excluded patterns as r5c36. May be there is some improvements to get out of them.

The solver establishes at that point that “r8c46 (1&6)” is not valid thru that AIC
[]1r8c4 - 1r56c4 = 1r6c5 - 6r6c5.b

Unhappily, it’s not a start for virus expansion. Virus expansion would have required r8c46(3&8) not valid.

I am looking for such examples to check whether the solver is working properly.
champagne
2017 Supporter
 
Posts: 5742
Joined: 02 August 2007
Location: France Brittany

Postby champagne » Sun Mar 09, 2008 1:35 pm

For the time being, I have not that much to do in the solver. All known puzzles are cracked and hardest puzzles producers have some difficulties to pass Golden Nugget.

So I am working on improving the solving solutions and preparing a personal web site (already opened with a French draft in construction) to describe, in addition of the method, the programming options and to deliver the sources(C+).

Doing so, I thought over how to explain in an easier way the solutions of hardest puzzles.

I will make a trial in two posts,

That one will develop a model of the tagging process in “rules” and “constraints”. The second one will explain thru drawings the solving process for hardest steps.


Model used in tagging


To build that model, we need specific definitions:

Candidate: any potential digit that can still be part of the solution in a cell; (nothing new, just for the next topic)

Group of candidates: a set of candidate having a solving potential. In a group of candidates, at most one is valid. Most common groups will be:
The candidates of one digit belonging to two units,
The candidates of one digit belonging to an ALS, an AHS …..
Any set of candidates belonging to a cell.
Like super candidates here after, groups of candidates validation does not lead generally to a fix, but at least provides a clearing of candidates

Super Candidate: any potential group of digits that could change an unlocked set in a locked set.
I applied the concept of super candidate to sets with four unknown digits, two of them valid, this is I think the general definition for super candidates in that process.
The set of digits can have several patterns in the unlocked set.

Strong and weak link:
We use the standard definition of strong and weak link /inference. We only need an extension based on the basic definition:

Strong link between two entities: One has to be true (valid), only one is true (valid)
Weak link between two entities: if one is True (valid), the other one is False (not valid)

Chains: We will use two chains

Chain of strong links: That well known chain is used in the tagging procedure. Thru Chain of strong links: we define useful tags and associated tags (at least the collection at the start of the process)

AICs (Alternate inference chains): we are using such chains with tags. They have exactly the same properties as the AICs made of candidates.
The canonical AIC in the full tagging process has a weak link at each end. This is not the preferred form in other methods. Any canonical AIC defines a distant weak link using both ends. In drawings, a canonical AIC will be shown as a line Bold Blue

Tag: A tag is a kind of container having the following properties

1) If the puzzle solution makes one component True (valid), all components are True (valid).
2) If the puzzle solution makes one component False (not valid), no components is True (valid).
3) If two tags have one component each having a strong link with the other one, any component of the first tag has a strong link with any component of the other tag.
4) If two tags have one component each having a weak link with the other one, any component of the first tag has a weak link with any component of the other tag

Rules 1) and 2) is the equivalence relation with the short ==The smallest tag has one known Tag component (the smallest Tag component is a candidate)

With such a set of rules, a tag can be used in a chain in place of any component.



Tag component (TC):

A tag Component is any entity that complies with tag specifications;
A candidate; a group of candidates, a super candidate are tags components.
If a tag candidate is proven valid, we have at least some clearing of candidates. In the best case, we have one or several fix.
In the future, other TCs could be added. As long as they fulfill the tag requirements, there is no problem.

One tag component can enter one and only one tag. If it happens during the process that two tags (or two tags components of different tags) have an equivalence link, this means that we have open one tag container in excess. One must be emptied and all tag components put in the other. This has been called a merging of tags.

Although this can happen due to imperfect tagging procedure, new equivalences are normally generated by Nice loops.



Associated tag :

We have the associated tag of a tag if both are linked by a strong link relation:
We can also say that there is a strong link between associated tags
Most often, such a relation is marked using upper case lower case letters.

If the tag is represented by a candidate, we will use the ~ sign to indicate the associated tag.

If 5r1c2 is a candidate, ~5r1c2 is the tag associated to the tag in which r1c2 is included.

Choice: A collection of tags where one and only one is valid.

Native choice: A choice where tags are represented by candidates, groups or super candidates expressing a basic choice.

Candidates of a cell are forming a choice,
Row, column or box candidates of the same digit (groups authorized) are forming as many choices as you can find combining candidates and groups including all candidates with no overlapping,
AC (almost cell) components (the groups of candidates of the same digit for the unknown digits) are forming a choice.
AC2, components (the couple tags still valid.) are forming a choice.

=======================


These definitions are too general to generate a solving process . The scope is too large, it must be reduced thru constraints. The constraints are given to create an homogeneous set of tags and choices, leading to clearing of candidates.

We have several examples of constraints:

Ground level:

We want chains crossing exclusively row, columns and boxes, We use bi values of candidates of the same digit in rows, column and boxes. Groups are authorized (candidates of the same digit belonging to two units). No choice activated.

Level one

Same as ground level, adding cells in chains and bi values in cells.


Level “T “ chains


This should be validated by Denis, but for me, the first “T” chain set would have been:

Ground zero without groups, plus level one, Choices (cells only ??) and groups of candidates complementary to any isolated candidate.

Meantime, the scope has been extended.
I have in mind to create a similar level in the solver to facilitate comparisons..

Level two

Level one plus ALS AHS plus choices (cells and on digit in one unit)…….


Rules applied to a group of candidates

We will consider a group of candidates and the candidates belonging to the group.

Rule 1: A candidate in weak link with a group of candidates is in weak link with any of the candidates

Rule 2: If a candidate in weak link with each of the candidates of a group, it is in weak link with the group.

Rule 3: If two groups of candidates are in weak link each candidate of the first group is in weak link with each candidate of the second one.

This is trivial, but good to keep in mind. The same rules can be written with strong links and extended to tag components and tags..


Example of application of these rules :

Code: Select all
             a
  ___________b
 /___________c
X____________d        (a,b,c,d  are the candidates of a cell)


Let’s assume a,b,c,d is a the list of candidates in a cell or the tags associated to theses candidates.
‘X’ is a tag and each line means that we have a canonical AIC linking X,b X,c and X,d respectively. If we define a tag ‘Y’ for the group (b;c;d) Applying the rules, we can say that

X and Y are in weak link. But Y is complementary to a, so we should have identified the group as tagged A


Nothing more to say about the model. Next psot will develop drawings
champagne
2017 Supporter
 
Posts: 5742
Joined: 02 August 2007
Location: France Brittany

Postby champagne » Sun Mar 09, 2008 2:17 pm

Note I intend to use colors here, but it seems dificult to mix colors with fix lenght size. Sorry if I didn't acheve exactly what I intended to do.



We have seen in the previous post that we have a common set of rules with constraints giving a level of difficulty and a certain potential of resolution.

In the common set, we have to describe the common rules applied to the choices.

Code: Select all
              a
  ___________|b|
 /___________|c|
X____________|d|     b,c,d is the group A 


This is the diagram we have used at the end of the previous post. This is a key diagram.

In any choice (a set of tags, one and only one valid) if all the tags but one are in weak link with the same external tag, The external tag is in weak link with the associated tag of the last tag of the choice. So here we say that XA is a weak link.

In a T&E process, this means that ‘X’ true will force ‘a’ True.

Using that key diagram, we can easily conclude in the following situations.

Code: Select all
              a __________Y
  ___________|b|
 /___________|c|
X____________|d|     b,c,d is the group A




We can write that sequence

X _______ A a _________ Y
We have replaced the three AICs by the corresponding group. Then, the two pieces of AIC are merged to give the final canonical AIC
X ___________ Y

Code: Select all
             a ________x
  ___________|b|
 /___________|c|    If ‘Y’ is ‘x’, we have a  Nice loop
X____________|d|    X==a  x==A

Note: we have no guaranty that such a Nice loop has some clearing effect.

Code: Select all
              a _________X
  ___________|b|
 /___________|c|     If ‘Y’ is ‘X’ than ‘X’ is cleared
X____________|d|   . (we could in that example have concluded directly)




Our last elementary diagram now


Code: Select all
              a ______________Y
              b _____________/
  ___________|c|
 /___________|d|   
X____________|e|   . 


Following the previous ones, no problem. We create two temporary tags, let say z=(a,b) Z=(cde) and we have immediately
X ______ Z z ______ Y

In fact, there is no other use of Z,z, so the solver goes directly to
X ________ Y
As in the former case, we can end with a Nice loop X ___x or a clearing chain X___X.


The next point is “what if we have overlapping choices.”




Code: Select all
              e ______ ?         
   __________ f
  /      a __ g
 /______|b| \_h
X_______|c|   



Obviously, this is equivalent to X_____?. It would be found by the solver in that way:

First, the first diagram gives X ___A and consequently
X ____ g and X ___ h.
Then, the second diagram is seen equivalent to X ___?

If '?' is ‘x’, this is a Nice loop, if ? is ‘X’, ‘X’ is cleared, if '?' is another tag, we have a new distant link.

You can build any net of such elementary diagrams; they will be easily found by the solver.

We will see several examples extracted from the “full tagging examples”. Before entering the first example, we will define a simpler equivalence of the previous diagram. On can notice that if ? is ‘x’ or ‘X’, the search is over. Clearing chains and Nice loops are what we are looking for. So, in a search, the diagram establishes a new weak link X___Y. (for the solver, a bit is set to one).

Two “non canonical forms” that we will find.

Code: Select all
              ?       
         a __ g
  ______|b| \_h
X_______|c|   


In that situation ‘?’ can be ‘x’ or ‘X’. . Equivalent AIC would then be

Code: Select all
X___A = a___X  if ? is ‘x’
X___A = a ___x  if ? is ‘X’


We have now the canonical form and we see that the right end of the chain is the associated tag of ‘?’.

If ‘?’ is ‘x’, we have a clearing chain, if ‘?’ is ‘X’ it is a mice loop.



For the time being, choices (the basis to apply the diagram) are made out of:
Cell candidates
Row, column or box candidates of the same digit (groups authorized)
AC (almost cell) components being the groups of candidates of the same digit for the unknown digits
AC2, components being the couple tags still valid.

For each of these possible choices, we define a short for the diagram easy to handle.

Cell: __r1c2 |1 2 5|6 7| ___
Row __3r3|c25 c6|c7| ___
Column ___3c3|r25 r6|r7| __
Box ___3B2 |r4c4 r56c5|r6c7| ___
AC ___ AC:r1c237 | 2 5 | 8 9| ___
AC2 ___AC2:r2c13 | 1&5 6&7 1&8 | 1&7 7&8 | ___

These very simple shorts should be enough in most cases. If necessary, Additional lines will come as here

Code: Select all
 ___AC2:r2c13 | 1&5  6&7 1&8 | 1&7 7&8 | ___
 ________________|   |    |
 ____________________|____|


To avoid confusing pictures, a sub diagram will be reduced if possible to the equivalent weak link in the form :

____ WL|…..| ____

To see how it works , I take a small piece of Easter Monster solution. I ‘ll show, step by step, an equivalent drawing.

Code: Select all
1     47B8  345h8  |3567À  389g 5678  |34i89 36A9   2     
2B38  9     37b8   |4      1a26 267B  |1A38  5      36a8 
345H8 2b48  6      |1235   389G 1258  |7     1a39   34I89
---------------------------------------------------------
24c68 5     14C7z8 |9      126  3     |1a28  1267E  678   
389   1Í2Î6 389    |1Ê2Ë6Ì 7    4     |35d89 1M2È6É 35D89
2369  1267b 1379   |8      5    1L26  |239   4      367z9
---------------------------------------------------------
7     1j48  4589k  |1235   34f8 1258  |6     2E39   3459 
456j  3     1J45   |1267e  126  9     |2e45  8      457E 
4589K 46J8  2      |3567   34F8 567À8 |3459  37e9   1     


We started with

Code: Select all
#[]a/1r8c4   []1r5c8/1r3c8_1r2c7/1r2c5-a []1r5c4/1r8c4 []1r5c2/1r7c2_1r8c3/1r8c4
#[]j/a      1r8c3-J []1r8c5/1r2c5 []1r8c4/a|#


euivalent drawing is
Code: Select all
                             1r8 |c54 c5|c3.J|   
1r2c5.a ___ 1r5 |c8|c4 c2 | _______|   |
        \______________________________|       ___ WL |a  j|___



Then we had

Code: Select all
6r5c2==6r9c4
#[]6r5c2/§m   6r9c4-§M []6r5c4/6r5c2 []6r8c4/6r8c1_6r9c2/6r5c2
      []6r1c4/6r1c8_6r2c9/6r8c1_6r9c2/6r5c2
#[]ï/6r9c4   6r5c2-Ï  []6r5c8/6r1c8_6r2c9/6r8c1_6r9c2/6r9c4 []6r5c4/6r9c4


equivalent drawing :

6r5c2 ___ 6c4 |r5 r8|r9| ___6r5 |c8 c4|c2| loop


next sequence

Code: Select all
2r2c5==6r2c6
#[]2r2c5/£s   6r2c6-£S  []7r2c6==2r2c1-B/2r2c5 []2r2c6/2r2c5
#[]ö/6r2c6   2r2c5-Ö []1r2c5==6r2c9/6r2c6 []6r2c5/6r2c6


equivalent to

2r2c5 ___ r2c6 | 2 7 | 6 | ___r2c5| 1 6 | 2 | loop

last sequence

Code: Select all
6r9c6==6r6c2
#[]$e/6r9c6   6r6c2-$E []6r9c2/6r9c6 []6r5c2==6r9c4/6r9c6
#[]6r6c2/§Y   6r9c6-§y []6r9c2/6r6c2 []6r9c4==6r5c2/6r6c2


and equivalnce

6r9c6 ___ 6c2 |r9 r5 |r6 | ___ 9r9 | c2 c4 | c6 | loop

At that point I wrote

Code: Select all
We have now 6r5c2==6r9c4    2r2c5==6r2c6     6r9c6==6r6c2

Some weak links
#[]7r2c3-b/8r3c9  7r1c2-B []4r1c2/4r1c7_4r3c9/8r3c9 []8r1c2/8(r2c13)_8(r2c79)/8r3c9
#[]1r4c8/1r2c5   []1r2c5/1r2c7-h_1r3c8-H/1r4c8
#[]1r5c2/1r4c8   []1r8c5/1r8c3_1r7c2/1r5c2 []1r4c5/1r4c8 []1r2c5/1r2c7_1r3c8/1r4c8
#[]A/1r5c2   1r3c8-a  []1r5c8/1r5c2 []1r4c8/1r5c2|#


Here, the las two lines are equivalent to


1r5c2 ___ 1c5 | r8 | r4 r2 | __ 1r4c8


for the first one and

Code: Select all
                    1c8 | r5 r4 | r3.a |
1r5c2 ____________________| /
  \                        /     
   \__1c5 | r8 | r4 r2 | _/


if yous consider bth.
The following step is slightly more difficult to draw

Code: Select all
6r6c9==6r2c6==2r2c5
#[]ö/6r6c9   6r2c6-Ö []6r6c6/6r6c9 []6r9c6==6r6c2/6r6c9 []6r1c6/6r1c8_6r2c9/6r6c9
#[]Ö/6r6c1   []1r5c2/1r2c7.A|#_1r2c5/2r2c5-Ö []2r5c2/2r3c2_7r2c6/6r2c6-Ö []6r5c2/6r6c1
#[]Ö/$X      6r6c9-$x []6r6c6/6r2c6-Ö []6r6c2==6r9c6E/6r2c6-Ö []6r6c1/Ö|#


Code: Select all
Loop 6r6 |c9 | c1 c2 c6 |
               |   |_|__________________
               ¬|________                |
                        |               |
                 r5c2 | 6 | 1 5 |       |
                            | |_________|
             _______________|           |       
            |               |           |   
     1c5 | r8 | r4 r2 | _   |           |
                         |  |           |
                  1c8 | r4 r5 | r3.a | _|
                                        |
6r6c9 __ 6c6 | r6 r9 r1 | r2.Ö | ______ |




This will be the temporary end of this post as long as I have not found the proper way to show such drawing including color and fix length text.
champagne
2017 Supporter
 
Posts: 5742
Joined: 02 August 2007
Location: France Brittany

Postby champagne » Sun Jun 22, 2008 2:59 pm

No big change in the full tagging process for long, I made recently a small improvement in Vicinity Analysis in “virus patterns” to try to push the solver as close as possible of the concept of “scenarios analysis” I made in the thread “fighting against the SK loop”

http://forum.enjoysudoku.com/viewtopic.php?t=6085


I am analyzing the results, but I am somehow disappointed. Although the solver has now a shorter path, that will be soon on my web site, It did not killed the main layers of the Sk loop.

This means that building a scenario, we bring something more and I tried to figure out what it could be on a very simple example.

Let us assume that we have two ternary choices (let say two cells having each three candidates abc def).
We assume we can link two candidates x and y to these cells thru AICs in the following ways

Code: Select all
1) x _ a     d _ y
   x _ b     e _ y
       c  -  f
2) x _ a     d _ x
   y _ b     e _ y
       c  -  f


In the first case, x – y is a derived weak inference commonly used in AICs nets.

In the second case we have a derived weak inference as well.

(x&y)=>c – f <=(x&y)

(x&y) is not valid which is exactly the definition for a weak inference x – y.

As far as I remember, I have never seen such a very simple net used.

What is for sure is that my solver does not use it for the time being. Such derived weak inferences open new possibilities before using ALS ACs ….

I think the next plus in the solver will be an intermediate step around level 1+ including such derived weak inferences.
champagne
2017 Supporter
 
Posts: 5742
Joined: 02 August 2007
Location: France Brittany

Postby Steve K » Sun Jun 22, 2008 6:57 pm

Chamapgne - I doubt this will be of any use, but perhaps:
The algorithmic approach that I use to solve the very difficult puzzles is basically a link counting device between nodes. Mentally I place the nodes into one type of deduction, which I call a Mixed Block Matrix. If the matrix resolves at any time to nxn, a deduction is reached. However, one can arbitrarily force the matrix into nxn at any time. The items forced into the first column become a derived strong inference set, which I remember as a quantum group. In cases whereas it is possible to prove that the derived strong inference set is also a weak inference set, I have derived an entire quantum "cell", which can then be used just like any other cell. Store in memory enough of these quantum "cells", or groups, and most devious puzzles will unlock. A walk-thru of the idea is available at http://212.188.181.131/SudokuThread.asp?fid=4&sid=10183&p1=1&p2=11
where I stumble through strm's 11.4 puzzle. Although I consider transformations of the puzzle, they are not required and basically serve as a shortcut in understanding the symmetry.
Steve K
 
Posts: 98
Joined: 18 January 2007

Postby champagne » Mon Jun 23, 2008 10:33 am

Steve K wrote:Champagne - I doubt this will be of any use, but perhaps:
The algorithmic approach that I use to solve the very difficult puzzles is basically a link counting device between nodes. Mentally I place the nodes into one type of deduction, which I call a Mixed Block Matrix. If the matrix resolves at any time to nxn, a deduction is reached. However, one can arbitrarily force the matrix into nxn at any time. The items forced into the first column become a derived strong inference set, which I remember as a quantum group. In cases whereas it is possible to prove that the derived strong inference set is also a weak inference set, I have derived an entire quantum "cell", which can then be used just like any other cell. Store in memory enough of these quantum "cells", or groups, and most devious puzzles will unlock. A walk-thru of the idea is available at http://212.188.181.131/SudokuThread.asp?fid=4&sid=10183&p1=1&p2=11
where I stumble through strm's 11.4 puzzle. Although I consider transformations of the puzzle, they are not required and basically serve as a shortcut in understanding the symmetry.


I started reading and I reached point 1g) which bring me very close to step five in my post (if I understood your text in the proper way).

The vocabulary is not the same, the philosophy is not the same, but we are turning around the same things.

From what I know of Matrix processing, it's faster and more flexible that my process .

I need time to go to the end and I'll come soon with questions.

A preliminary one: is "sis" a short for symetries? If not what does it mean.
champagne
2017 Supporter
 
Posts: 5742
Joined: 02 August 2007
Location: France Brittany

PreviousNext

Return to Advanced solving techniques