Haskell Sudoku solver

http://www.cs.tufts.edu/~nr/comp150fp/archive/richard-bird/sudoku.pdf

by 10ren • 17 years ago

16 7 17 years ago

cs.tufts.edu

simonista• 17 years ago

Really cool to see how this would be done in Haskell, thanks for the link! I just read through so some of it went over my but seeing how they layout the mathematical logic was insightful. Here's another great take on the problem (in python) for those who may not have seen it: http://norvig.com/sudoku.html

vito3• 17 years ago

I wrote a Sudoku puzzle solver in Haskell as practice a while ago, if anyone's interested the source (including tests and a description of the algorithm) is here: http://github.com/vito/sudoku.hs

j2d2• 17 years ago

That sure is a lot of code given Haskell's concise reputation. I don't know Haskell. Would you mind explaining all what all the logic is doing?

vito3• 17 years ago

I don't think it's too much code. Sudoku solving is nontrivial, and this is a complete application consisting of all of the IO handling, pretty printing, tests, guessing, etc. The actual solving is roughly 2/3rds of this source.

Haskell is consise in the sense that you can accomplish a lot with small definitions - as you'll note, many of those functions are one-liners and exist solely to give meaning/value to something that is otherwise unclear. Even if the definition is used only once (or never used at all), it's well worth doing just for clarity and reusability's sake.

That being said, there are a few warts in there - basically anything to do with the "boxes" I had to do a lot of repetitive ugly lines. I could probably have changed the structure of the grid to denote boxes, but this was a learning experience.

(edit: re: the logic and everything, it's all explained at the bottom of the readme though I'd be happy to expound upon it)

pshc• 17 years ago

Coincidentally, I had to write one last week as an assignment. It's kind of messy because I had to implement several heuristics for the backtracking search. http://pastebin.com/f4c385e8d

g__• 17 years ago

and $ map can be shortened to all in many places.

I'd use pointless style more: row = (!!)

The function valid has a lot of repetition, maybe the repeating part can be abstracted of?

Instead of length possible > 0, you can use not $ null possible. This is faster, since it doesn't go through the whole list.

Instead of pattern matching on Maybe (tile), you can use Prelude's maybe.

vito3• 17 years ago

Yep. As I said, this is all pretty old and was done as a learning experience. Thanks though. :)

Haskell Sudoku solver

Related Stories