Diabolical puzzle that has JSudoku stumped

Post the puzzle or solving technique that's causing you trouble and someone will help

Diabolical puzzle that has JSudoku stumped

Postby udosuk » Tue Apr 29, 2008 9:13 am

I personally prefer to find a solution via ALS-xz and medium hard techniques such as fishes, xy-wings, xyz-wings, y-wings, turbot fish etc. But I don't expect this puzzle can be solved that way:
Code: Select all
Original puzzle:
..5..3.64
.........
1..8.2..9
.1.....7.
7..6.9..5
......8..
9.4.5...7
......6..
..7.3..42

Stuck state:
+-------------------------+-------------------------+-------------------------+
| 28      2789    5       | 179     179     3       | 127     6       4       |
| 2346    234679  2369    | 14579   4679    1457    | 1237    1238    138     |
| 1       3467    36      | 8       467     2       | 357     35      9       |
+-------------------------+-------------------------+-------------------------+
| 23456   1       23689   | 345     248     458     | 2349    7       36      |
| 7       234     238     | 6       1248    9       | 1234    123     5       |
| 23456   234569  2369    | 13457   1247    1457    | 8       1239    136     |
+-------------------------+-------------------------+-------------------------+
| 9       368     4       | 2       5       68      | 13      138     7       |
| 2358    2358    1       | 479     4789    478     | 6       59      38      |
| 568     568     7       | 19      3       168     | 59      4       2       |
+-------------------------+-------------------------+-------------------------+

So time to flex your "forcing chain" muscle, experts!:)
udosuk
 
Posts: 2698
Joined: 17 July 2005

Postby tarek » Tue Apr 29, 2008 3:49 pm

NOT a fun puzzle...

I couldn't find a nice solution....

My solver also had to go to forcing chains .... This is where it goes to forcing chains after exhausting all possible ALS -xz & -xy

Code: Select all
*--------------------------------------------------------------------------*
| 28      2789    5      | 179     179     3      | 27      6       4      |
| 2346    234679  2369   | 4579    4679    457    | 237     18      18     |
| 1       467     36     | 8       467     2      | 357     35      9      |
|------------------------+------------------------+------------------------|
| 23456   1       2389   | 345     248     458    | 349     7       36     |
| 7       234     238    | 6       1248    9      | 134     23      5      |
| 23456   234569  2369   | 3457    1247    1457   | 8       239     136    |
|------------------------+------------------------+------------------------|
| 9       368     4      | 2       5       68     | 13      18      7      |
| 2358    2358    1      | 479     4789    478    | 6       59      38     |
| 568     568     7      | 19      3       168    | 59      4       2      |
*--------------------------------------------------------------------------*

tarek
User avatar
tarek
 
Posts: 3762
Joined: 05 January 2006

Postby Jean-Christophe » Tue Apr 29, 2008 4:53 pm

I agree with tarek, not really fun.:(

Here is one which does not require forcing chains.

Code: Select all
+-------+-------+-------+
| 5 . 7 | 9 . . | . . . |
| . . . | . . 6 | . . . |
| 1 . . | . . . | . 5 8 |
+-------+-------+-------+
| 9 . . | . 6 2 | . . . |
| . . . | 3 . . | . 4 6 |
| . 3 . | 1 . 8 | . . . |
+-------+-------+-------+
| . . . | . . . | . 6 7 |
| . . 4 | . 7 . | 1 . . |
| . . 8 | . 2 . | 4 . . |
+-------+-------+-------+


JSudoku wrote:Techniques used:
43 Naked Singles
14 Hidden Singles
1 Hidden Pairs
1 Naked Triplets
4 Intersections
1 Finned X-Wing
2 Y-Wings
1 Sue de Coq up to 6 cells
3 ALS-XZ up to 5 cells
2 ALS-XZ


PS: Matt, as you can see, I've added some techniques to JSudoku. A new release will come soon.:)
Jean-Christophe
 
Posts: 149
Joined: 22 January 2006

Postby udosuk » Tue Apr 29, 2008 5:06 pm

Jean-Christophe wrote:PS: Matt, as you can see, I've added some techniques to JSudoku. A new release will come soon.:)

Great!:D So does your new version, armed with more vanilla weapons, solve the puzzle I quoted? After all it's generated by your own current version!:idea:
udosuk
 
Posts: 2698
Joined: 17 July 2005

Re: Diabolical puzzle that has JSudoku stumped

Postby hobiwan » Tue Apr 29, 2008 6:23 pm

udosuk wrote:So time to flex your "forcing chain" muscle, experts!:)

