The puzzle that ate the world?!

May 10, 2005 7:11 PM

The puzzle that ate the world?! It's called Su Doku. It came from Japan. It's deceptively simple, but a brief tutorial reveals hidden depths. It's spreading like gangbusters through the puzzle-obsessed British public, where it is making major news and being rapidly added to the country's newspapers. Fortunately, archived puzzles and free software are out there to provide puzzle addicts their latest fix. C'mon... give it a try. It's only *one* little puzzle. (Heh, heh.)
posted by insomnia_lj (30 comments total)

Games Magazine has had these for a while. They print lots of variations as well.
posted by donth at 7:15 PM on May 10, 2005

These things are a snap!
posted by brain_drain at 7:34 PM on May 10, 2005

from Mike Spivey, Oxford University Computing Laboratory

Don Knuth observed that the Sudoku problem is an instance of a class of exact cover problems that can be formulated in terms of Boolean matrices and solved by a backtracking procedure he calls "dancing links", using pointer manipulations to cover and uncover rows and columns of the matrix.
...
Knuth's approach reformulates the problem in terms of finding an exact cover of a 729 x 324 Boolean matrix. The 324 columns correspond to the 4 x 81 constraints enumerated above, and each of the 729 rows corresponds to a move that puts one of the 9 digits in one of the 81 cells. Each row contains four 1's, corresponding to the way the move satisfies one constraint from each group. The problem becomes one of finding a subset of the rows that contains exactly one 1 in each column.

It's best always to select a constraint that has the smallest number of remaining possibilities. If that number is zero, then we have followed a dead end, and should backtrack. If the number is one, then we can definitely fill in a square, and there is no genuine choice. If it is more than one, then we can explore all the possibilities in a depth-first pattern.

This shows that the distinction between forced moves and arbitrary choices is artificial, since a forced move is just the special case where there is only one choice. Knuth's method also treats all four kinds of constraint uniformly, so that it can not only backtrack over all the digits that can fit in a square, but also over all the places that a given digit can be put into a row or column or block. None of the submitted solutions for the main competition can do that -- it may not be necessary for Sudoku, but it does reveal a symmetry to the problem that is rather nice.

For Knuth's method of dancing links, see this paper on his page of preprints.
posted by MonkeySaltedNuts at 7:55 PM on May 10, 2005

cute. but easy.
posted by blacklite at 8:29 PM on May 10, 2005

iSudoku for OS X (donationware)
posted by indices at 9:06 PM on May 10, 2005

Posted once before...
posted by precipice at 9:18 PM on May 10, 2005

blah they put these in Games magazine every month and i have stopped doing them because they are too easy.
posted by MrLint at 10:06 PM on May 10, 2005

The thinking person's crack cocaine has arrived on our shores.

For joy.
posted by airguitar at 10:06 PM on May 10, 2005

yeah, it's fun but it's hardly what I'd consider the next big thing in puzzles.
posted by BuddhaInABucket at 11:38 PM on May 10, 2005

Yeah these are pretty easy. I developed a notation and solved one in about 15 minutes. Most programmers should make easy work of these. These are appealing I think because you have a clear methodical process for completing them and they reward you by falling apart quickly in the end.
posted by jeblis at 11:53 PM on May 10, 2005

Seems pretty simple, like jeblis said. Maybe it's because I did some time in CS, but it really is all about just working an algorithm until it cracks. Maybe there are some people who have more creative solution methods, but good notation and brute-force works pretty well (and is pretty boring). Not stimulating the creative part of the brain.
posted by thedevildancedlightly at 12:12 AM on May 11, 2005

Brute force is completely missing the point - it's a little like claiming that recreational lockpicking is easy, because you can always smash the lock open with a hammer. To do Sudoko properly, you should be absolutely, positively assured through logical deduction that each and every number can be in one position and one position only before you place it. A "let's stick a '3' there and see how it pans out" approach is like kicking the door off its hinges.
posted by obiwanwasabi at 3:53 AM on May 11, 2005

If you're finding them too easy, then the puzzles are too easy. Try the Times on Thursday and Friday, when they are rated as "Fiendish". I used to think there was a simple deterministic way to solve these, but a few of the Fiendish puzzles have taught me that sometimes you have to be a little bit cleverer than that.

My name is salmacis and I am a Sudoku addict.
posted by salmacis at 3:59 AM on May 11, 2005

