Looking for super defficult sudoku

Advanced methods and approaches for solving Sudoku puzzles

Looking for super defficult sudoku

Postby lenzgo » Wed May 24, 2006 10:08 am

hi everybody

at first I wanted to say that I'm from Switzerland so my english isn't perfect:)

a friend of mine told me that he could solve almost every sudoku if he had enough time. I didn't believe him and so we bet

of course I'm now looking for a sudoku that is nearly impossible to solve. it can have any size and doesn't matter if there are numbers or letters.
could anyone of you guys help me?

thank's a lot
lenzgo
 
Posts: 1
Joined: 24 May 2006

Postby ravel » Wed May 24, 2006 11:09 am

This is the hardest puzzle, i have seen so far. It is still unsolved (manually, without guesses), so your friend can become famous, when he solves it with logic steps:)

It is nr 89 from the top1465
Code: Select all
 +-------+-------+-------+
 | . . . | 3 . . | 5 . . |
 | . 5 . | . 1 . | . 3 . |
 | . . 7 | . . 4 | . . 1 |
 +-------+-------+-------+
 | 2 . . | . . . | 4 . . |
 | . 6 . | . 9 . | . . . |
 | . . 1 | . . 6 | . . 2 |
 +-------+-------+-------+
 | 8 . . | 7 . . | 2 . . |
 | . 9 . | . 8 . | . 5 . |
 | . . 5 | . . 9 | . . 7 |
 +-------+-------+-------+

It will become number 1 in a list with about 100 ultrahard puzzles.
ravel
 
Posts: 998
Joined: 21 February 2006

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

Hm, maybe I get famous...:

Solution to #89:

f1=9, e1=5, d9=5, d8=6, row4!=9 > f1!=9, d3=3

c5=2, (ab6=78, a5=6, c4=5, b4=9, a8=2, b7=7, ab9=4, b6=8, a6=7, b3=2, k2=2, gh3=6, (a1=1, a9=9, g8=9, k8=4, k5=3, k1=nil contradiction >)a2=1, k1=1, (g2=4, gh3=3, e3!=3 or f2=4, ef1=35, e3!=3>)e3!=3, gh3=3, g2=4, e3=4, a3=8, c2=3, k8=4, h4=4, k4=6, k5=3, g5=5, g6=1, h6=2, e4=2, h7=1, e16=35, e7=8, k7=nil contradiction >) c5!=2

h3=2 or k2=2, a5=2,b3=2 > a3!=2
k5=2 or a5=2, c8=2, b3=2, k2=2 > k4!=2
c8=2 or a8=2, k5=2, h3=2, c2=2 > c5!=2
a5=2 or k5=2, h3=2, b46=2 > a6!=2

c4=8, (c5=5, a6=7, b6=2, a5=6, b7=7, b4=9, a3b13=468, g6=5, k5=2, e4=2, h3=2, f45=4, b13=6, gh2=4, df2=78, e8=7, (a2=1, a1=9, gk2=34, g3=6, ab39=48 non-unique contradiction >)a2=2, c2=3, c1=9, a1=1, c7=6, c8=2, f7=9, f8=8, k7=8, k1=3, e6=8, e7=1, d8=6, de9=35, h7=3, h6=1, box5!=1 contradiction >) c4!=8

b4=8, (a6=7, b6=2, a5=6, c5=5, c4=9, b7=7, g6=5, k9=2, h3=2, e4=2, f45=4, (a3=4, b9=4, e1=4, f1=5, f4=4, row8!=4 contradiction >) a3=8, (a2=1, a8=2, ab9=4, c2=2, c1=3, f1=5, f4=4, row8!=4 contradiction >) a1=1, b1=9, (a2=4, b9=4, c2=2, c1=3, f1=5, f4=4, row8!=4 contradiction >) a2=2, c2=3, c1=6, g3=6, b3=4, e3=3, e1=4, k1=3, f1=5, c8=2, c7=8, k8=8, b9=6, d8=6, f7=9, f8=7, e8=1, e7=3 contradiction with e3=3 >)b4!=8, ab6=8

b4=2, (c4=9, c5=5, g6=5, e6=2, k5=2, h3=2, a5=6, ab6=7, (a2=1, c2=2, c1=3, c78=68, ab9=49, g25=34, g3=6, g9=9 contradiction with ab9=49 >) a1=1, b1=9, (k1=6, h4=6, h9=4, a8=4, b3=4, col3!=5 contradiction >) k1!=6, g3=6, e3=3, c1=6, c2=3, a2=2, c7=8, c8=2, k8=8, f7=9, f8=7, e8=1, e7=3 contradiction with e3=3 >) b4!=2

a5=2 or k5=2, h3=2, b6=2, a6=8, a5=7 > a5!=6

a2=8, (a1=1, a6=7, a5=2, c8=2, b3=2, k2=2, b6=8, a89=9, b7=7, c7=8, c2=3, g2=1, f2=4, d2=7, f5=7, e3=8, e4=4, ef1=35, f7=9, f8=8, box9!=8 >) a2!=8

