Minimum sudoku

July 19, 2006 11:14 AM

Minimum Sudoku. It is believed (though not proven) that the minimum number of entries in a Sudoku grid that will lead to a unique solution is 17. Gordon Royle of the University of Western Australia has collected 36,628 "minimum Sudoku" grids. Additional reading: an article in American Scientist on determining the difficulty of a Sudoku problem; Wikipedia article on the mathematics of Sudoku; the Sudoku Programmers' Forum on Sudoku mathematics.
posted by Prospero (29 comments total)

have discovered a truly marvelous proof of this, which this thread is too narrow to contain.
posted by sindark at 12:11 PM on July 19, 2006 [3 favorites]

Sudoku - the Rubik's Cube of our decade?

Seriously, I've been watching the mounting fascination with this idle pasttime with a mingling of humor and chagrin. I can't wait for the inevitability of determining intelligence by the speed at which one can solve a Sudoku puzzle...
posted by FormlessOne at 12:26 PM on July 19, 2006

Wow. It's kind of hard to argue against that.
posted by Flashman at 12:38 PM on July 19, 2006

FormlessOne, like this?
posted by monju_bosatsu at 12:40 PM on July 19, 2006

Despite enjoying the Sudoku module in Brain Age immensely, I have to agree with FormlessOne, most of the fever over Sudoku is pure fad. Witness the rise of several Sudoku knockoffs, also involving grids and given Japanese names, evidently banking on a growing perception that Japan must be filled with number puzzle geniuses.

At least Games Magazine will probably get a few extra subscriptions from all this. That publication's survival, IMO, is an absolute good.
posted by JHarris at 12:44 PM on July 19, 2006

Will Shortz on Suduko. (Was this already on MeFi?) Shortz argues that Sudoku has a secret psychological hook. While solving them, you tend to get bogged down midway—then suddenly break through, fill in the last bunch of empty boxes in a row, bang bang bang. “It gives you a satisfying feeling to be rushing at those squares,” Shortz says. “And immediately you want to do another one. That’s the key to why they are so addictive.” I personally prefer crossword puzzles as being more creative, but Soduko puzzles are somewhat seductive.
posted by caddis at 12:47 PM on July 19, 2006

Shortest known (to the author) Sudoku solvers in Ruby, Python && Perl.
posted by signal at 12:53 PM on July 19, 2006

I want to see a Sodoku solver in PostScript. That would rock. cat the incomplete puzzle to the printer and get the solution printed out. Like this baby. Or this.
posted by GuyZero at 1:02 PM on July 19, 2006

Same newyorkmetro.com article:

Less charitably, one could regard Sudoku as the lowest common denominator— a puzzle for a nation whose citizens no longer presume to have any culture in common. “I don’t want to call it a dumbing down of society,” Abby Taylor, Dell’s editor-in-chief, says delicately, but she has noticed that nonlanguage puzzles like Sudoku—or nondemanding ones like word searches—have been steadily increasing in sales, while sales of difficult crosswords remain flat.

[...] Mind you, I’m never exactly sure how Shortz really feels, because when the conversation turns to Sudoku, he never quite lights up the way he does when we discuss a nicely jam-packed grid, crackling with wit and wordsmithery. Wisely, he’s not criticizing a game that is making him rich.

Minimum solutions to LCD puzzles. Woo.
posted by pracowity at 1:23 PM on July 19, 2006

This is cool! Thanks, Prospero. I've been doing Sudoku for a while and I agree with Shortz on the "hook" thing. There is a definite rush.

I think I'll go do a crossword puzzle.
posted by rex dart, eskimo spy at 1:46 PM on July 19, 2006

Regarding the invention of Sudoku:

Who made this puzzle? In addition to being the crossword editor of the New York Times, Will Shortz is a puzzle historian, so he did detective work to find the answer. He knew that "Number Place" puzzles had appeared in Dell Magazines, and went through his collection to find the first. Dell listed no author, but the name Howard Garns always appeared in the contributor's list of any issue containing a "Number Place" puzzle. Also, Garns' name did not appear in any issue lacking a Number Place, which clinched the identification. Further research revealed that Howard Garns to be a retired architect who created the puzzle at age 74. Howard Garns died in Indianapolis in 1989, and never got a chance to see his creation as a worldwide phenomenon. (Shortz, pers. comm. 2005)

