Author |
Topic: Su Doku (Read 604 times) |
|
WombatDeath
Junior Member
Posts: 89
|
Su Doku is a sort of logic puzzle appearing daily in The Times newspaper. The idea is to place the digits 1-9 in a 9x9 grid according to certain rules, and the puzzles come in easy, medium, hard and very hard varieties.
I found the first three easy enough but the very hard puzzle has me baffled after placing four digits. I can't find a move that doesn't require a 50/50 guess, which the author maintains is never necessary.
Any thoughts?
|
|
 IP Logged |
|
|
|
Sir Col
Uberpuzzler
impudens simia et macrologus profundus fabulae
Gender: 
Posts: 1825
|
 |
Re: Su Doku
« Reply #1 on: Mar 18th, 2005, 2:41pm » |
 Quote  Modify
|
Hmm? I am able to deduce the contents of five cells with certainty:
5 at (1,9) [bottom left]
8 at (4,9)
3 at (1,5)
4 at (1,6)
9 at (6,6)
After this I'm stuck!
|
| « Last Edit: Mar 18th, 2005, 3:43pm by Sir Col » |
IP Logged |
mathschallenge.net / projecteuler.net
|
|
|
asterex
Guest
|
I'm not sure how you were sure of the 8. But a couple more hints. You can be sure of the 2 in column one and the 9 in column 4
|
|
IP Logged |
|
|
|
Sir Col
Uberpuzzler
impudens simia et macrologus profundus fabulae
Gender:
Posts: 1825
|
|
Re: Su Doku
« Reply #3 on: Mar 18th, 2005, 5:31pm » |
Quote Modify
|
After getting 5 in (1,9), the bottom row contains 1,3,4,5,7,9. The 4th column contains 2,6, so the only digit missing is 8.
This is like table tennis logic... how can we be sure of the 2 in the 1st column? The 2 could be in (1,4) or (1,5).
|
|
IP Logged |
mathschallenge.net / projecteuler.net
|
|
|
WombatDeath
Junior Member
Posts: 89
|
|
Re: Su Doku
« Reply #4 on: Mar 18th, 2005, 7:20pm » |
Quote Modify
|
on Mar 18th, 2005, 2:41pm, Sir Col wrote:| Hmm? I am able to deduce the contents of five cells with certainty |
|
You're quite right; I forgot about the 9 at (6, 6). It seems to me that there are four basic avenues to follow:
1) Where can x be placed in this row?
2) Where can x be placed in this column?
3) What value(s) of x can be placed in this cell?
4) Where can x be placed in this 3x3 box?
It's the fourth one that gives the nine at (6, 6), of course. The 3 and 6 follow from the fact that (1, 1) and (8, 1) have got 1 and 7 covered between them, even though we don't know which is which.
In my scribblings at work (the last two days have been amazingly unproductive...) I've marked all the cells which can be narrowed down to two possibilities. It really doesn't help, although it's interesting to note that 7 is a common theme in many of the 'potential pairs'. I have a feeling that cracking (1, 1) (or (1, 7) by extension) will solve much of the puzzle, as there's a fairly long chain which follows from that result.
|
|
IP Logged |
|
|
|
asterex
Guest
|
I have seven with certainty (I should have figured out that 8 in the bottom row quicker).
The first column is
?
6
2
9
3
4
8
?
5
The 2 must be (1,3) because the middle left box must have its 2 in the third column, so top left box must have it in the first column and the first row has a 2 already.
if you put 9 at (6,6) you must also put 9 at (4,1), the only place it can be it the top row.
|
|
IP Logged |
|
|
|
Sir Col
Uberpuzzler
impudens simia et macrologus profundus fabulae
Gender:
Posts: 1825
|
|
Re: Su Doku
« Reply #6 on: Mar 19th, 2005, 3:09am » |
Quote Modify
|
Argh! I hadn't copied the puzzle down properly and I missed the given 9 in (1,4)! And nice deduction with the 9 in (4,1), as the 9 in the first box must be on the second row.
I did some "research" to find strategies and I stumbled on this amazing website.
http://www.sudokusolver.co.uk/
It seems that Peter Wake, the author, doesn't want to take any credit, but kudos to him!
He's written a lovely JavaScript solver which not only provides the solution but gives a commentary on the reasoning that leads to the solution.
If you click on "Enter Start Grid As Text String" you can use this string to set up the puzzle:
_43_8_25_+6________+_____1_94+9____4_7_+___6_8___+_1_2____3+82_5_____+__ ______5+_34_9_71_
If you still want to complete it yourself, the following link, for "Solve Methods", presents the stategies used by his script:
http://www.sudokusolver.co.uk/solvemethods.html
However, although the solution is unique, it can only be solved by the "thread of Ariadne" method (guess and check).
|
| « Last Edit: Mar 19th, 2005, 3:19am by Sir Col » |
IP Logged |
mathschallenge.net / projecteuler.net
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Su Doku
« Reply #7 on: Mar 19th, 2005, 6:31am » |
Quote Modify
|
I have tried the easy puzzle with my 9 years old son; we made a mistake somewhere, and ended in a contradiction. Then, I ran the solver from Sir Col's link - it ended with the message that the puzzle did not solve.  I tried it twice, with the same result.
After expecting its solution, it turned out that the solver was just one step short from the actual solution.
Any comments? Is it a bug in the script?
|
|
IP Logged |
|
|
|
Sir Col
Uberpuzzler
impudens simia et macrologus profundus fabulae
Gender:
Posts: 1825
|
|
Re: Su Doku
« Reply #8 on: Mar 19th, 2005, 9:40am » |
Quote Modify
|
Interesting, Barukh. I've just emailed Peter about it.
In fact, I've been working on my own program to solve these puzzles and my version solves it exclusively using (what he calls) method A.
Quote:| Look across a row in the solution grid to see if there are any numbers that occur only once in the row. If so, the cell containing that occurance must be the solution. This rule is repeated for columns and blocks. |
|
I stumbled on another excellent website that has an Excel version of the solver (it uses VB script):
http://www.di-mgt.com.au/sudoku.html
(Apparently these puzzles are NP-Hard; check out: http://www.phil.uu.nl/~oostrom/cki20/02-03/japansepuzzles/ASP.pdf)
|
| « Last Edit: Mar 19th, 2005, 9:41am by Sir Col » |
IP Logged |
mathschallenge.net / projecteuler.net
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print
Remove