This is my first stab on Forcing chains, so beware, its not pretty!

From your stuck state:
Code: Select all
Almost Locked Set XZ-Rule: A=[r3c8] - {35}, B=[r8c45689] - {345789}, X=5, Z=3 => [r2c9],[r7c8]<>3
XY-Wing: 8/3/1 in [r28c9],[r7c7] => [r12c7]<>1
Locked Candidates, Hidden Pair, Naked Pair
Finned X-Wing: 3 r27 c27 f[r2c1] f[r2c3] => [r3c2]<>3

.------------------------.------------------------.------------------------.
| 28      2789    5      | 179     179     3      | 27      6       4      |
| 2346    234679  2369   | 4579    4679    457    | 237     18      18     |
| 1       467     36     | 8       467     2      | 357     35      9      |
:------------------------+------------------------+------------------------:
| 23456   1       23689  | 345     248     458    | 349     7       36     |
| 7       234     238    | 6       1248    9      | 134     23      5      |
| 23456   234569  2369   | 13457   1247    1457   | 8       239     136    |
:------------------------+------------------------+------------------------:
| 9       368     4      | 2       5       68     | 13      18      7      |
| 2358    2358    1      | 479     4789    478    | 6       59      38     |
| 568     568     7      | 19      3       168    | 59      4       2      |
'------------------------'------------------------'------------------------'
Forcing Chain Verity => [r5c3]=8
  [r1c5]=9=>[r1c4]=1=>[r9c4]=9=>[r4c7]=9=>[r5c7]=4=>[r5c5]=1=>[r5c3]=8
  [r2c5]=9=>[r3c5]=6=>[r3c3]=3=>[r2c7]=3=>[r7c7]=1=>[r5c5]=1=>[r5c3]=8
  [r8c5]=9=>[r6c8]=9=>[r4c3]=9=>[r5c3]=8

Finned X-Wing: 3 r57 c27 f[r5c8] => [r4c7]<>3
Finned Swordfish: 3 r357 c278 f[r3c3] => [r2c2]<>3

.------------------------.------------------------.------------------------.
| 28      2789    5      | 179     179     3      | 27      6       4      |
| 2346    24679   2369   | 4579    4679    457    | 237     18      18     |
| 1       467     36     | 8       467     2      | 357     35      9      |
:------------------------+------------------------+------------------------:
| 23456   1       2369   | 345     248     458    | 49      7       36     |
| 7       234     8      | 6       124     9      | 134     23      5      |
| 23456   234569  2369   | 13457   1247    1457   | 8       239     136    |
:------------------------+------------------------+------------------------:
| 9       368     4      | 2       5       68     | 13      18      7      |
| 2358    2358    1      | 479     4789    478    | 6       59      38     |
| 568     568     7      | 19      3       168    | 59      4       2      |
'------------------------'------------------------'------------------------'
Forcing Chain Verity => [r9c7]=5
  [r6c3]=2=>[r4c5]=2=>[r4c6]=8=>[r7c6]=6=>[r9c6]=1=>[r9c4]=9=>[r9c7]=5
  [r6c3]=3=>[r4c4]=3=>[r8c9]=3=>[r7c7]=1=>[r5c5]=1=>[r1c4]=1=>[r9c4]=9=>[r9c7]=5
  [r6c3]=6=>[r3c3]=3=>[r3c8]=5=>[r9c7]=5
  [r6c3]=9=>[r4c7]=9=>[r9c7]=5


I do have a solution without Forcing Chains (lots of Nice Loops + ALS + Sue de Coq), but it is even longer.

