Haskell Sudoku solver(cs.tufts.edu)
cs.tufts.edu
Haskell Sudoku solver
http://www.cs.tufts.edu/~nr/comp150fp/archive/richard-bird/sudoku.pdf
2 comments
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
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
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
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.
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.
Yep. As I said, this is all pretty old and was done as a learning experience. Thanks though. :)
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?
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)
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)