The Toughest Known Puzzle

Post puzzles for others to solve here.

Postby ravel » Wed May 10, 2006 2:33 pm

Hi inventor,

thanks for verifying that those puzzles are extra hard.

inventor wrote:When I edited this "Emily's friend's" into the sudoku program (the program for this site), it refused to verify.... Have someone others experienced that? What is wrong?

This program calls sudokus "invalid", which are assumed to be "unfairly hard".
What is the bottom line here? Well, obiously that any supertechnique solving any sudoku is not found yet! But we try, don't we?

There are such supertechniques, but there ouputs are not really human readable (i.e my program could write some series of monster chains to solve these hard puzzles). And i dont believe that a future super technique could provide better solutions, when current techniques already allow an elegant solution.

If you (or others) have more such hard ones, let me know!

When i stumble against an ultra hard puzzle, i will add it to the list above.
ravel
 
Posts: 998
Joined: 21 February 2006

Postby daj95376 » Mon May 15, 2006 7:16 pm

Another application of Brute Force Elimination Chains with Naked/Hidden Singles and Locked Candidates:

Code: Select all
Puzzle #77 from top1465:
7.....4...2..7..8...3..8..9...5..3...6..2..9...1..7..6...3..9...3..4..6...9..1..5

r9c8    =  3     Hidden Single
    b9  =  4     Locked Candidate (1)
r1c3    <> 5     BFE
r4c6    <> 9     BFE
r5c4    <> 4     BFE
r6c5    <> 8     BFE
r2c7    =  5     BFE
trivial from here
daj95376
2014 Supporter
 
Posts: 2624
Joined: 15 May 2006

Postby Viggo » Mon May 22, 2006 5:10 pm

ravel wrote:This puzzle is that hard, that i had to put another loop around my program to get some hints, how it could be solved. The result so far is, that it can be cracked with one of the following 10 step brute force eliminations.

r1c2<>5, r6c2<>4, r5c7<>1, r3c4<>4, r1c6<>2, r2c9<>1, r1c5<>9, r6c5<>3, r5c9<>1, r5c7<>5
r4c6<>4, r1c6<>2, r6c2<>4, r5c7<>1, r3c4<>4, r2c9<>1, r1c5<>9, r6c5<>3, r5c9<>1, r1c8<>1
r7c6<>6, r1c6<>2, r6c2<>4, r5c7<>1, r3c4<>4, r2c9<>1, r1c5<>9, r6c5<>3, r5c9<>1, r2c7<>6
r1c4<>1, r6c2<>4, r5c9<>1, r4c6<>9, r4c6<>4, r1c6<>2, r5c7<>1, r2c3<>4, r6c5<>3, r1c8<>1

Each elimination can be made with singles, tuples, locked candidates, xwing and UR type 1, but i dont know, how to do it effectively or if some of them can be done with advanced methods.
To check all possible orders of eliminations to find an optimum would last years with my program, so i did it in a greedy way starting from each of the 20 eliminations that are possible at the beginning. Since UR type 2 is not implemented, Carculs first chain would need 3 eliminations. So many improvements are possible.

Compare: for the ancient toughest puzzle easily 4 step eliminations could be found:
r3c5<>1, r2c3<>4, r5c4<>8, r3c2<>9
r3c5<>1, r3c5<>8, r2c3<>4, r3c2<>9
r3c5<>1, r5c5<>1, r2c3<>4, r3c2<>9


You may have noticed, that RW and I have tried to solve the Emilys friend's puzzle - see. See here
I should like to see Ravel solvers suggested 4 step eliminations for this puzzle. Can Ravel or somebody else supply that? Is the solver in some way public for me to use?

I suppose it is hard to rate these puzzles. Do somebody know a good link to such a discussion? I suppose it should be here at some place. In general I think, that the number of links in total used in the error nets would be a better figure. If you are able to make 30 much simpler (only few links used) elimination steps, then I think the puzzle is easier solved for a human. If you compress the number of steps needed by the solver, you may end up with very complicated steps, that almost add values to all cells before the contradiction is met.

/Viggo
Viggo
 
Posts: 60
Joined: 21 April 2006

Postby ravel » Mon May 22, 2006 6:07 pm

Viggo wrote:You may have noticed, that RW and I have tried to solve the Emilys friend's puzzle - see. See here

Yes, i saw that, very nice.
I should like to see Ravel solvers suggested 4 step eliminations for this puzzle. Can Ravel or somebody else supply that? Is the solver in some way public for me to use?