Another possibility:
Code: Select all
Forcing Chain Verity => [r5c3]=8
  [r7c2]=3=>[r8c9]=3=>[r4c9]=6=>[r6c9]=1=>[r5c5]=1=>[r5c3]=8
  [r8c1]=3=>[r8c2]=2=>[r8c8]=5=>[r6c8]=9=>[r4c3]=9=>[r5c3]=8
  [r8c2]=3=>[r8c1]=2=>[r8c8]=5=>[r6c8]=9=>[r4c3]=9=>[r5c3]=8
Finned Swordfish: 3 r357 c278 f[r3c3] => [r2c2]<>3
Almost Locked Set XZ-Rule: A=[r3c8] - {35}, B=[r8c45689] - {345789}, X=5, Z=3 => [r2c9],[r7c8]<>3
Almost Locked Set XZ-Rule: A=[r2c9] - {18}, B=[r7c7],[r8c9] - {138}, X=8, Z=1 => [r12c7]<>1
Locked Candidates, Hidden Pair, Naked Pair
Forcing Chain Verity => [r9c7]=5
  [r6c3]=2=>[r4c5]=2=>[r4c6]=8=>[r7c6]=6=>[r9c6]=1=>[r9c4]=9=>[r9c7]=5
  [r6c3]=3=>[r4c4]=3=>[r8c9]=3=>[r7c7]=1=>[r5c5]=1=>[r1c4]=1=>[r9c4]=9=>[r9c7]=5
  [r6c3]=6=>[r3c3]=3=>[r3c8]=5=>[r9c7]=5
  [r6c3]=9=>[r4c7]=9=>[r9c7]=5
hobiwan
2012 Supporter
 
Posts: 321
Joined: 16 January 2008
Location: Klagenfurt

Postby daj95376 » Tue Apr 29, 2008 7:03 pm

[Withdrawn: chain logic flawed!]
Last edited by daj95376 on Sun May 04, 2008 7:53 am, edited 1 time in total.
daj95376
2014 Supporter
 
Posts: 2624
Joined: 15 May 2006

Postby champagne » Fri May 02, 2008 4:09 pm

Hi udosuk

I did not start exactly form your stuck state.
Here is the proposal of my solver.
First chain clears 1r2c5, what you did, but at that point my solver does not clear 1r4c7, what you did.

Code: Select all
2A8a   278A9Æ   5       |17Í9   179    3      |1o2r7  6      4     
234z6  234679   2s369Ç  |145b79 146k79 145B7  |1237   12T38c 1m38C
1      34d67    3É6é    |8      4D6K7  2      |35e7U  3e5E   9     
------------------------------------------------------------------
2345À6 1        2368F9e |3j45   248    458Å   |234l9E 7      3N6n 
7      234      238f    |6      1p248F 9      |1234L  123    5     
23456  2345á69Ç 2369    |13J457 1247   1457   |8      1239e  1M36N
------------------------------------------------------------------
9      3C6h8    4       |2      5      6H8h   |1g3G   1G38C  7     
2i3x5  2I358    1       |479    478Å9È 478    |6      5e9E   3C8c 
56Ã8A  568      7       |1e9E   3      1E6h8Ä |5E9e   4      2   



Code: Select all
[]1r2c5 - 1r5c5.p = 1r5c78.P - 1r6c9.M = 1r2c9.m - 1r2c5


Code: Select all
[]8r5c5.F - 1r5c5.p = 1r5c78.P - 1r6c9.M = 1r2c9.m - 8r2c9.C = 8r8c9.c - 8r8c56.E = 9r4c3.e - 8r4c3.F


key point is here 8r8c56.E = 9r4c3.e the solver got in ALS/ACs r8456 r7c6r9c46
8r8c56.E is re used below


