Sudoku Solving

by nu2ycombinator • 15 years ago

111 51 15 years ago

jonah2• 15 years ago

He could have used Mechanical Turk to solve them. ;)

Growing up, we had a favorite game. That is until my sister solved it in that going first you could always win. It wasn't as fun after that.

mryall• 15 years ago

http://xkcd.com/832/

jonah2• 15 years ago

I like that one.

Ours was a different game: Mühle. Also Mill or Nine Men's Morris.

I just discovered that Ralph Gasser solved it in 1996 using retrograde analysis and an 18-ply alpha- beta search. [1] Becoming "the first non-trivial game to be solved that does not seem to benefit from knowledge-based methods."

[1] http://library.msri.org/books/Book29/files/gasser.pdf

wallflower• 15 years ago

Reminds me of:

http://blog.jgc.org/2010/01/more-fun-with-toys-ikea-lillabo-...

muhuk• 15 years ago

  Why did I do this? As computer security expert Ben Laurie
  has stated, Sudoku is "a denial of service attack on human
  intellect". My wife was infected by the virus, and I wanted
  to convince her that the problem had been solved and didn't
  need any more of her time.

Very true.

jules4• 15 years ago

Now lets go back to watching TV!

adrianN2• 15 years ago

Nah, that's a solved problem. I let my VCR watch TV for me. Now if I had an electric monk, I could stop believing in things.

mberning• 15 years ago

I remember doing something very similar in college. My first cut used a hideous object model, but my second go at it used a 3 dimensional matrix to track all of the data and was much faster and space efficient.

The "Why?" at the end of the article pretty much sums up why I can't play most board games and puzzles. Once you 'solve' sudoku, chess, connect 6, ect. it really takes the fun out of it, even if your brain doesn't calculate the solution as quick as your code.

iki23• 15 years ago

Doesn't apply to chess imho. I still keep discovering different views of the game on occasional plays. The standard algorithm takes too much time, so you have to find out how to see what's important.

adrianN2• 15 years ago

I played chess for a while in a chess club. But to become any good you need to memorize a lot of positions to be able to efficiently recognize good moves. Playing creatively to have fun almost always leads to defeat.

spacemanaki• 15 years ago

I think you're being a bit unfair to chess, but anyway you can still play Go. I think it's far from "solved" as amateurs beat computer programs very often, as I understand.

jws3• 15 years ago

Sadly it is a backtracking algorithm which is not proper Sudoku solving technique. (Opinions vary on the topic.)

crux_8• 15 years ago

I'm curious... what would be the 'proper' technique?

nazgulnarsil• 15 years ago

solving without trial and error at all.

YuriNiyazov2• 15 years ago

Can someone explain the Ben Laurie quote? I know what Sudoku is, and I know what a DOS attack is. I don't see the connection between the two.

JoshCole• 15 years ago

Sudoku has a human using their mind to solve things which don't need to be solved. A denial of service attack leaves a computer trying to handle things which don't need to be handled. So they have something trying to deal with things that don't need to be dealt with.

YuriNiyazov2• 15 years ago

Thank you.

isak2• 15 years ago

I wrote one in C# a while ago:

http://isaksky.wordpress.com/2010/10/30/objected-oriented-so...

gumbo• 15 years ago

I did the same, need to dig into my back up hard drive to find it. Maybe i'm going to expose a REST api for generating sudokus. Do you think this might be interesting?

"Did you know that in order to generate a sudoku you need first to solve it?"

roryokane• 15 years ago

Norvig tries to test his program against the hardest puzzle he can find, but only tries to find this hard puzzle by generating random ones. The program Sudoku Susser (http://www.madoverlord.com/projects/sudoku.t) actually comes with “the hardest sudoku in the world”, which I think the author of that program has proven somehow, so Norvig should try his program on that.

Sudoku Susser can solve sudoku puzzles not only the brute-force way shown in the article, but also using “human” reasoning, and show you all the steps.

silentbicycle• 15 years ago

I wouldn't call constraint propagation "brute-force". It isn't enumerating every combination of values and backtracking (as either a non-contstraint Prolog program or a C program with up to 81 nested for-loops would). Rather, it's removing every possibility that has already been canceled out (constraint propagation), then saving undo information, making one guess, and seeing if that sets off another chain reaction or reaches a solution.

He acknowledges the possibility of using more "reasoning" in the article, but dismisses it:

"We could try to code more sophisticated strategies. For example, the naked twins strategy looks for two squares in the same unit that both have the same two possible digits. [...] Coding up strategies like this is a possible route, but would require hundreds of lines of code (there are dozens of these strategies), and we'd never be sure if we could solve every puzzle."

If you want to read more about constraint programming, there is an excellent overview chapter in CTM (http://www.info.ucl.ac.be/~pvr/book.html). "The Art of the Propagator" (http://dspace.mit.edu/handle/1721.1/44215) is also good, though it focuses more on arithmetic value propagation than set propagation problems like sudoku. For more advanced material, look at the clp(FD) papers by Danial Diaz (http://cri-dist.univ-paris1.fr/diaz/publications/cv-short.ht...); familiarity with Prolog terminology will be helpful.

ozataman• 15 years ago

Would be interesting to see how this fares performance-wise in comparison:

http://corp.galois.com/blog/2009/3/18/solving-sudoku-using-c...

It's a sudoku solver based on Cryptol, which is "... a language tailored for cryptographic algorithms." built on top of Haskell. The amazing this is that all you need to define is a function that checks whether a given board is solved. Cryptol does the searching for you!

jws3• 15 years ago

I find that calculating the sequence of stereo pairs for an MP3 file is much simpler and more accurate if I dispense with the human listener.

For instance, I just rendered "In the Year 2525" 593 times faster than a human can listen to it on a single thread of a core i3.

xtacy• 15 years ago

If you really want speed, then I would recommend using a good implementation of Dancing Links for solving constraint satisfaction problems. Don Knuth proposes a doubly linked list structure to speed up recursive state space exploration: www-cs-faculty.stanford.edu/~uno/papers/dancing-color.ps.gz.

bobfunk2• 15 years ago

Mentioned this below as well, but got a pretty straight forward ruby implementation of Knuths Dancing Links up at:

https://github.com/biilmann/Ruby-DLX-Sudoku-Solver

It's not hyper-fast (for speed I actually implemented it as a c-extention to ruby, but it's a long time ago and I don't think I have the code around by now) but being ruby it's fairly easy to read.

Can really recommend reading the paper on Dancing Links and playing around with the algorithm, its such a great feeling once you start visualizing how the linked list trick works :)

jmelloy• 15 years ago

Dancing Links is definitely a fun algorithm to implement. I wrote one in Python a while back and included an option to generate graphs as it went through the recursion tree. I put up a quick page at http://cavernum.net/dlsudoku/ demonstrating them.

atuladhar• 15 years ago

I wrote one in JavaScript a long time ago, again using a simple backtracking algorithm.

http://www.amrittuladhar.com/projects/sudokusolver/

EDIT: Just realized the "load puzzle" feature doesn't seem to work on Chrome, but it does in other browsers.

akivabamberger• 15 years ago

The answer is just 3 words: depth first search. I don't get why such a tedious article was written for such a simple, common, and obvious solution.

alienDeveloper• 15 years ago

http://news.ycombinator.com/item?id=2374763

another php version

Sudoku Solving

Related Stories