A new "toughest puzzle" champion?

Advanced methods and approaches for solving Sudoku puzzles

Re: A new "toughest puzzle" champion?

Postby ronk » Sat Dec 03, 2005 5:30 am

rubylips wrote:Consider the chain r2c1-9-r4c1~9~r4c5~5~r2c5+<5|7>+r2c7.
When the cell r2c7 contains the value 9, some other value must occupy the cell r2c1, which means that the value 7 must occupy the cell r2c7 - a contradiction.
Therefore, the cell r2c7 cannot contain the value 9.
- The move r2c7:=9 has been eliminated.

Thanks. From my sticking point, that breaks the puzzle. Unfortunately, my program had to make 15 T&E eliminations to get to that point.

Suggestion: I think the eq'n should stand alone and loop from r2c7 to r2c7 to read ...

r2c7~9~r2c1-9-r4c1~9~r4c5~5~r2c5+<5|7>+r2c7

Then from the equation alone it's easy to see ... r2c7 equal to 9 ... propagates to ... r2c7 equal to 7 ... a contradiction.

P.S.
In the equation, it appears '-' indicates a strong link, '~' a weak link, and '+<5|7>+' a strong Almost Disjoint Subset (ADS) link.
But why the verbose ADS link notation? Why not just '+57+'?
Or since '-' already means strong link elsewhere, why not even '-57-' ?
Last edited by ronk on Sat Dec 03, 2005 7:43 am, edited 1 time in total.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby dukuso » Sat Dec 03, 2005 6:20 am

I didn't find that puzzle, it's from Gordon Royle's list of 10 million
(and growing) sudokus with 18 clues.
We filtered them with http://magictour/free.fr/suexrate.exe
recently for hard sudokus. Hard, that is for a canonical backtracking
program ("dancing links").

While Gordon's 17-clue-sudoku generation seems to come to an
end ( there are probably about 40000 non-equivalent
17-clue-sudokus only) there are no such signs for
18-clue-sudokus, so many more of them could be created.
It seems that these 17,18s have a much better chance of being
really hard than normal sudokus.

-Guenter
dukuso
 
Posts: 479
Joined: 25 June 2005

complicated solution

Postby bennys » Sat Dec 03, 2005 7:48 am

Code: Select all
I found a complicated solution

+-------------------------+-------------------------+-------------------------+
| 7       126     8       | 459     4569    4569    | 3       1456    1259    |
| 469     36      3469    | 2       34569   1       | 4679    45678   5789    |
| 5       1236    123469  | 78      3469    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       |
+-------------------------+-------------------------+-------------------------+
| 128     9       12357   | 6       125     2358    | 127     1378    4       |
| 12468   12368   12346   | 3489    7       23489   | 5       1368    1289    |
| 12468   1235678 1234567 | 34589   12459   234589  | 12679   13678   12789   |
+-------------------------+-------------------------+-------------------------+



A={R2C8,R2C9}
B={R4C7,R5C7,R6C7}
C={R1C2,R2C2,R3C2,R4C8}
G={R5C8,R5C9}
H={R7C1,R7C7}
D={R5C4,R5C7,R5C8,R5C9}


lets assume R2C5<>5

A is locked on 58 =>
R2C7=7 =>
B locked on 148 =>
G locked on 57 =>
C locked on 1236 =>
R8C2=8 =>
H locked on 12 =>
R7C5=5 => R4C5=9 =>
D is locked on 1457 => R5C7=1
but R4C1,R4C7,R7C7,R7C1 are x wing on 1 contradiction.
After that the puzzle is solved

 
bennys
 
Posts: 156
Joined: 28 September 2005

Re: complicated solution

Postby ronk » Sat Dec 03, 2005 2:12 pm

bennys wrote:A={R2C8,R2C9}
B={R4C7,R5C7,R6C7}
C={R1C2,R2C2,R3C2,R4C8}
G={R5C8,R5C9}
H={R7C1,R7C7}
D={R5C4,R5C7,R5C8,R5C9}
lets assume R2C5<>5

A is locked on 58 =>
R2C7=7 =>
B locked on 148 =>
......

The 'R2C5<>5' doesn't seem to fit here unless the starting point is the unidentified Almost Locked Subset ...
X={R2C1,R2C2,R2C3,R2C5,R2C7}={345679}. Then since the 5 and 7 each appear in only one cell, R2C5<>5 => R2C7=7, and there is no need to even identify set A.