Code: Select all
[]AC:r2c89(2r2c8.T - 1r2c89) = 1r12c7 - 1r7c7.g = 3r7c7.G - 3r7c2.C = 8r2c8.c - 2r2c8.T
[]3r3c2 - 3r3c8.e = 8r8c56.E - 8r8c9.c = 3r7c2.C - 3r3c2   
[]6r4c3 - 6r4c9.n = 3r4c9.N - 3r8c9.C = 8r8c9.c - 8r8c56.E = 9r4c3.e - 6r4c3
[]1r6c8 - 1r6c9.M = 1r2c9.m - 8r2c9.C = 8r8c9.c - 8r8c56.E = 9r6c8.e - 1r6c8
[]1r6c4 - 1r6c9.M = 1r2c9.m - 8r2c9.C = 8r8c9.c - 8r8c56.E = 1r9c4.e - 1r6c4
[]AC:r27c8(3r27c8 - 1r27c8) = 1r56c8 - 1r6c9.M = 1r2c9.m - 8r2c9.C = 8r8c9.c - 8r8c56.E = 3r3c8.e - 3r27c8
[]AC:r2c89(3r2c89 - 1r2c89) = 1r12c7.€d - 1r7c7.g = 3r7c7.G - 3r7c2.C = 8r8c9.c - 8r8c56.E = 3r3c8.e - 3r2c89
[]1r2c4 - 1r1c45.O = 1r1c7.o - 1r7c7.g = 3r7c7.G - 3r7c2.C = 8r8c9.c - 8r8c56.E = 1r9c4.e - 1r2c4



3 r5c3=8 B
-
>LS2 cells 89 digits 18 row 2
->LS2 cells 27 digits 18 column H
->LS2 cells 56 digits 18 box 3

next step restarts at that point


Code: Select all
2B8b    2Æ78B9à 5      |1a7Ì9 1A79   3      |2l7L   6      4     
234v6   234679   2p369Ä |45d79 46k79  45D7   |2L3q7  1c8C   1C8c   
1       4e67     3q6Q   |8     4E6K7  2      |3Ç5A7q 3A5a   9     
------------------------------------------------------------------
2345x6f 1        239A   |3j45  2o48g  458G   |34m9a  7      3f6F   
7       23r4Ê    8      |6     1c2È4  9      |1C3É4M 2n3N   5     
23456   2345Y69Ä 236z9  |3J457 1247   1A457  |8      2N3Í9A 1c3Î6f
------------------------------------------------------------------
9       3c6h8Ë   4      |2     5      6H8h   |1c3C   1C8c   7     
2i3t5   2I358    1      |479   478G9Å 478    |6      5A9a   3c8C   
56Á8B   568      7      |1A9a  3      1a6h8Â |5a9A   4      2   
Last edited by champagne on Sun May 04, 2008 5:31 pm, edited 2 times in total.
champagne
2017 Supporter
 
Posts: 7466
Joined: 02 August 2007
Location: France Brittany

Postby udosuk » Sun May 04, 2008 11:32 am

A big thank you for all the moves, experts!:D Sorry for not replying sooner. Like JC & tarek mentioned this one is probably not fun to solve manually. Hope the ones who enjoy solving extra-tough puzzles by chains enjoy it!:)
udosuk
 
Posts: 2698
Joined: 17 July 2005

Postby champagne » Sun May 04, 2008 3:35 pm

udosuk wrote

Like JC & tarek mentioned this one is probably not fun to solve manually. Hope the ones who enjoy solving extra-tough puzzles by chains enjoy it!


I would not qualify that puzzle as "extra tough".
the ALS/AC I used at that point is very easy to find without a computer
It is often the pass to crack middle class puzzles;

This is the box 8
Code: Select all
2      5      6H8h       
479    4789   478     
1e9E   3      1E6h8   


ALS/ACs are patterns being at the same time ALS and AHS/AC. They have 2 unknown digits.

The simplest one can be seen here r79c6 6H8h 1E6h8.
. 6 is compulsory
. are remaining 1r9c6.E 8r79c6 This is a strong link and 8r79c6 must be tagged "e"
. this is enough to have 8r8c56 tagged "E" what we are looking for.


Adding r9c6 gives a new ALS/AC r7c6r9c46
.6 and 1 compulsory
. are remaining 9r9c6.E and again 8r79c6


Complementary sets r8c456r9c4 or r8c456 are ALS/AC as well, but not so easy to detect because compulsory digits are all in groups ('4' '7' '9').

It is slightly easier to detect these key ALS/AC on a tagged map of candidates, but you can do it as well without tagging.



Out of the chains produced in my post, 4 are not using more that this strong link and basic bi values (including groups). I did not check whether you could go to the end without crossing other ACs
Last edited by champagne on Sun May 04, 2008 5:17 pm, edited 1 time in total.
champagne
2017 Supporter
 
