Sudoku Solving • Hacker News Board

Re: Sudoku Solving

#51

Post by jules » Sat, Mar 26, 2011, 7:58 PM UTC

ondrasej wrote: post #47

jules wrote: post #30

Earlier quoted context omitted.

> I'd be very interested to see what an algorithm that solves any valid sudoku puzzle looks like. You might be interested in the article linked to by this post.

The code in the post is based on depth-first search, which basically is a trial and error approach. A well implemented and effective one thanks to constraint propagation, but it is still trial and error. And there are cases, in which backtracking (trial and error) is necessary - at least one of them is documented in the post (the puzzle "hard1" that took 188 seconds).

There is no meaningful difference between trial and error and without trial and error. It makes this no less of an algorithm.

Re: Sudoku Solving

#52

Post by bobfunk » Sat, Mar 26, 2011, 9:20 PM UTC

xtacy wrote: post #40

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.

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

Re: Sudoku Solving

#53

Post by jmelloy » Sat, Mar 26, 2011, 10:03 PM UTC

bobfunk wrote: post #52

xtacy wrote: post #40

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.

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…

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.