wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> easy >> Su Doku
        
(Message started by: WombatDeath on Mar 18^th, 2005, 12:20pm)

Title: Su Doku
Post by WombatDeath on Mar 18^th, 2005, 12:20pm

Su Doku (http://www.timesonline.co.uk/section/0,,18209,00.html) 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 (http://www.timesonline.co.uk/article/0,,18209-1354177,00.html), medium (http://www.timesonline.co.uk/article/0,,18209-1354182,00.html), hard (http://www.timesonline.co.uk/article/0,,18209-1354184,00.html) and very hard (http://www.timesonline.co.uk/article/0,,18209-1354183,00.html) 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?

Title: Re: Su Doku
Post by Sir Col on Mar 18^th, 2005, 2:41pm

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!

Title: Re: Su Doku
Post by asterex on Mar 18^th, 2005, 5:01pm

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

Title: Re: Su Doku
Post by Sir Col on Mar 18^th, 2005, 5:31pm

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).

Title: Re: Su Doku
Post by WombatDeath on Mar 18^th, 2005, 7:20pm

on 03/18/05 at 14:41:13, 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.

Title: Re: Su Doku
Post by asterex on Mar 18^th, 2005, 8:37pm

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.

Title: Re: Su Doku
Post by Sir Col on Mar 19^th, 2005, 3:09am

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).

Title: Re: Su Doku
Post by Barukh on Mar 19^th, 2005, 6:31am

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?

Title: Re: Su Doku
Post by Sir Col on Mar 19^th, 2005, 9:40am

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 (http://mathworld.wolfram.com/NP-HardProblem.html); check out: http://www.phil.uu.nl/~oostrom/cki20/02-03/japansepuzzles/ASP.pdf)