As i said, this program tries to find a good order to minimize the number of brute force steps (which mostly only can be written as monster chains) needed to solve the puzzle. It therefore is not qualified for finding an elegant solution, but the number of steps it needs is a rather good measure for extremely hard puzzles.
It is under construction and it would take me too much time to improve the code so much, that i would dare to make it public.
The 4-steppers are:
Code: Select all
r1c9<>1, r8c3<>3, r5c6<>1, r4c4<>7
r2c9<>4, r6c9<>4, r2c6<>4, r4c4<>7
r4c2<>8, r8c3<>3, r7c9<>1, r7c5<>9
r5c4<>8, r5c4<>4, r5c6<>1, r4c4<>7
r6c9<>4, r2c6<>4, r5c4<>8, r4c4<>7
r8c8<>1, r8c3<>3, r5c6<>1, r4c4<>7
r9c9<>2, r7c9<>1, r2c6<>4, r4c4<>7


BTW, i found today that nr 89 of the top1465 is the first puzzle, that my program could not solve:)
ravel
 
Posts: 998
Joined: 21 February 2006

Postby Viggo » Mon May 22, 2006 6:48 pm

Ravel, thank you for your reply

Ravel wrote:As i said, this program tries to find a good order to minimize the number of brute force steps (which mostly only can be written as monster chains) needed to solve the puzzle. It therefore is not qualified for finding an elegant solution, but the number of steps it needs is a rather good measure for extremely hard puzzles.


I'am sorry not to have noticed your previous comment. Your comment seems to be very true. I have compared your solvers eliminations with RW's and my eliminations used in the error nets. Not even one is equal! So in order to make a solvers hints more human, it may try to propose steps with small error nets.

Ravel wrote:BTW, i found today that nr 89 of the top1465 is the first puzzle, that my program could not solve:)


Interesting - a possible new candidate for a very hard puzzle?:D

/Viggo
Viggo
 
Posts: 60
Joined: 21 April 2006

Postby Alain David » Tue May 30, 2006 8:05 pm

As I am new in the sudoku world and does not understand all the technicities above, could somebody tell me if the solution of this puzzle is :



786 912 453
925 473 681
143 658 729

284 596 317
367 124 598
951 837 246

612 385 974
538 749 162
479 261 835

I spent about one hour to solve it, with 4 guesses
Alain David
 
Posts: 2
Joined: 27 May 2006

The solution

Postby keith » Tue May 30, 2006 9:14 pm

Alain,

You have two <9>'s in C1, two <8'>'s in C2.

Here is the solution:

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


I make no claim about solving it myself! This is from Sudoku Susser.

Keith
keith
2017 Supporter
 
Posts: 209
Joined: 03 April 2006

Re: The Toughest Known Puzzle

Postby maria45 » Wed Jul 26, 2006 2:38 pm

Hello Carcul,
Carcul wrote:So, the purpose of this thread is to collect all logical solutions and other studies regarding Puzzle #77, and I invite here the others users of this forum to do that in this thread.

well, I will add my solution:

d6=6 or d5=6, k5=8, g5=5, c5=1, c12b3=456, a3=8, a456=6 > b6!=6
d6=6 or d5=6, (k2=4, c2=5 or k2=7, k7=2, f7=5 > f2!=5
k2=7 or k2=4, f2=9, d6=9, h6=2, g6=6, k4=7 > k7!=7 > k7=2, f7=5
k2=4 or k2=7, k4=6, g6=2, h6=9, f5=9, f2=4 > cd2!=4 > c2=5, b6=5, a8=5, b9=3 > ck1=46
h6=9 or h6=2, g6=6, k4=7, k2=4, f2=9, d6=9 > a6!=9
a2=9 or a2=1, a9=2, c4=2, c1=4, k2=4, k4=7, h4=9 > a4!=9
a4=2 or a4=6, k4=7, k2=4, f2=9, a2=1, a9=2 > a6!=2, ac4=2, h4!=2
c7=7, e7=8, h7=1 or c7=6, c8=7, c1=4, k1=6, k2=4, f2=9, f8=4, g8=1 > gh9!=1, ad9=12
h4=9, k4=7, k2=4, f2=9, a2=1, b7=1, g8=1, g9=4, eh79=78 contradiction > h4=7, k4=6, a6=6)
> g6!=6

d6=6 or d5=6, k5=8, g5=5, g6=2, h6=9 > d6!=9
d5=6, d6=4, (e6=3), k5=8, g5=5, g6=2, h6=9, (h4=7), (k4=6), a6=6, b6=5, c5=1, a5=3, f5=9, e4=1, f4=8, c12b3=456, a3=8, b1a2=19, cf2=45, k2=7, k7=2, a8=5, g3=6, b3=4, b4=9, a4=2, f2=4, f8=2, box3!=2 contradiction > d5!=6, d6=6