From another addict:

All the free sudoku you can shake a stick at. Japanese page, but a breeze to navigate.
posted by Jeanne at 4:40 AM on May 11, 2005

This has a similar feel to nonograms.
posted by skryche at 5:10 AM on May 11, 2005

Cure you, insomnia_lj! I just tried one. I'm just about to print a heep more to play for my bus journeys and at home. Addictive.
posted by nthdegx at 6:26 AM on May 11, 2005

I am so glad for these links. I saw many people doing these puzzles on the train in Japan, but I never figured out by watching what the goal was. I thought it was some sort of magic squares thing.
posted by bashos_frog at 6:52 AM on May 11, 2005

To do Sudoko properly, you should be absolutely, positively assured through logical deduction that each and every number can be in one position and one position only before you place it.

It seems as if it's really important to solve them with ink (instead of pencil) to get the greatest challenge. Interesting.
posted by Prospero at 7:11 AM on May 11, 2005

C'mon... give it a try. It's only *one* little puzzle. (Heh, heh.)

You fiend! Damn you!
posted by hardcode at 7:45 AM on May 11, 2005

Not stimulating the creative part of the brain.

Hmm. I'm not sure about that. The hard ones *are* hard. And if you're doing them per Prospero's instructions, it's a bit different than trying several possible solutions.

I guess that's not really "creative," but it's still decent exercise.
posted by mrgrimm at 8:21 AM on May 11, 2005

A "let's stick a '3' there and see how it pans out" approach is like kicking the door off its hinges.

But for the intermediate/advanced cases you do need to run through the possibilities for some because they don't all simplify down - you can do it through notation or by actually running it through, but it's impossible to get them all by pure deduction without running some tests.
posted by thedevildancedlightly at 11:04 AM on May 11, 2005

but it's impossible to get them all by pure deduction without running some tests.

I've never had to resort to that, even for the fiendish ones. You have to narrow the possibilities down for individual squares, but you never have to say "assume this is a 3..."
posted by salmacis at 11:56 AM on May 11, 2005

skryche, I loves me the nonograms! I didn't know that's what they were called, however.
posted by papercake at 12:17 PM on May 11, 2005

I've never had to resort to that, even for the fiendish ones. You have to narrow the possibilities down for individual squares, but you never have to say "assume this is a 3..."


I don't know appropriate terminology, but you're correct that in the vast majority of cases you can rule out all possibilities by directly writing them in, but there are some where the propagation of a bad number leads to problems downstream and that's the only way to sort them out. Wish I had a link or more theory. Or maybe I just didn't do a good job eliminating possibilities completely.
posted by thedevildancedlightly at 12:47 PM on May 11, 2005

I work on puzzles from the Dell Logic Puzzles periodicals quite often. (You can get these in just about any magazine rack.)

They have this puzzle (Su Doku), which I found fairly easy. But they also have some which are infinitely more challenging: Cross Sums and Figure Logics. Check them out if you get bored with these simple number grid puzzles.
posted by TreeHugger at 1:15 PM on May 11, 2005

The 9x9 ones are rarely super-challenging for me, but I find that 16x16 ones are *killers*.
posted by antimony at 11:12 PM on May 11, 2005

Treehugger, Su Doku can be made trivially easy or fucking bastard hard, or anywhere in between. Just because the Su Doku in the Dell Logic Puzzles is easy, don't assume that Su Doku in general are easy.
posted by salmacis at 12:57 AM on May 12, 2005

I did about 10 yesterday. Hardest one took an hour, easiest 25 minutes (all fiendish). An easy one took 17 minutes.

With proper notation it's pretty easy, though you have to make deductive leaps at certain points
posted by flippant at 2:08 AM on May 12, 2005

What kind of notation do people use? I also run into situations where I can only see "postulate then prove contradiction" as the way forward. Circumstances probably make a difference; as I do them in the pub with only a pen handy, everything has to be done mentally. But I assume there are techniques involving preliminary labelling of squares?
posted by raygirvan at 5:53 AM on May 12, 2005

Nice online version (free) here. A new puzzle every day, and it shows you if you put in anything that is "impossible", ie the number has already been used in that row, column or square. I still haven't had the time to finish one though. So addictive.
posted by cushie at 4:22 AM on May 26, 2005