But AFAIK one can't make an elimination based on a conflict unless one starts with an '=' instead of an '<>' ... so one might as well just start with (assume) the R2C7=7 and ignore both sets A and X. The elimination is R2C7#7.

Also set C={R1C2,R2C2,R3C2,R5C2}
I found a complicated solution

Amen to the complicated ... but it's arguably the toughest puzzle known ... currently.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

About C

Postby bennys » Sat Dec 03, 2005 6:14 pm

About C you are right.
About R2C5<>5 I am showing that its =5 using the contradiction that I get.
No I am not using almost locked subset.
simply after removing 5 from R2C5 the only cells that has 58 as candidates in R2 are in A. and then the only candidate for 7 in R2 is R2C7.
bennys
 
Posts: 156
Joined: 28 September 2005

Re: About C

Postby ronk » Sat Dec 03, 2005 7:55 pm

bennys wrote:About R2C5<>5 I am showing that its =5 using the contradiction that I get.
No I am not using almost locked subset.

OK, I didn't notice the naked quad {R2C1,R2C2,R2C3,R2C5}={3469} after eliminating R2C5#5. But that set of 4 locations starts out with 5 candidates. Doesn't that too fit the definition of an almost locked set?
bennys wrote:simply after removing 5 from R2C5 the only cells that has 58 as candidates in R2 are in A. and then the only candidate for 7 in R2 is R2C7

Those are reversed IMO. The naked quad leaves 7 as a naked single in R2C7, and *then* A=58 due to both the naked quad and naked single.
ronk wrote:But AFAIK one can't make an elimination based on a conflict unless one starts with an '=' instead of an '<>' ...

Sorry, that statement was (and is) incorrect.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

I can but I dont

Postby bennys » Sat Dec 03, 2005 8:28 pm

I can use almost locked sets but I dont
As I said "simply after removing 5 from R2C5 the only cells that has 58 as candidates in R2 are in A" (Hidden Pairs)so A is locked on 58.
bennys
 
Posts: 156
Joined: 28 September 2005

Postby Bob Hanson » Sun Dec 04, 2005 1:03 pm

Thank you for pointing out these two puzzles. I've added them as "+depth" and "hardest" at the Sudoku Assistant:

http://www.stolaf.edu/people/hansonr/sudoku

Their solution required adding the element of depth of checking for subset elimination in the hypothesis and proof (trial and error) stage.

Is there really nothing out there harder than these?
Bob Hanson
 
Posts: 75
Joined: 04 December 2005

Postby Lummox JR » Thu Dec 15, 2005 1:19 am

After mulling this puzzle over a bit I think what worries me most about it is that it implies difficulty has no upper bound, and T&E has potentially infinite complexity. Simple T&E does not solve it.

As Trebor said, adding box-line interactions to tabling will solve the puzzle. This implies there may be puzzles out there requiring tabled implications that involve using any available technique.
Lummox JR
 
Posts: 125
Joined: 22 September 2005

Postby gsf » Thu Dec 15, 2005 6:37 am

Ruud wrote:I've done some tests on this little monster:

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


With only singles and line-box interactions, no magic cells are available.

this puzzle is FN-2-constrained meaning the magic cells come in pairs for the simplest constraints:
Code: Select all
[1,6]=6*{[6,6]=7}
[1,9]=5*{[3,4]=7[3,6]=8[6,6]=7[9,4]=8}
[2,8]=7*{[4,3]=7}
[4,3]=7*{[5,2]=6[5,9]=7[7,8]=8}
[5,2]=6*{[6,6]=7}
[5,6]=2*{[6,6]=7}
[5,9]=7*{[6,6]=7}
[6,1]=8*{[6,6]=7}
[6,3]=2*{[6,6]=7}
[6,5]=6*{[6,6]=7}
[6,6]=7*{[9,5]=2}

where the cell on the left of * can be paired with any cell in {...} to solve using the simplest constraints
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Postby Bob Hanson » Thu Dec 15, 2005 6:30 pm

Sudoku Assistant reports:


Done! (59 steps) W3MsP++

728 946 315
934 251 678
516 738 249

147 593 826
369 482 157
852 167 493

293 615 784
481 379 562
675 824 931

So that's:

W3 a swordfish
Ms single strong chain analysis
P++ next-level trial and error through subset elimination/grids

I count 6 applications of trial and error. That's difficult.
Bob Hanson
 
Posts: 75
Joined: 04 December 2005

Previous

Return to Advanced solving techniques