Exotic patterns a resume

Advanced methods and approaches for solving Sudoku puzzles

Re: Exotic patterns a resume

Postby champagne » Tue Jun 26, 2012 5:30 am

daj95376 wrote:In my previous post, I was looking for confirmation that the puzzle didn't contain an acceptable SK-Loop. From the responses, I'm not sure if there's a consensus or not. So, I'll just proceed with puzzles that I consider to contain an (acceptable to me) SK-loop.


It would be interesting to have more details on which SK loops in my file of "sk loop seen" you don't recognise.
Your former example is a valid SK loop



daj95376 wrote:Consider this puzzle:
In each case, the puzzle's solution contains a single value from each side of the (ab=cd) term.

FWIW: This happens in all 1,944 (acceptable to me) SK-loops that I found in champagne's 31,804 puzzles from HARD_11.

Now, I'm probably the only one who finds this interesting.


May be we have not been clear but this is the point noticed earlier by ronk.
There is a statistical reason to have that, but we have so far no logical proof that it must be, so it has to be established in each case.

The statistical reason is very simple. each belt of your "ab" or "cd" is valid or false in bloc.
Here is the better chance to have a contradiction.
champagne
2017 Supporter
 
Posts: 5753
Joined: 02 August 2007
Location: France Brittany

Re: Exotic patterns a resume

Postby daj95376 » Tue Jun 26, 2012 6:16 am

It's obvious that I'm in way over my head on understanding what makes SK-loops work. So, I'm bowing out.
daj95376
2014 Supporter
 
Posts: 2624
Joined: 15 May 2006

Re: Exotic patterns a resume

Postby ronk » Tue Jun 26, 2012 12:22 pm

daj95376 wrote:It's obvious that I'm in way over my head on understanding what makes SK-loops work. So, I'm bowing out.

daj95376, you're doing just fine, so please don't "bow out."

daj95376 wrote:In each case, the puzzle's solution contains a single value from each side of the (ab=cd) term.

FWIW: This happens in all 1,944 (acceptable to me) SK-loops that I found in champagne's 31,804 puzzles from HARD_11.

Now, I'm probably the only one who finds this interesting.

In short order you've done the "worthwhile exercise" I mentioned in my prior post, so this result is very interesting to me.

You've likely identified at least 95% of the sk-loops that champagne's program finds. (We would have an exact percentage if champagne searched all 31,804 puzzles, or you searched only the first 30,000 puzzles.) IMO the "other 5%" are lost when patterns have "a single value from each side of the (ab=cd) term" as the only possibility. This might be easy to fix.

daj95376 wrote: (79=18)r56c5 - (18=79)r4c46 - (79=23)r4c89 - (23=69)r56c7 -
(69=18)r89c7 - (18=57)r7c89 - (57=23)r7c46 - (23=79)r89c5 - SK_loop =>

r4c2<>79; r7c2<>57; r9c4<>2; r8c6<>3; r7c1<>5; r1c7<>6; r4c3<>7; r2c7,r3c5<>9

In NL notation this loop could/would be written as ...
Code: Select all
 r56c5 -18- r4c46 -79- r4c89 -23- r56c7 -69- r89c7 -18- r7c89 -57- r7c46 -23- r89c5 -79- continuous loop
... which better illustrates the sharing of link digits between AALSs.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Re: Exotic patterns a resume

Postby daj95376 » Tue Jun 26, 2012 5:52 pm

ronk wrote:You've likely identified at least 95% of the sk-loops that champagne's program finds. (We would have an exact percentage if champagne searched all 31,804 puzzles, or you searched only the first 30,000 puzzles.) IMO the "other 5%" are lost when patterns have "a single value from each side of the (ab=cd) term" as the only possibility. This might be easy to fix.

Of the 1700 SK-loop puzzles listed by champagne in his HARD_11 folder, I questioned the only puzzle that my solver didn't accept. I don't understand the mechanism that's involved to allow the "loop" eliminations. I assumed that it was based on pairs of candidates in pairs of cells residing in a loop environment. Now that one pair of candidates can reside in one cell, I've lost interest.

If you go back to the puzzle in question and perform r7c2<>9 before attempting to create the SK-loop, then the absurdity of:

r8c12 -48- r79c2

might become more apparent. As far as I'm concerned, the logic supporting an SK-loop can't be expressed as a traditional loop... be it in Eureka or NL notation. Just as the logic for n-value Template eliminations can't be expressed outside their boolean context.
daj95376
2014 Supporter
 