Posts: 7466
Joined: 02 August 2007
Location: France Brittany

Postby ronk » Sun May 04, 2008 7:32 pm

champagne wrote:
Code: Select all
[]8r5c5.F - 1r5c5.p = 1r5c78.P - 1r6c9.M = 1r2c9.m - 8r2c9.C = 8r8c9.c - 8r8c56.E = 9r4c3.e - 8r4c3.F

key point is here 8r8c56.E = 9r4c3.e the solver got in ALS/ACs r84546 r7c6r9c79

But 8r8c56 is not tagged 'E' ... and r9c9 doesn't even have a candidate. Is this what you mean?

r5c5 =1= r5c78 -1- r5c9 =1= r2c9 =8= r8c9 -8- ALS:r8c4568 -5- r9c7 -9- r4c7 =9= r4c3 =8= r5c3 -8- r5c5
==> r5c5<>8
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby udosuk » Sun May 04, 2008 9:13 pm

champagne wrote:udosuk wrote

Like JC & tarek mentioned this one is probably not fun to solve manually. Hope the ones who enjoy solving extra-tough puzzles by chains enjoy it!


I would not qualify that puzzle as "extra tough".
the ALS/AC I used at that point is very easy to find without a computer
It is often the pass to crack middle class puzzles;

Oops, so I see it's not in the same class as the "Easter Monster" or "Golden Nugget" etc. It should be expected as it was just a random puzzle generated by JSudoku. What surprised me was that JSudoku (version 1.2b1) itself couldn't solve it logically (I think the latest version 1.3b1 probably can). Still thanks for your feedback and hope it gave you some joy solving it. Sadly I don't understand your notation much and don't have time & energy to study it vigorously. Hope others understand it better!
udosuk
 
Posts: 2698
Joined: 17 July 2005

Postby champagne » Sun May 04, 2008 9:31 pm

champagne wrote:

[]8r5c5.F - 1r5c5.p = 1r5c78.P - 1r6c9.M = 1r2c9.m - 8r2c9.C = 8r8c9.c - 8r8c56.E = 9r4c3.e - 8r4c3.F

key point is here 8r8c56.E = 9r4c3.e the solver got in ALS/ACs r84546 r7c6r9c79



ronk wrote

But 8r8c56 is not tagged 'E' ... and r9c9 doesn't even have a candidate. Is this what you mean?


1) thank you ronk for pointing errors. I change r8c4546 in r8c456 and r9c79 in r9c46 as it should has been in the two posts.

2) 8r8c56 is tagged 'E'. This is not visible on the map, (tags for groups are not shown) but the solver has identified that strong link.

ronk wrote

r5c5 =1= r5c78 -1- r5c9 =1= r2c9 =8= r8c9 -8- ALS:r8c4568 -5- r9c7 -9- r4c7 =9= r4c3 =8= r5c3 -8- r5c5
==> r5c5<>8


As usual, you have several ways to reach the same conclusion. The solver gives priority to the shortest clearing AICs.
champagne
2017 Supporter
 
Posts: 7466
Joined: 02 August 2007
Location: France Brittany

Postby champagne » Sun May 04, 2008 9:57 pm

udosuk wrote
Oops, so I see it's not in the same class as the "Easter Monster" or "Golden Nugget" etc. It should be expected as it was just a random puzzle generated by JSudoku


There is many intermediate levels between that puzzle and the "hardest" family

That one does not request for example nets of AICs.

Random generation gives about 1% of such puzzles. At least this is what I got on a sample file of 10000 minimum puzzles. About 1/1000 are requesting use of nets of AICs or equivalent methods.
champagne
2017 Supporter
 
Posts: 7466
Joined: 02 August 2007
Location: France Brittany

Postby ronk » Sun May 04, 2008 11:41 pm

champagne wrote:As usual, you have several ways to reach the same conclusion. The solver gives priority to the shortest clearing AICs.

I'm not trying to find a shorter way, a longer way, or even another way. I'm trying to figure out the way your solver used.

The typos didn't help. The fact that you abbreviate a portion of the chain with rMcN.E = rScT.e doesn't help. The fact that the right end of your chain doesn't loop back to r5c5 doesn't help.