c2=3, df2=78 or c1=3, ef1=45 > f2!=4

a8=7, (c8=2, a5=2, a6=8, b6=7, b3=2, k2=2, ab9=4, c2=8, e3=8, c1=3, ef1=45, df2=37, e8=1, b14=69, b7=8, b9=4, agh9=369, de9=58, d8=6, f8=9, g9=9, c7=9, b4=9, b1=6, a1=9, , a2=1, a3=4, a9=6, h9=3, k1=1, g2=4, h3=6, g3=3, k8=4, k7=8 contradiction with b7=8 >) a8!=7, b7=7

c8=2 or a8=2, a5=7, a6=8, b6=2, c2=2, c1=3, ef1=45, b3=8, e3=3, e4=2, e789=8, h3=2, ab9=4, h4=4, k5=2, k14=16, f5=4, f7=3, k7=8, c8=8 > c8=28

c7=8, (c8=2, c2=3, b149=469, hk7=6, k8=8, f7=9, f8=7, e8=1, d8=6, e7=3, f2=8, e3=4, d2=7, e1=5, f1=3, e6=7, a6=8, b6=2, e4=2, b3=8, a3=6, c1=9, b1=4, h3=2, g3=3, ag89=49 non-unique (or additionally k17=16, k4=4, h9=4, ah9=9 contradiction)>) c7!=8, c457=569, c1=3, ef1=45, b14=69

e3=8 or e3=3, df2=8, c2=2, a8=2, a5=7, a6=8 > a3!=8
f7=9 or f8=9, c7=9, b4=9, a1=9, b1=6, a3=4, b9=4, h4=4, f5=4, f2=7, f7=3 > f7!=8
c7=6 or c7=9, b4=9, b1=6, a3=4, b9=4, h4=4, k14=16 > k7!=6
c7=6, b4=6 or c7=9, b4=9, b1=6, a1=9, k1=1, f7=3, k7=8, a3=4, b9=4, h4=4, k4=6 > c4!=6, h4!=6
c8=2, c2=8, e3=8 or a8=2, c8=8, k7=8, b6=2, e4=2 > e478!=8, k7=8, k25=23

a8=2 or c8=2, c2=8, e3=8, gh3=3, k5=3, a5=2 > a2!=2
b3=2 or c2=2, c8=8, b9=4 > b3!=4, b9=4
k2=3 or k2=2, c2=8, df2=37 > g2!=3
c7=6 or c7=9, b4=9, b1=6, a3=4, g2=4, k8=4, h4=4, f5=4, e4=2, k1=1, k4=6, d4=1, c4=5, f4=8, f8=9, g9=9, f7=3, e7=1, e8=7, h7=6, h9=3, g8=1, h6=1, b6=2, b3=8, e3=3, e9=8, a9=6 > a8!=6
k5=3 or k5=2, b6=2, b3=8, e3=3, c2=2, k2=3, h3=2, h4=4, f5=4, e9=8, f7=3, d9=5, d8=6, f1=5, f4=8, f2=7, d2=8, d4=1, a5=7, d5=3 > fg5!=3
f2=3 or f7=3, f8=9, c7=9, b4=9, b1=6, a3=4, h4=4, f5=4, f2=7 > f2!=8
f7=9, f2=3, k5=3 or f8=9, c7=9, a9=6, h9=3 > h6!=3
a3=6, (k1=6, g5=6, c7=6, h9=6, d8=6, f7=9, b4=6, b1=9, a1=1, a2=4, g2=1, c5=5, g6=5, k5=3, d5=7, f5=4, a5=2, b3=2, k2=2, c2=8, e3=8, a6=7, f1=5, f4=8, f8=7, f2=3, d2=nil contradiction >) a3=4, which solves the remaining numbers.

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

Postby ravel » Wed Jul 26, 2006 3:02 pm

Thanks Maria,

i will look at your solution, when i can find some time and provide a link to it from my hardest sudokus thread.
You can see there, that Viggo already has solved the puzzle and other toughies were found in the meantime that i rated even harder.
ravel
 
Posts: 998
Joined: 21 February 2006

Postby udosuk » Wed Jul 26, 2006 4:22 pm

Maria, I can spot the word "contradiction" appearing several times in your walkthrough, so I'm afraid it won't make you famous anyways...

Also, you might like to learn the proper "lingo" of posting walkthrough so as to communicate better with the experts here... Representing cells with something like "r5c5" instead of chess notation like "e5" would be much more desired...
udosuk
 
Posts: 2698
Joined: 17 July 2005

Postby maria45 » Thu Jul 27, 2006 7:04 am

Hello udosuk,

why would a contradiction be considered something inappropriate? Even most single solution steps could be called contradiction. A single value in a cell must be placed there, because every other value would be a contradiction. Or consider a naked pair a,b. Each value outside the naked pair cells would provoke a contradiction. So even the most simple steps use covert contradictions.

As for the notation, I notice already several in use. I considered switching to one of them, but since I like my notation best (as everyone does, I assume), and it is very short, and the solutions I give here are quite lengthy, I simply stick to my notation.

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

