Easter Monster defeated by logic and Christmas presents !

Advanced methods and approaches for solving Sudoku puzzles

Easter Monster defeated by logic and Christmas presents !

Postby aran » Tue Dec 18, 2007 9:44 pm

100000002 090400050 006000700 050903000 000070000 000850040 700000600 030009080 002000001
1st observation
1. Box 1 :
- note that if A2+C2 = 2+7 : then contradiction (=> B5=2, and H5=2)
- note that if A2+C2 = neither 2 nor 7 : then contradiction (=> E2=2, and E8=2).
Hence 2 and 7 are conjugates in A2 and C2.
Similar logic for B1+B3 results in : 2 and 7 are conjugates in B1+B3.
Hence in box 1 : 2 and 7 are limited to A2+B3+C2+B1, and are row-wise and column-wise conjugates
2. Box 7 :
- note that if G2+J2 = 1+6 : then contradiction (=> B1+B3=2+7, just shown impossible in 1 above)
- note that if G2+J2 = neither 1 nor 6 : then contradiction (=> A2+C2=2+7, just shown impossible in 1 above)
Hence 1 and 6 are conjugates in G2+J2.
Similar logic for H1+H3 : hence 1 and 6 are conjugates in H1+H3.
Hence in box 7 : 1 and 6 are limited to G2+H3+J2+H1 and are row-wise and column-wise conjugates.
3. Equivalent conclusions in boxes 3 and 9.
4. All of this forces candidates 1,6,2,7 :
- to occupy alone the central cells of boxes 2,4,6 and 8
- and on a conjugate basis in this sense : 1 member from each of the pairings 16 and 27.
Conclusions :
- eliminations : <2> C1; <7> A3; <3>+<8> B5; <8> B6; <4>+<8> E2; <3>+<9> E8; <1> G3; <6> J1; <5> H4; <4> H5.
- conjugacy as described above : providing a path round the puzzle.


Note : it is pointed out by the second poster that identical conclusions have already and earlier been made by S Kurzhals. I was aware that he had found the eliminations but not the conjugacy, which is the crucial element. Apologies to S Kurzhals. No disgrace in being second to a man of your calibre !

5. The triples 126 now revealed in E2 E4 E8, and B5 D5 H5 generate :
- placement : 4 in E6
- eliminations : <2>+<4>+<6> E1 <4> E3 <1>+<2> E7 <6> E9 <6> A5 <1>+<2> C5 <1>+<2> G5 <6> J5.


2nd observation
6. Consider the four cells : E2 H5 E8 B5 (all limited to candidates : 126)
- observe that no candidate can be absent from all four cells (otherwise => contradiction in box 5)
- hence one candidate must appear twice. Call this the "dual" candidate
- observe that the dual candidate forces a placement of that same candidate at F6.
- observe that the placements of the dual candidate are restricted : eg if 2 is dual, then either B5+E8=2 or E2+H5=2 but not for example B5+E2 : proof : using the conjugacy established above we would have B5 and H5=2. Contradiction.
Can we determine which candidate does not appear twice then eliminate it from F6 and so obtain a bivalue and a pathway through box 5 ?

Two observations :
- given the close pairing "16" and "27" on the grid, the absence of 7 from the four cells under discussion is an intuitive pointer to "2" as being the odd man out
- we will be able to examine the dual 2 position in detail : for combined with conjugacy, this will allow placement of all 2s and 7s on the grid, as will the positions of 1 and 6 enable placement of all 1s and 6s on the grid.

This may throw up anomalies or squeeze available space for other candidates.

On the other hand, dual "1"s or dual "6"s and a single 2 permit placement of all 1s and 6s but not of all 2s and 7s. So little or no chance of anomalies or of squeezing.

So, since dual "2"s at least give us something which can usefully be examined, that's do exactly that :

Considering the 4 possible positions :
case 1 : B5+E8=2 with E2=1+H5=6
case 2 : B5+E8=2 with E2=6+H5=1.
case 3 : E2+H5=2 with B5=1+E8=6
case 4 : E2+H5=2 with B5=6+E8=1.

Case 1 : place 2s and 7s then 1s and 6s : => B6=1 and G6=1 : mpossible

Case 3 : place 2s and 7s then 1s and 6s : => E4=1 and H4=1 : impossible

Case 4 : place 2s and 7s then 1s and 6s : => E4=6 and H4=6 : impossible

