The New Sudoku Players' Forum

[jco]

Hello,

The following puzzle (Nightmare #5 from App Sudoku4ever) is on my list of unsolved ones for a while now.
After basics, I had the hope of finding "small moves" to advance it little by little but it has been a futile effort.
(Hodoku solver can't solve it without brute force, SE shows lots of dynamic forcing chains)
I am writing to ask for help to bring this puzzle (SE 9.5) down to a manageable
(for me as a manual solver) configuration (SE around 7.5 would be very nice).
An explanation on the reasoning made to arrive at the moves is very much
appreciated (valuable learning experience to hopefully use next time).

Code: Select all

,-----------------------------,
| .  .  1 | .  .  2 | .  .  . |
| .  2  . | .  3  . | .  .  . |
| 4  .  . | 5  .  . | 6  .  . |
|---------+---------+---------|
| .  .  6 | .  .  . | .  .  7 |
| .  1  . | .  .  . | .  8  . |
| 9  .  . | .  .  . | 5  .  . |
|---------+---------+---------|
| .  .  7 | .  .  8 | .  .  3 |
| .  3  . | .  9  . | .  1  . |
| 5  .  . | 7  .  . | 4  .  . |
'-----------------------------'
..1..2....2..3....4..5..6....6.....7.1.....8.9.....5....7..8..3.3..9..1.5..7..4..


PM

Code: Select all

.-------------------.------------------------.--------------------.
| 3678  56789  1    | 4689    4678    2      | 3789  34579  4589  |
| 678   2      589  | 14689   3       14679  | 1789  4579   14589 |
| 4     789    389  | 5       178     179    | 6     2379   1289  |
:-------------------+------------------------+--------------------:
| 238   458    6    | 123489  12458   13459  | 1239  2349   7     |
| 237   1      2345 | 23469   24567   345679 | 239   8      2469  |
| 9     478    2348 | 123468  124678  13467  | 5     2346   1246  |
:-------------------+------------------------+--------------------:
| 126   469    7    | 1246    12456   8      | 29    2569   3     |
| 268   3      248  | 246     9       456    | 278   1      2568  |
| 5     689    289  | 7       126     136    | 4     269    2689  |
'-------------------'------------------------'--------------------'

Thank you in advance!
jco
[Edit 1: added source of the puzzle; EDIT 2: Corrected S.E.R. of the puzzle (thanks to remark by coloin) ]

[Hajime]

Add "8" in r1c1 and r9c9.
Than you will have a puzzle that can be solved with only these methods:

Pointing, Claiming | (9)r7b9 => (-9)r9c8
2-string Kite (2) r5c7=r7c7-r9c8=r9c3 => (-2)r5c3
XY_Chain | (2=4)r6c3 (4=5)r5c3 (5=9)r2c3 (9=7)r3c2 (7=6)r2c1 (6=2)r8c1 (2=9)r9c3 (9=6)r9c2 (6=2)r9c8 [9] => (-2)r6c8 (-2)r9c3

That reduces the rating considerable.

[jco]

Hello,

Add "8" in r1c1 and r9c9.
Than you will have a puzzle that can be solved with only these methods:

Pointing, Claiming | (9)r7b9 => (-9)r9c8
2-string Kite (2) r5c7=r7c7-r9c8=r9c3 => (-2)r5c3
XY_Chain | (2=4)r6c3 (4=5)r5c3 (5=9)r2c3 (9=7)r3c2 (7=6)r2c1 (6=2)r8c1 (2=9)r9c3 (9=6)r9c2 (6=2)r9c8 [9] => (-2)r6c8 (-2)r9c3

That reduces the rating considerable.

Thanks, but this not what I had in mind.
I really want to solve the puzzle in its original configuration,
using logical sound Sudoku moves (no trial and error, no adding digits from nowhere).

Regards,
jco

[Hajime]

I see what you need: the silver bullet that Hodoku and SE does not have....

[RSW]

Starting with your initial puzzle:
Singles: 1r7c1 -1r7c45 3r9c6 -3r456c6 7r8c7 -7r12c7 1r9c5 -1r346c5
Box/Line: Column 7/Box 3, (8)r1c7 r2c7 => -8r123c9

Code: Select all

 +-----------------+--------------------+-----------------+
 | 3678 56789 1    | 4689   4678  2     | 389  34579 459  |
 | 678  2     589  | 14689  3     14679 | 189  4579  1459 |
 | 4    789   389  | 5      78    179   | 6    2379  129  |
 +-----------------+--------------------+-----------------+
 | 238  458   6    | 123489 2458  1459  | 1239 2349  7    |
 | 237  1     2345 | 23469  24567 45679 | 239  8     2469 |
 | 9    478   2348 | 123468 24678 1467  | 5    2346  1246 |
 +-----------------+--------------------+-----------------+
 | 1    469   7    | 246    2456  8     | 29   2569  3    |
 | 268  3     248  | 246    9     456   | 7    1     2568 |
 | 5    689   289  | 7      1     3     | 4    269   2689 |
 +-----------------+--------------------+-----------------+

Finned-X-Wing: Digit 1 in rows 3 6 columns (4) 6 9, Fin: r6c4  => -1r4c6


That's as far as my solver gets, before having to resort to T&E methods.

Edit:
I included the initial eliminations after I noticed that my PM grid, after basics, was different than the OP's PM grid.

[yzfwsf]

This puzzle have no single cell backdoor.

[denis_berthier]

The following puzzle (Nightmare #5 from App Sudoku4ever) is on my list of unsolved ones for a while now.
After basics, I had the hope of finding "small moves" to advance it little by little but it has been a futile effort.

Code: Select all

.---------.---------.---------.
| .  .  1 | .  .  2 | .  .  . |
| .  2  . | .  3  . | .  .  . |
| 4  .  . | 5  .  . | 6  .  . |
:---------+---------+---------:
| .  .  6 | .  .  . | .  .  7 |
| .  1  . | .  .  . | .  8  . |
| 9  .  . | .  .  . | 5  .  . |
:---------+---------+---------:
| .  .  7 | .  .  8 | .  .  3 |
| .  3  . | .  9  . | .  1  . |
| 5  .  . | 7  .  . | 4  .  . |
'---------'---------'---------'


Just noticing this puzzle.
SER 9.3 makes it a very hard one, unlikely to be human solvable. It belongs to what I called the grey zone, long ago. It is a priori uncertain whether it can be solved by whips/braids/g-whips/g-braids.

First thing I tried is T&E. This puzzle does belong to T&E(1). From my T&E vs braids theorem, it follows that it can be solved by braids (of unspecified maximum length).

When a puzzle can be solved by braids, it can generally be solved by (much simpler) whips. BUT this one doesn't. SudoRules finds several (long) whips, the last one of length 24, and it stops. The first non trivial whip has length 11:
whip[11]: c5n2{r6 r7} - r7c7{n2 n9} - r5c7{n9 n3} - r1c7{n3 n8} - r2c7{n8 n1} - r4n1{c7 c4} - r4n3{c4 c1} - r6n3{c3 c4} - c4n8{r6 r2} - c1n8{r2 r8} - c1n2{r8 .} ==> r5c4 ≠ 2

At this point, we can already say that this puzzle will be a hard fight. jco, no wonder your efforts were futile.

In this situation, rather than using braids, I generally try a solution with g-whips (computationally better than braids). It is not guaranteed that a solution will be obtained, because B is not included in gW (neither does the reverse). I just launched it on a very old Mac (I need my working one for different purposes). I'll complete this post in due time.

I'm very surprised that no solution from Robert, yzf..., or using set covers was proposed.

[Mauriès Robert]

I'm very surprised that no solution from Robert, yzf..., or using set covers was proposed.

Busy with other topics at the moment. But I'll try later!
Robert

[Mauriès Robert]

Hi Denis,
There is a resolution with a resolution tree (DFS). Here is the one proposed by my friend François C with whom I exchange a lot on TDP.
I only give here the structure of the resolution tree, because the sequences (branches) are long to write.
Of course, I use the TDP notation, i.e. the concatenation P(A).P(B) whose candidates are those of the two tracks P(A) and P(B).

Code: Select all

                           ->P(2r5c7)->Contradiction
                         /
             -> P(9r3c3).
           /             \
          /                ->P(9r5c7)->contradiction
         /
P(8r3c5). ->P(9r2c3)-> contradiction
         \         
          \                ->P(1r3c9)->contradiction
           \             /
             -> P(9r9c3). 
                         \       
                           ->P(1r3c6)->solution


                           ->P(1r3c6)->Contradiction
                         /
             -> P(5r1c2).
           /             \
          /                ->P(9r3c6)->contradiction
         /
         |  ->P(6r1c2)-> contradiction
         |/
P(7r3c5). 
         |\
         |  ->P(9r1c2)-> contradiction
         \         
          \                ->P(1r2c9)->contradiction
           \             /
             -> P(7r1c2).->P(4r2c9)->contradiction 
                         \       
                           ->P(9r2c9)->contradiction


The resolution depth of this tree is 3.
It seems that it is not possible to find a resolution tree of depth 2.
We classify the grids by TDP level by counting the number of invalid branches of the "optimal" resolution tree. This grid is therefore at maximum TDP level 11.
Cordialy
Robert

[coloin]

So .... judging by the comments from everybody this puzzle [ i got it as SE 9.5] could be described as a little bit harder than other SE 9.5s

[denis_berthier]

So .... judging by the comments from everybody this puzzle [ i got it as SE 9.5] could be described as a little bit harder than other SE 9.5s

You're right, the SER is 9.5 and not 9.3 as stated in the title.
It's a very special case, as it is in T&E(1) and therefore solvable by braids, quite rare for SE 9.5. But it is not solvable by whips.
I'm not sure it's harder than other 9.5s.

[jco]

Hello,
Thank you all for all this information. I corrected the title but forgot that it does not change the title in the replies, so I changed back to 9.3.
I played around using Phil's Sudoku Solver (output hidden). Perhaps someone more experienced with it would get a better version.

Hidden Text: Show

[1] 8s at r12c7 only ones in row/column => -8 r123c9.

[2] Finned X-wing of 1s (r36\c69), fin at r6c4, eliminating 1 from r4c6

[3] If 2 is true in r4c7 then the 6 at r7c2 is both true and false, hence 2 is false and can be eliminated

[4] Since the 2 at r5c7 must be either true or false, chains beginning in each case show 2 to be false at r5c3
chain1: (2)r5c7 - r5c3
chain2: (2)r5c7 = r7c7 - r7c5 = r8c4 - r8c1 = r9c3 - r5c3

[5] Since the 2 at r5c7 must be either true or false, chains beginning in each case show 2 to be false at r5c4
chain1: (2)r5c7 - r5c4
chain2: (2)r5c7 = r7c7 - r7c5 = r8c4 - r5c4

[6] If 2 is true in r5c9 then the 8 at r9c9 is both true and false, hence 2 is false and can be eliminated

[7] If 2 is true in r8c9 then the 2 at r3c8 is both true and false, hence 2 is false and can be eliminated

[8] If 7 is true in r3c6 then the 5 at r5c5 is both true and false, hence 7 is false and can be eliminated

[9] If 9 is true in r2c7 then the 3 at r4c4 is both true and false, hence 9 is false and can be eliminated

[10] Whether 1 at r4c4 or r4c7 is true, the cells at r7c45, r8c46 are reduced to 246, 2456, 246 and 56

[11] If 2 is true in r4c8 then the 2 at r7c7 is both true and false, hence 2 is false and can be eliminated

[12] If 2 is true in r5c1 then the 2 at r7c7 is both true and false, hence 2 is false and can be eliminated

[13] If 2 is true in r6c9 then the 3 at r6c4 is both true and false, hence 2 is false and can be eliminated

[14] If 1 is true in r2c6 then the 4 at r7c2 is both true and false, hence 1 is false and can be eliminated

[15] If 3 is true in r4c8 then the 6 at r2c6 is both true and false, hence 3 is false and can be eliminated

[16] If 1 is false in r3c6 then the 5 at r4c2 is both true and false, hence 1 must be true in r3c6

[17] Since the 4 must be true in either r4c2, r6c2 or r7c2, chains beginning with each all show 4 to be false at r6c4
chain1: (4)r4c2 - (4=9)r4c8 - (49=5)r4c6 - r4c5 = (5-4)r7c5 = r7c4 - r6c4
chain2: (4)r6c2 - r6c4
chain3: (4)r7c2 - r7c5 = r8c4 - r6c4

[18] If 2 is true in r4c4 then the 2 at r8c1 is both true and false, hence 2 is false and can be eliminated

[19] If 2 is true in r6c4 then the 9 at r2c8 is both true and false, hence 2 is false and can be eliminated
2s at r78c4 only ones in row/column => -2 r7c5.

[20] If 3 is true in r1c8 then the 4 at r7c2 is both true and false, hence 3 is false and can be eliminated

[21] If 2 is false in r3c9 then the 6 at r8c1 is both true and false, hence 2 must be true in r3c9

[22] Since either 2, 3 or 9 must be true at r5c7, chains beginning with each all show 9 to be false at r4c7
chain1: (2)r5c7 - (2=9)r7c7 - r4c7
chain2: (3)r5c7 - r1c7 = r1c1 - r3c3 = r6c3 - r4c1 = (3-1)r4c4 = (1-9)r4c7
chain3: (9)r5c7 - r4c7

[23] If 7 is false in r5c1 then the 4 at r1c9 is both true and false, hence 7 must be true in r5c1

[24] If 6 is false in r2c1 then the 1 at r4c4 is both true and false, hence 6 must be true in r2c1

[25] If 2 is true in r7c8 then the 4 at r4c2 is both true and false, hence 2 is false and can be eliminated

[26] If 3 is true in r4c4 then the 3 at r6c3 is both true and false, hence 3 is false and can be eliminated

[27] If 2 is false in r5c7 then the 5 at r5c3 is both true and false, hence 2 must be true in r5c7

[28] Naked pairs of 38 at r1c17 => -8 r1c245

[29] Complex chain: (5)r8c6 = (5-4)r7c5^2 = (4*)r7c2 - (4=8)r6c2 - (8|4*=5)r4c2 => -5 r4c6

[30] Naked pairs of 49 at r4c68 => -4 r4c245, -9 r4c4

[31] Complex chain: (6)r6c8 = (6*)r7c8 - (6=4)r7c2 - (4|6*=5)r7c5 - (5=6)r8c6 => -6 r6c6

[32] Naked triplets of 479 at r246c6 => -4 r5c6, -9 r5c6

[33] Simple chain: (9)r2c6 = (9)r4c6 - (9)r4c8 = (9)r5c9 => -9 r2c9

[34] Finned swordfish of 5s (r147\c258), fin at r1c9, eliminating 5 from r2c8

[35] Since the 1 at r6c4 must be either true or false, chains beginning in each case show 4 to be false at r6c9
chain1: (3)r6c4 = (3-9)r5c4 = r4c6 - (9=4)r4c8 - r6c9
chain2: (1)r6c4 = r4c4 - (1=3)r4c7 - (3=8)r1c7 - (8=1)r2c7 - r2c9 = (1-4)r6c9

[36] Since the 2 at r4c1 must be either true or false, chains beginning in each case show 9 to be false at r2c3
chain1: (2)r4c1 - r4c5 = r6c5 - r6c3 = r8c3 - (2=8)r8c1 - (8=9)r9c3 - r2c3
chain2: (2)r4c1 = (2-5)r4c5 = r4c2 - r1c2 = (5-9)r2c3

[37] Since the 2 at r4c1 must be either true or false, chains beginning in each case show 8 to be false at r4c2
chain1: (2)r4c1 - r4c5 = r6c5 - r6c3 = (2-4)r8c3 = r7c2 - (4=8)r6c2 - r4c2
chain2: (2)r4c1 = (2-5)r4c5 = (5-8)r4c2

[38] Since the 1 at r6c4 must be either true or false, chains beginning in each case show 4 to be false at r5c9
chain1: (1)r6c4 - (1=8)r4c4 - r2c4 = (8-1)r2c7 = (1-3)r4c7 = r4c1 - (3=4)r5c3 - r5c9
chain2: (1)r6c4 = r4c4 - (1=3)r4c7 - (3=8)r1c7 - (8=1)r2c7 - (1=4)r2c9 - r5c9
4s at r12c9 only ones in row/column => -4 r12c8.

[39] Since the 1 at r6c4 must be either true or false, chains beginning in each case show 4 to be false at r2c4
chain1: (1)r6c4 - (1=6)r6c9 - r6c8 = r7c8 - (6=4)r7c2 - r8c3 = r8c4 - r2c4
chain2: (1)r6c4 = r4c4 - (1=3)r4c7 - (3=8)r1c7 - (8=1)r2c7 - (1=4)r2c9 - r2c4

[40] Since the 1 at r6c4 must be either true or false, chains beginning in each case show 7 to be false at r3c8
chain1: (1)r6c4 - (1=8)r4c4 - (8=9)r2c4 - (9=7)r2c8 - r3c8
chain2: (1)r6c4 = r4c4 - (1=3)r4c7 - (3=8)r1c7 - (8=3)r1c1 - r3c3 = (3-7)r3c8
Complex chain: (4=9)r4c8 - (9)r4c6 = (9-3)r5c4 = (3-4)r5c3*4 = (4)r5c5 => -4 r4c6

[41] 6s at r5c456 only ones in row/column => -6 r6c45.
Simple chain: (7=9)r1c2 - (9)r1c4 = (9)r2c4 - (9=7)r2c8 => -7 r1c8

Solved!

When I wrote on this topic, I had some hope that some technique unavailable in Hodoku and SE (developed later) could help (learned SL-loops recently for this reason). Also recently managed to install YZF_Sudoku, but it also gives lots of dynamic contradiction chains and as in the above solver, it has SK-loops, but there are none in this puzzle. At least, learned a technique I did not know. : )

Regards,
jco
[Edit: small changes to improve clarity]

[DEFISE]

First thing I tried is T&E. This puzzle does belong to T&E(1). From my T&E vs braids theorem, it follows that it can be solved by braids (of unspecified maximum length).
...

Hi Denis,
Do you remember me ? In May I had done a resolution program using whips or braids, which was working fine since I had checked several whips and braids from your book. But for this puzzle my program is also powerless.
My question is the following: do you consider that a resolution in depth 2 is irrelevant, knowing that this puzzle belongs to T&E (1) ?

François C.

[denis_berthier]

First thing I tried is T&E. This puzzle does belong to T&E(1). From my T&E vs braids theorem, it follows that it can be solved by braids (of unspecified maximum length)....

Hi Denis,
Do you remember me ? In May I had done a resolution program using whips or braids, which was working fine since I had checked several whips and braids from your book. But for this puzzle my program is also powerless.
My question is the following: do you consider that a resolution in depth 2 is irrelevant, knowing that this puzzle belongs to T&E (1) ?
François C.

Hi DEFISE,
yes, I do remember you.
I think your program faces the same problem as mine, i.e. combinatorial explosion: the number of partial-braids increases very fast but only very few of them give an elimination. This is intrinsic to the puzzle and no program can avoid it. And, from the computations I ran with g-whips, it seems they allow to go farther than braids, but I'm still waiting for the program to complete.
What maximal length of braids do you get on this puzzle before your program fails (or you're tired of waiting)?
I also remember your program could find the B rating faster. Does it find anything for this puzzle?

As for your question, I can't give a single answer. Irrelevant for what?
- If the only goal is to get the fastest possible solution, DFS is the best choice, so a solution of a priori unrestricted depth is the best. Robert gave some hint of a solution at depth 3; I'm not a great fan of it.
- If the goal is to get a solution readable by a normal player, the best approach is to forget this puzzle.
- If the goal is to get a solution using some precisely defined but unreadable patterns, such as w-whips, w*-whips..., that can deal with depth 2 puzzles but can also be used for depth 1, why not; but, again, who will want read it?

I'm not sure what you meant exactly. If you have some solution at depth 2, you should post it.

[DEFISE]

I think your program faces the same problem as mine, i.e. combinatorial explosion...

Exact !

... I ran with g-whips, it seems they allow to go farther than braids, but I'm still waiting for the program to complete.

I have not programmed these patterns.

What maximal length of braids do you get on this puzzle before your program fails (or you're tired of waiting)?

With maximal length paramater = 17 my program fails quickly. I conclude that we need braids[n], n> = 18.
With maximal length paramater = 18 my program finds more braids, including one [18] but does not manage to finish after 15 minutes, so I dropped.
With whips I found it like you (roughly, because I don't eliminate loops).

As for your question, I can't give a single answer. Irrelevant for what?

I think you answered my question further.

If the only goal is to get the fastest possible solution, DFS is the best choice, so a solution of a priori unrestricted depth is the best. Robert gave some hint of a solution at depth 3; I'm not a great fan of it.

I know that.

If the goal is to get a solution using some precisely defined but unreadable patterns, such as w-whips, w*-whips..., that can deal with depth 2 puzzles but can also be used for depth 1, why not; but, again, who will want read it?

There you answered my question.

If you have some solution at depth 2, you should post it.

Yes, here is only a summary of my resolution at depth 2, because my program does not output the exact syntax of whips (only right links):
1) I prove that (puzzle + hint 7L3C5) has no solution, using several whips[n], n <= 10.
2) I delete the candidate 7L3C5
3) I solve the puzzle using several whips[n], n <= 10.