A solver finding a solution path to a difficult puzzle is great, but note that this site is called the Players' Forum. If the presentation for a solver step doesn't quickly communicate the inference stream to a player, well ... there won't be many players looking more than once.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby champagne » Mon May 05, 2008 6:15 am

champagne wrote:
As usual, you have several ways to reach the same conclusion.
The solver gives priority to the shortest clearing AICs.
Ronk wrote
Code: Select all
I'm not trying to find a shorter way, a longer way, or even another way. I'm trying to figure out the way your solver used.

The typos didn't help. The fact that you abbreviate a portion of the chain with rMcN.E = rScT.e doesn't help.
The fact that the right end of your chain doesn't loop back to r5c5 doesn't help.

A solver finding a solution path to a difficult puzzle is great, but note that this site is called the Players' Forum.
If the presentation for a solver step doesn't quickly communicate the inference stream to a player,


Ok Ronk, you are surely right. I am doing my best to clarify my posts, but there is some work.
I have nevertheles a limit. If somebody has not enough motivation to read the full tagging principles, there will be some opacity in my posts.

I try here after to comment a little more that AIC

First of all, my AICs are following the general rule agreed here for AICs (thanks to Mike Barker who helped me).

The main specificity of AICs in full tagging is that your never find several strong links attached. You jump from one point to another one.
This comes normally on layers shown on the map. In any case, adding the tag to the candidate or the group of candidates gives an easy way to rebuild the jump.

This happens also at the ends. []8r5c5.F - .. - 8r4c3.F means clearly that tag 'F' is not valid. 8r5c5 and 8r4c3 will be cleared.
For user more familair with full tagging, I would have written :
Code: Select all
[] Fp PM mC cE eF  'F' is dead. (which is exactly the same).


Here is the map revised to keep only used layers.

Code: Select all
28     2789     5       |179    179    3      |12r7   6      4     
2346   234679   2369    |14579  14679  145B7  |1237   1238c  1m38C
1      3467     36      |8      467    2      |35e7   3e5E   9     
------------------------------------------------------------------
23456  1        2368F9e |345    248    458    |2349E  7      36 
7      234      238f    |6      1p248F 9      |1234   123    5     
23456  234569   2369    |13457  1247   1457   |8      1239e  1M36
------------------------------------------------------------------
9      3C68     4       |2      5      6H8    |13     138C   7     
235    2358     1       |479    4789   478    |6      5e9E   3C8c 
568    568      7       |1e9E   3      1E6h8  |5E9e   4      2   


The AIC was

Code: Select all
[]8r5c5.F - 1r5c5.p = 1r5c78.P - 1r6c9.M = 1r2c9.m - 8r2c9.C = 8r8c9.c - 8r8c56.E = 9r4c3.e - 8r4c3.F

If I clean the tag where there is no jump and nothing special, I can write it

Code: Select all
[]8r5c5.F - 1r5c5 = 1r5c78 - 1r6c9 = 1r2c9 - 8r2c9 = 8r8c9 - 8r8c56.E = 9r4c3.e - 8r4c3.F


I gave a specific comment to justify the strong link 8r8c56.E = 9r4c3.e.
Another way would have been, I agree, to replace the comment by 8r8c9 - AC:r8c456r9c4(8r8c56 = 9r4c3) - 8r4c3
And I could have written two AICs including the 'F' layer

Code: Select all
[]8r5c5 - 1r5c5 = 1r5c78 - 1r6c9 = 1r2c9 - 8r2c9 = 8r8c9 - AC:r8c456r9c4(8r8c56 = 9r4c3) - 8r4c3 = 8r4c5 - 8r5c5
[]8r4c3 - 8r4c5 = 8r5c5 - 1r5c5 = 1r5c78 - 1r6c9 = 1r2c9 - 8r2c9 = 8r8c9 - AC:r8c456r9c4(8r8c56 = 9r4c3) - 8r4c3 


your comment will surely help to improve the communication.

Unfortunately, for toughest puzzles, other difficulties appear, but I am prepared to work with you on improvment of the form.
champagne
2017 Supporter
 
Posts: 7466
Joined: 02 August 2007
Location: France Brittany

Next

Return to Help with puzzles and solving techniques