Posts: 2624
Joined: 15 May 2006

Re: Exotic patterns a resume

Postby ronk » Tue Jun 26, 2012 7:55 pm

daj95376 wrote:If you go back to the puzzle in question and perform r7c2<>9 before attempting to create the SK-loop, then the absurdity of:

r8c12 -48- r79c2

might become more apparent.

The notation merely shows that digits <48> are shared by the two AALSs, for which there are four possibilities: r79c2 holds none, either one, or both of the restricted common digits. For the case when r79c2 ultimately holds only one of the digits, why must the digits appear as candidates in two cells?
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Re: Exotic patterns a resume

Postby champagne » Tue Jun 26, 2012 8:48 pm

daj95376 wrote:[

If you go back to the puzzle in question and perform r7c2<>9 before attempting to create the SK-loop, then the absurdity of:

r8c12 -48- r79c2

might become more apparent. As far as I'm concerned, the logic supporting an SK-loop can't be expressed as a traditional loop... be it in Eureka or NL notation. Just as the logic for n-value Template eliminations can't be expressed outside their boolean context.


I am busy with the game, but let me comment quickly.

There are several ways to justify the eliminations in the SK loop

I use (see the post at the start where the extended sk definition of the sk loop is given) the "virus chain" which is just one way to look at the loop.

In any piece of logic as that one (what I call a virus chain link)

79- r4c89 -23- r56c7 -69

you have (forget for a while the small problem above)

23 r4c89 => 69 r56c7
23 r56c7 => 79 r4c89

If you can extend the chain as here

79- r4c89 -23- r56c7 -69- r89c7 -18

you have
23 r4c89 => 18 r89c7
69 r89c7 => 79 r4c89

If you can extend the chain till the point where you have a loop, then the condition at both end forces eliminations.
As you can take any start in the loop, you can justify eliminations at each point.

It works exactly as a classical AIC loop.

Now the special case you have seen.

First of all, we only need one valid way in the loop to conclude.
Second point, if you turn in the right way, you cross the tough point with the condition
" both digits sharing the cell are false" so the logic is valid.

When I wrote earlier that I see a possible window for a bug, I was thinking of a situation where both ways would be locked.
I have at the moment no guaranty that the logic would work. It is an open point

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

Re: Exotic patterns a resume

Postby ronk » Tue Jun 26, 2012 10:05 pm

champagne wrote:If you can extend the chain as here

79- r4c89 -23- r56c7 -69- r89c7 -18

Interesting, when did you start using this notation?

champagne wrote:Now the special case you have seen.

First of all, we only need one valid way in the loop to conclude.
Second point, if you turn in the right way, you cross the tough point with the condition
" both digits sharing the cell are false" so the logic is valid.

What "logic is valid?" [edit: Oh, I guess you mean the loop is a continuous loop.]
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Re: Exotic patterns a resume

Postby champagne » Wed Jun 27, 2012 5:39 am

ronk wrote:
champagne wrote:If you can extend the chain as here
79- r4c89 -23- r56c7 -69- r89c7 -18

Interesting, when did you start using this notation?


this I copied from the ongoing discussion.

Usually, I show the loop in that way (copied from the first sk loop example on my website)

r2c13 r13c2 r79c2 r8c13 r8c79 r79c8 r13c8 r2c79 loop
3827 2748 4816 1645 4527 2739 3916 1638

But if your question refers to the logic of the chain, this has been done and written if I am right in autumn 2007.







ronk wrote:
champagne wrote:Now the special case you have seen.

First of all, we only need one valid way in the loop to conclude.
Second point, if you turn in the right way, you cross the tough point with the condition
" both digits sharing the cell are false" so the logic is valid.

What "logic is valid?" [edit: Oh, I guess you mean the loop is a continuous loop.]


yes, you can expand the chain and come to the loop in one of the 2 ways crossing the difficulty with a "false".

But again, even if we face 2 locked ways, it's possible that the other ways to prove the validity of eliminations still work.
It would be interesting to have one example.

So far, I keep my code untouched. May-be one day the bug if any will appear.
champagne
2017 Supporter
 
Posts: 5753
Joined: 02 August 2007
Location: France Brittany

Re: Exotic patterns a resume

Postby David P Bird » Sun Jul 08, 2012 11:40 pm

Champagne, I've been able to find multiple eliminations in three of your puzzles using my Shark implementation of Multi-fish but I suspect that your solver can already find them.

They are:
....5...9.5.1...3.....37...2..6..8...6..1..7...4..5.....9.....2.3...1.6.8.....4..;136;elev;117;2BN D1D3
Digit set (2489): 14 eliminations in 13 cells
.....6.8...71..2.....32...1..1.4...7.6.....5.9.........9.........42....38....5.7.;2325;elev;L206;12347;
Digit set (5689): 17 eliminations in 13 cells
1...5......7.....6.897.......89....3.7.......5...3.4...3.6....8.....21......4..2.;5586;elev;L550;1245;
Digit set (6789): 17 eliminations in 12 cells

If you have time, please will you check that you get similar results? They need not be identical as follow-on eliminations will probably give the same final reduction.

PS I really enjoyed watching the manic FDJ team manager today as his rider Pinot led in the final 2km of the Tour de France!
David P Bird
2010 Supporter
 
Posts: 983
Joined: 16 September 2008
Location: Middle England

Re: Exotic patterns a resume

Postby pjb » Mon Jul 09, 2012 1:45 am

Dear David / Champagne

I found Multi-fish patterns for the second and third puzzles mentioned above by David, the second appearing the same but the third different:
Code: Select all
.....6.8...71..2.....32...1..1.4...7.6.....5.9.........9.........42....38....5.7.
Found Multi-Fish pattern with base set of 5,6,8 and 9
16 Truths = {5689R2, 5689R3, 5689R4, 5689R8}
16 Links = {56c1, 58c2, 89c6, 69c8,  2n5, 2n9, 3n3, 3n7, 4n4, 4n7, 8n5, 8n7}
17 Eliminations:  29<>4, 37<>4, 37<>7, 47<>3, 85<>1, 85<>7, 87<>1, 11<>5, 12<>5, 56<>8, 56<>9, 66<>8, 68<>6, 71<>5, 71<>6, 76<>8, 78<>6

1...5......7.....6.897.......89....3.7.......5...3.4...3.6....8.....21......4..2.
Found Multi-Fish pattern with base set of 1,2,4 and 5
19 Truths = {124R2, 1245R3, 1245R4, 1245R5, 1245R7}
19 Links = {24c1, 12c5, 145c6, 25c7, 145c8,  2n4, 3n9, 4n2, 5n3, 5n4, 5n9, 7n3}
15 Eliminations:  24<>3, 24<>8, 42<>6, 53<>3, 53<>6, 54<>8, 59<>9, 16<>4, 17<>2, 18<>4, 66<>1, 68<>1, 81<>4, 96<>1, 96<>5


However, the first one is a problem: I got 16 truths and 17 links for the base set of 2489, and couldn't see a way around it. Can you help by giving more details for your Multi-fish result?
Thank you,
Phil
pjb
2014 Supporter
 
Posts: 1763
Joined: 11 September 2011
Location: Sydney, Australia

Re: Exotic patterns a resume

Postby daj95376 » Mon Jul 09, 2012 6:10 am

FWIW: My templates solver listed the following combinations as having potential Multi-Fish scenarios.

Code: Select all
Puzzle #1:   136;elev;117;2BN D1D3     <2489>
Puzzle #2:   2325;elev;L206;12347;     <1234>, <5689>
Puzzle #3:   5586;elev;L550;1245;      <1245>, <6789>
daj95376
2014 Supporter
 
Posts: 2624
Joined: 15 May 2006

Re: Exotic patterns a resume

Postby champagne » Mon Jul 09, 2012 6:46 am

pjb wrote:Dear David / Champagne

I found Multi-fish patterns for the second and third puzzles mentioned above by David, the second appearing the same but the third different:
Code: Select all
.....6.8...71..2.....32...1..1.4...7.6.....5.9.........9.........42....38....5.7.
Found Multi-Fish pattern with base set of 5,6,8 and 9
16 Truths = {5689R2, 5689R3, 5689R4, 5689R8}
16 Links = {56c1, 58c2, 89c6, 69c8,  2n5, 2n9, 3n3, 3n7, 4n4, 4n7, 8n5, 8n7}
17 Eliminations:  29<>4, 37<>4, 37<>7, 47<>3, 85<>1, 85<>7, 87<>1, 11<>5, 12<>5, 56<>8, 56<>9, 66<>8, 68<>6, 71<>5, 71<>6, 76<>8, 78<>6

1...5......7.....6.897.......89....3.7.......5...3.4...3.6....8.....21......4..2.
Found Multi-Fish pattern with base set of 1,2,4 and 5
19 Truths = {124R2, 1245R3, 1245R4, 1245R5, 1245R7}
19 Links = {24c1, 12c5, 145c6, 25c7, 145c8,  2n4, 3n9, 4n2, 5n3, 5n4, 5n9, 7n3}
15 Eliminations:  24<>3, 24<>8, 42<>6, 53<>3, 53<>6, 54<>8, 59<>9, 16<>4, 17<>2, 18<>4, 66<>1, 68<>1, 81<>4, 96<>1, 96<>5


However, the first one is a problem: I got 16 truths and 17 links for the base set of 2489, and couldn't see a way around it. Can you help by giving more details for your Multi-fish result?
Thank you,
Phil


hello David and phil ,

Nice work phil, I'll study that to-day mainly to see if I can design a new pattern out of these examples.

No surprise, in the fact that none of these multi fish was detected by my solver:

the second and the third are on the list of "something to find" and I did not introduce a new pattern so far
the first one has a jexocet pattern and no multi fish seen by my solver.
I'll check in the data base to see the frequency of puzzles having both an exocet and a multi-fish pattern

David, I agree with Phil's remark, it would help if you could give (with any notation) the list of sets and link sets you use.

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

Re: Exotic patterns a resume

Postby David P Bird » Mon Jul 09, 2012 8:13 am

Champagne, the Shark approach to Multi-fish I'm using is not based on truth and link sets or templates. As such it is much simpler and won’t necessarily always find all the eliminations available, but nevertheless it is fairly successful. Unless you've tried to follow my description of them you will probably find my explanations difficult. This is why I posed the question rather than giving the logic I used. (If you do try to follow that thread, ignore any post transferred there from the "bi bi pattern in the hardest puzzles" thread which doesn't belong there.)

I'll post the logic I used for puzzle 1 in that thread where it really belongs.

Phil, I believe you understand both approaches and have already translated puzzles 2 & 3 into truth and link sets. When you see my explanation for puzzle 1. you may be able to translate that too. When I've posted that, I'll check your eliminations for #3 against mine where you've used a near-complement digit set to me, but I expect they'll both produce the same end result. (daj has also made a similar finding.)

DPB
David P Bird
2010 Supporter
 
Posts: 983
Joined: 16 September 2008
Location: Middle England

Re: Exotic patterns a resume

Postby ronk » Mon Jul 09, 2012 10:11 am

champagne wrote:
pjb wrote:I found Multi-fish patterns for the second and third puzzles mentioned above by David ...
Code: Select all
.....6.8...71..2.....32...1..1.4...7.6.....5.9.........9.........42....38....5.7.
Found Multi-Fish pattern with base set of 5,6,8 and 9
16 Truths = {5689R2, 5689R3, 5689R4, 5689R8}
16 Links = {56c1, 58c2, 89c6, 69c8,  2n5, 2n9, 3n3, 3n7, 4n4, 4n7, 8n5, 8n7}
Nice work phil, I'll study that to-day mainly to see if I can design a new pattern out of these examples.
No surprise, in the fact that none of these multi fish was detected by my solver:
the second and the third are on the list of "something to find" and I did not introduce a new pattern so far

I see no essential difference between the <1368>-jellyfish in Artoi's 2012 "most difficult" and the <5689>-jellyfish in the above. That your solver finds the first but not the second is a surprise to me.

Image___Image
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Re: Exotic patterns a resume

Postby champagne » Mon Jul 09, 2012 10:21 am

ronk wrote:I see no essential difference between the multi-fish in Artoi's 2012 "most difficult" and in the above. That your solver finds the first but not the second is a surprise to me.


The reason is quite simple;

I put a limit in the number of permutations in the search to speed up the process.

The second one exceeded the limit.

I increased the limit. The process is slower, but the solver catches now the second example.

The third one is a pattern I have already seen, not studied by my code limiting the search to rows columns having all the digits of the base;

I am studying the first one which seems interesting.

Phill, could you give your rank 1 construction?
champagne
2017 Supporter
 
Posts: 5753
Joined: 02 August 2007
Location: France Brittany

PreviousNext

Return to Advanced solving techniques