Source
posted by vacapinta at 1:51 PM on July 19, 2006

monju_bosatsu, that's only the beginning. Until this thing spawns an animated series, a bunch of spinoff toys, and a number of contests in which local media can immerse itself, Sudoku has not yet "arrived."
posted by FormlessOne at 1:53 PM on July 19, 2006

GuyZero: hells yes. I've had "Thinking in Postscript" on my "too sexy to not read, yet too time-absorbing to get serious about it" pile for months.
posted by sonofsamiam at 1:53 PM on July 19, 2006

I can't wait for the Sudoku animated series, personally. Two anime characters - one a smooth-coiffed, slightly effeminate yet deeply evil mathematician bent on world domination, the other a spunky teen male with spiky hair and a motivation based on personal loss - face off, furiously writing single digits into a kiosk developed by the United Nations to restrict the horrifying carnage to neutral ground.

Warms my heart to know you can't sell a Sudoku booster pack.
posted by FormlessOne at 1:57 PM on July 19, 2006

If they could do it to Go...

Teenage Mutant Sudoku Numbers!
posted by sonofsamiam at 2:15 PM on July 19, 2006

“It gives you a satisfying feeling to be rushing at those squares,” Shortz says. “And immediately you want to do another one. That’s the key to why they are so addictive.”

I wonder if Shortz knows that Sudoku is actually a pun on Chudoku, which means addiction in Japanese.
posted by sour cream at 2:45 PM on July 19, 2006

Warms my heart to know you can't sell a Sudoku booster pack.



posted by mhum at 2:55 PM on July 19, 2006 [4 favorites]

I find it interesting that people make the assumption that crossword puzzles require more thought or intelligence. While it could be argued that crosswords require a bit of cultural awareness it is my contention that mostly the culture you have to become aware of is that of crossword puzzles.

I've known some pretty dim people who do crosswords, and I know a couple of pretty dim people who do Sudoku. I think its a mistake to assume that either has much to do with intelligence.

As far as crosswords and intelligence go, my wife does crosswords I don't. Both of us are language oriented types with around equal interest and education in literature, current events, etc, we both like word games and obscure words [1]. Every now and then I'll peek at a crossword puzzle she's working on and I absolutely cannot figure out what word they're trying to get at with their clues, but she gets it every time. Obviously this is just a single experience, but it leads me to suspect crosswords are really just testing how deeply you've become involved in the culture of crosswords.... [2]

As for Sudoku, I've never tried it, but I can see how it would both be appealing, and draw criticism. Its hedging into the mindspace occupied by crosswords and that means crossword fans pretty much have to object to it. However, unlike crosswords it doesn't require that you become immersed in a little subculture where "Heads of Hair" is a clue for the word "MOPS", and that is going to appeal to a lot of people. There's also no denying that it'll appeal to people with small vocabularies, but hey, they've got to be entertained too, yes?

As for Sudoku being a fad, while I certainly won't say it can't be, I can't help but wonder how many people thought crosswords would be just a flash fad when they got started.

[1] Gawd as I read that it makes us out to be really boring people......

[2] Either that or Carol is a lot smarter than me.
posted by sotonohito at 3:24 PM on July 19, 2006

Nice post. I bought a Sudoko travel book to accompany me on an eight hour flight and I've since been hooked. It's a great boredom buster and I can finally say I don't hate numbers anymore.
posted by liquorice at 4:46 PM on July 19, 2006

Sudoku - the Rubik's Cube of our decade?

As for Sudoku being a fad, while I certainly won't say it can't be, I can't help but wonder how many people thought crosswords would be just a flash fad when they got started.