Postby ravel » Thu Jul 27, 2006 7:33 am

To say it one more time:
Since A=>B is equivalent to (not B) => (not A) every chain that leads to a contradiction can be expressed as a (multiple) chain (with case distinctions) without contradiction. Instead of A=x => contradiction C (e.g B empty) you write it backwards: no contradiction C (e.g. for all values in B) => A<>x. But you will see, that in most cases the contradiction chain is shorter and easier to read (and find), so i prefer it.

Concerning the notation i dont have any more problems than with others. An advantage of this one is, that it can be read without studying the notation first.
ravel
 
Posts: 998
Joined: 21 February 2006

Postby udosuk » Thu Jul 27, 2006 7:48 am

Well, I must apologize... I thought when they said logical they meant no "trial and error" (because any puzzle is solvable with an amount of "trial and error")... Of course, using "forcing chains" could be interpreted as a form of "trial and error"... So the question is, are your "contradiction chains" short enough for them to accept? It's for the experts to decide...
udosuk
 
Posts: 2698
Joined: 17 July 2005

Postby daj95376 » Thu Jul 27, 2006 5:29 pm

[Edited:] Forget that I opened my mouth!
Last edited by daj95376 on Thu Jul 27, 2006 11:52 pm, edited 1 time in total.
daj95376
2014 Supporter
 
Posts: 2624
Joined: 15 May 2006

Postby ronk » Thu Jul 27, 2006 6:08 pm

daj95376 wrote:They often use the notation => as ravel defines it above. In this context, the negative/negation is asserted in the definition.

Huh? I think => just stands for the word 'implies'.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby daj95376 » Thu Jul 27, 2006 9:49 pm

[Edited:] Forget that I opened my mouth.
Last edited by daj95376 on Thu Jul 27, 2006 11:53 pm, edited 1 time in total.
daj95376
2014 Supporter
 
Posts: 2624
Joined: 15 May 2006

Postby ronk » Fri Jul 28, 2006 12:43 am

daj95376 wrote:
ronk wrote:I think => just stands for the word 'implies'.
That's how I would like to use =>, but ravel (and possibly others) keep insisting that it has another, technical definition that's based on negation.

Are you saying that because ...
ravel wrote:Since A=>B is equivalent to (not B) => (not A) ...

If so, I see that simply as being able to read a canonical implication chain both left-to-right and right-to-left -- by interchanging the "equals" (=)and "not equals" (<>) and changing the direction of the implication arrows. That's hardly a redefinition.

[edit: This is rather vague. I'll be glad to clarify if necessary.]
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby ravel » Fri Jul 28, 2006 9:41 am

Hi Maria,

i went through your solution now. Obviously you are not using any program, not even for the notation, because sometimes it shows earlier contradictions. Really astonishing.

I found some typos and did not understand some details. I refer to "steps" what you devided by blank lines. Please clarify, what i missed:

step 1: typo d3=9
step 2: after g2=4 i still had a 4 in a3 and e1, so i dont see e3=4
step 3 can be done with a swordfish (c5 is a typo, should be c4)
step 4: typo gh3=4 -> gk2=4, df2=78 ? can be 3 - not necessary, a1=1 before c1=9, e6=8 (needs e3=3?), box5!=1: have 1 in e4 (needs e9=5, f1=5, e4=5 ?)
step 5: typo k9=2->k5=2, after c1=3 i have f1=45 (2 times) (?), at the end i have the contradicton e8=1 and e7=1
step 6: typo col3!=6, again i have the contradiction e8=1, e7=1 (3 in d9 and hk7)
step 11: contradiction already after g2=4, because g8=4

btw in chess the characters stand for columns, not rows. Is there a reason, why you did it different?
ravel
 
Posts: 998
Joined: 21 February 2006

Postby maria45 » Fri Jul 28, 2006 3:28 pm

Hi Ravel,

no program: right.

Typos: right.

step2: dunno where this went, but between g2=4 and e3=4 insert h4=4, h6=2, h7=1, g6=1, e679=358, so the whole line should be:

c5=2, (ab6=78, a5=6, c4=5, b4=9, a8=2, b7=7, ab9=4, b6=8, a6=7, b3=2, k2=2, gh3=6, (a1=1, a9=9, g8=9, k8=4, k5=3, k1=nil contradiction >)a2=1, k1=1, (g2=4, gh3=3, e3!=3 or f2=4, ef1=35, e3!=3>)e3!=3, gh3=3, g2=4, h4=4, h6=2, h7=1, g6=1, e679=358, e3=4, a3=8, c2=3, k8=4, k4=6, k5=3, g5=5, e4=2, e16=35, e7=8, k7=nil contradiction >) c5!=2

contradictions: mostly there are several at once, numbers double or places are nil, sometimes I notice a bit late, because I do this mostly in my head, but I'm still getting better...

rows/cols and chess board notation: I know, but I noticed this naming convention on some other sudoku boards, so I did it likewise.

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


Return to Advanced solving techniques

cron