c5=6, (etc., c12=1
b4=4, b3=5, c4=2, e6=4, e1=3, e7=5, c7=2, k7=7, k2=4, c2=1, h1=1, 7!=1 > b4=1, b9=3, d5=1, f45=9
c4=4 or c4=2, a4=9, f5=9, e6=3, a6=5, b6=4, b3=5, c12=14, c78=57, a89=12, f1=3, h379=128, h1=5, f2=5, e14=48, e3=7, e7=5, c7=7, k7=2, f7=8, f4=4 > e4!=4, e4=8
f2=4 or f2=5, e16=35, e3=7, e9=1, a9=2, a4=9, f4=4, e6=3, e1=4 > d13e3f18!=4, b3=4, b6=5, a6=3, a5=9, a4=2, c4=4, a9=1, a8=5, f4=4, e6=3, f5=9, f1=3, f2=5, c2=1, c1=5, e1=4, k1=2, k7=7, k2=4, c7=2, c8=7, d1=8, h1=1, h7=8, h9=2, h3=5, g2=7, g3=8, e3=7, d3=2, d8=4, f8=2, g8=1, g9=4, e9=1, e7=5, f7=8, f7=?, contradiction >) c5!=6

a5=6, (k5=8, g5=5, g6=2, h6=9, h4=7, k4=6, c5=1, e4=1, d5=9, f5=3, e6=4, f4=8, e1=3, c12b3=456, a3=8, b1a2=19, ab6=35
b6=5 or b6=3, b9=1, a2=1, dgk2=478, c2=5 > b3!=5, c12=5
c4=4, c2=5 or c4=2, a4=9, a2=1, dgk2=478, c2=5 > c2=5
f2=4 or f2=9, b1=9, b4=4, d3=4 > d12f1!=4
k7=2 or k7=7, k2=4, k1=2, f2=9, f1=5, f7=2 > ch7!=2
k7=7 or k7=2, k1=4, c1=6, c7=7 > e7!=7
f7=5 or f7=2, k7=7, k2=4, f2=9, a2=1, b9=1, b6=3, b7=5 > e7!=5, e7=8, e9=7, e3=5, h7=1, h1=5
f1=2 or f1=9, f2=4, k2=7, d2=8, d1=2 > k1!=2, k1=4, k2=7, k7=2, f7=5, b7=6, c7=7, c8=2, c4=4, c1=6, b3=4, b4=9, a4=2, a8=5, a6=3, b6=5, a9=1, b9=3, a2=9, b1=1, g1=8, h3=2, h9=8, g3=6, d3=7, d2=8, d1=2, f1=9, f2=4, g2=1, d9=2, g9=4, g8=7, f8=4, d8=1, d19=2 contradiction >) a5!=6, gk5=6

d5=1, (c5=5, gk5=68, f45=9
b6=4 or e6=4, e4=8, f4=9, f5=3, a5=9 > b6!=9, be6=34
b6=4 or b6=3, a5=9, a6=2, e6=4, e4=8, f4=9, hk4=27, b9=1, a8=5, b7=6, b4=4 > c4!=4, b13!=4, de4=4
b1=9 or a2=9, a3=8, a4=6, a6=2, c4=1, b1=1 > b1=19
d2=9, de3=47 or d1=9, b1=1, c2=4, c1=6, b3=5, a3=8, > d3!=8, e3!=58
f2=8, a3=8 or f2=5, e7=5, a8=5 > a3!=5
h6=9, a6=2, g6=5, c124=146, c78=27, ab9=13, a8=5, b3=5, h1=5, f2=5, e7=5, box6!=1 contradiction > h6!=9, a6=9, h4=9, k4=7, a5=3, b6=4, e6=3, f5=9, f1=3, b1=9, d2=9, d1=2, k7=2, f27=58, f4=4, e4=8, e1=5, f2=8, a3=8, k2=4, de3=47, g2=7, c2=1, a2=5, b3=6, c1=4, b4=1, b9=3, b7=5, a89=12, c8=7, c7=6, c4=2, a4=6, f7=5, bf7=5 contradiction >) d5!=1

d5=9, (e4=1, f45=8
f6=4, b6=4 or f4=8, f5=3, ac5=15 > b6!=5
f1=3, f5=8, k5=6, g5=5, g6=2, h6=9, a6=5, b6=4, c5=1, c12b3=456, a3=8, a4=6, b4=9, a2=9, box4!=9 contradiction >) d5!=9, d5=8, k5=6, g5=5, g6=2, h6=9, c5=1, c12b3=456, a3=8, f45=9, a2b1=19, e4=1

f4=4, b6=4 or f4=9, a5=9, a2=1, b9=1, b6=3 > b6!=5, a6=5
f4=4 or f4=9, a5=9, a2=1, a8=2, c4=2 > c4!=4, c12=4, de3=4
d1=2 or d1=9, b4=9, f5=9, f1=3 > f1!=2, d13=2
f2=8 or f2=5, c2=4, k1=4, k7=2, f7=8 > f1!=8
a4=6, c4=2
cf28=5 x-wing > cf17!=5, f1=3, f5=9, a5=3, b6=4, b4=9, f4=4, e6=3, b1=1, a2=9, g2=1, d2=7, d1=9, d3=2, e3=4, b9=3, h7=1
e1=8 or e1=5, k12h1=248, g1=6 > g1!=8, which solves the remaining numbers.

Greetings, Maria
maria45
 
Posts: 54
Joined: 23 October 2005

Previous

Return to Puzzles

cron