Case 2 ; place 2s and 7s then 1s and 6s : => placement 4D3. Then 4D3+1E3=>5H3. 5H3+7H4=>4H9=>4A7=>4 (C1 or C2) but C2=2 => 4C1. Then 4C1+7B3=>8A2. 8A2+2C2=>3B1. And finally 3B1+4C1+8A2+5H3 => empty cell A3 : impossible.

Hence elimination : <2> F6.

The first Christmas present !


7. 3rd observation
Note that if either 1 or 6 solves B6 D8 H4 F2 then by virtue of conjugacy, this forces 2 in B5 E8 H5 E2.
But we have seen that 2 can occupy only one of these cells. Therefore in three instances out of four B6 D8 H4 F2 cannot be either 1 or 6, so must be the bivalue 27.
Note also that the bivalues 27 in 3 of these 4 positions stops the corresponding candidates in B5 E8 H5 E2 from being 2 again because of conjugacy (eg if D8 is 2, E8 is not 2; if D8 is 7, E8 cannot be 2 because of the conjugacy rule established in point 4 above).
Consequently we can now make these statements about the pairs of cells : B6/B5 D8/E8 H4/H5 F2/E2 :

- in exactly three cases out of the 4, we have the bivalues 27/16. Call those pairs of bivalues the "included members" and the remaining pair the "excluded member".
- since we know from above (point 6) that one of the positions B5 E8 H5 E2 must be a 2, we can positively conclude that the excluded member must place "2".
Now observe that if D8/E8 is one of the included members and if F2/E2 is the excluded member, then D8=2 => E4=2 => E2 <2> but this is in contradiction with the fact that as excluded member E2=2. Thus D8 would be necessarily placed as 7.

Also observe that similar logic will apply for H4/H5 : if H4/H5 is included and B5/B6 is excluded, then H4 would be necessarily placed as 7.

Thus if both are included, we now have the certainty that we can place a 7 (either in D8 or H4) which combined with the placement of 2 in either E2 or B5 will enable via conjugacy to place all 2s and 7s (boxes 1, 2, 4, 6, 8 and 9). We also can be certain that such placements would reduce the monster to a domestic animal.

Note also that the chances of both being included are 50%.

We could proceed by fastidious contradictions (and they are in comparison to point 6 above)

But let's do something outrageous and actually test these two positions in a solver.

8. Test H4=7, B5=2. First make all the 2 and 7 placements which conjugacy enables (C2=2, B3=7, A6=7, F1=1, F2=7, D8=2, D9=7, G6=2, H7=2, J8=7).

A digital solver then demonstrates after simple steps that this is impossible (=> empty cell G4).

9. Test D8=7, E2=2. First make all the 2 and 7 placements which conjugacy enables (A2=7 B1=2; B6=7, C6=2; F3=7; F7=2; H4=2, J4=7; G8=2, H9=7).

A digital solver shows after simple steps that this solves the puzzle !

The second Christmas present !
Last edited by aran on Tue Dec 18, 2007 6:54 pm, edited 1 time in total.
aran
 
Posts: 334
Joined: 02 March 2007

Postby Red Ed » Tue Dec 18, 2007 10:07 pm

The 1st observation (or equivalent) was reported a while back: <here>; and <here>, too.

If you're on a roll then why not have a crack at the Golden Nugget. There are no cute attacks on that yet, AFAIK.
Red Ed
 
Posts: 633
Joined: 06 June 2005

Postby aran » Tue Dec 18, 2007 10:41 pm

I don't see that S Kurzhals has gone that far in the earlier post you mention, but do see that he has in the later post.
Thank's for pointing out, will edit first post accordingly.
PS : am mainly interested in simplifying things and in that spirit may have a look at the Golden Nugget, even if by the sound of your remark, the odds against are long
:)
aran
 
Posts: 334
Joined: 02 March 2007

Postby champagne » Sat Dec 22, 2007 10:17 am

hello,

you have a complete description of Easter Monster solving three threads below (full tagging level four examples). You can compare.

You have also the solution for DML 155, with no symmetry, intermediate step before Golden Nugget, the toughest I have seen.

I'll start developping the solution foru Golden Nugget next monday. I hope I'll have finished for the new year. It's a very long way thru full tagging process, but at least, it gives a way to crack it.

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


Return to Advanced solving techniques