I think the difference between rubik's cube and crossword puzzles is that once you solve the former, you're done with it - it isn't really a genus of puzzles; it's one particular puzzle. Sure, there are variations, and the interest can be stretched by comparing speed or doing alternate solutions or whatever, but essentially, once you've figured it out, there's only so much entertainment left. Whereas crossword puzzles are really not limited in that way. I do agree that crossword puzzles in the US have a definite culture, though, and that being familiar with it is primary to being good at the puzzles. (It's a bit different in the UK where the puzzles employ less punny references, and are less intricately designed - their puzzles are more like little trivia tests. The quiz shows over there also seem to run more intellectual/ less clever than ours.)

Anyway, as to whether Sudoku is in essence one puzzle or a lifetime of puzzles is a tough one - it kinda looks like the sort of thing one might eventually 'get' enough that it won't continue to hold interest, like rubik's cube, but I've never tried it myself.

that link about the american origin of sudoku & the all the variations was interesting - thanks, vacapinta.
posted by mdn at 5:07 PM on July 19, 2006

mdn: I could almost agree with you about the possibility of sodoku having limited appeal, except for the continuing popularity of solitaire and freecell. Both games have relatively simple mechanics, and there isn't much of anything new after the first few are played, yet people (me included) play them every day.

Something purely mechanical, like rubrik's cube [1], has limited replay value because its so limited. solitaire while its essentially the same thing every time has enough variation that it keeps people coming back even after it gets easy.

I kinda suspect that sudoku will be like that.

[1] I got a rubrik's Cube when I was around 5. I solved it in a manner which would later prove to be one of those "formative moments". I used a screwdriver to pop out one of the non-corner pieces, took the whole thing apart, and put it together solved. Looking back on that that my entry into computer programming, hacking, and now the law, seems inevitable.
posted by sotonohito at 5:15 PM on July 19, 2006

I can finally say I don't hate numbers anymore

Well, that's great, except that the fact that you're placing numbers is completely irrelevant to solving the puzzle! Sudoku could just as easily be played with the letters A through I, or nine different varieties of smilies, and the puzzles would be exactly the same. Granted, you can pull out some big abstract mathematical guns to solve a given Sudoku puzzle, but the actual numbers in the puzzle are just completely incidental. That's always something that bugged me about this fad -- people think they're being mathy and working with numbers, and they ARE being sort of mathy (behind the scenes) but not in the way they think.

So yes, what I'm saying is, you should continue to hate numbers.
posted by evinrude at 5:45 PM on July 19, 2006

outside man writes: "I find it interesting that people make the assumption that crossword puzzles require more thought or intelligence. While it could be argued that crosswords require a bit of cultural awareness it is my contention that mostly the culture you have to become aware of is that of crossword puzzles."

I agree; from a year or so of near-daily puzzling I've mainly picked up some crosswordese (Melville novels, kimono sashes, that city in Germany, etc.) and managed to train myself to anticipate Shortzian lateral thinking ("found in bars" - drinks? servers? No; more likely soap, musical notes, almonds etc.)
posted by kurumi at 5:48 PM on July 19, 2006

evinrude: Thank goodness! I was just waiting for a reasonable excuse to come along so I could hop back into the "hating maths" camp. Haha
posted by liquorice at 5:51 PM on July 19, 2006

Oh no no no evinrude. There are so many people turned off from sudoku just because it involves numbers that it is a testament to the fun of the puzzle that people are willing to challenge their entrenched innumeracy to play this game. Don't let them know that 1-9 is an arbitrary assignment of possibilities; please allow them to feel more confident with the use and manipulation of numbers in this setting so that that they may confidently apply that comfort to to rest of their life. It is for the better.
posted by peeedro at 6:19 PM on July 19, 2006

walnut, thanks for the validation, always nice to find out that I'm not crazy (on that particular topic anyway).
posted by sotonohito at 6:54 PM on July 19, 2006

Solve Sudoku (Without even thinking!) - there, that should take all the fun out of it.
posted by tellurian at 7:45 PM on July 19, 2006

tellurian, as some of the commenters point out, the non-thinking approach, in addition to being rather pointless busywork rather than strategic puzzle-solving, will only work on easy to moderate puzzles. Get yourself a "difficult" or "diabolical" and you'll be staring at a grid practically filled with boxes of five or six numbers.

I think part of the value - if there is a "value" to it - of Sudoku is it makes me aware of how I decide things. I can kind of watch myself making a logical chain of decisions and see where sometimes it goes wrong, all easily rendered in numerical form.

And as for the numbers, of course it could theoretically be any set of icons, but digits 1-9 have the advantage of being a closed set where you can more easily tell which of the members of the set aren't there. In fact, if I had to come up with one benefit of being a Sudoku player it's that I can now look at 8 different digits and instantly tell you the 1 that's missing, almost literally without thinking.
posted by soyjoy at 8:14 PM on July 19, 2006

I like it. Oh.
posted by simonemarie at 9:59 PM on July 19, 2006