[Haskell-beginners] suggestions for optimizing sudoku solver
kc1956 at gmail.com
Wed Jan 4 04:01:56 CET 2012
Bird begins with the specification (without regard to efficiency):
solve = filter valid . expand . choices
And ends up with this third version of solve
solve = search . choices
| not (safe m) = 
| complete m' = [map (map head) m']
| otherwise = concat (map search (expand1 m'))
| where m' = prune m
Note: some functions are missing
The interesting idea is how he uses equational reasoning to reach this solve.
On Sun, Jan 1, 2012 at 7:27 PM, Peter Hall <peter.hall at memorphic.com> wrote:
> I set myself a learning task of writing a sudoku solver.
> It works pretty well, but struggles with some of the harder grids.
> e.g. data/hard4.txt and data/hard5.txt take around 18 seconds to
> solve. Obviously there's a limit, but I feel like I should be able to
> make this faster.
> I think the main issue is reading/writing to the cells in the grid,
> since (!!) is O(n). Even though it never has to go beyond index 8, it
> will add up over the millions of times it has to do it. I imagine it
> could be a lot faster if I use a static, non-list data structure, but
> I was hoping to keep it a bit more flexible.
> Also, I'm struggling to get started with performance profiling. Can
> someone point me to some good resources?
> Beginners mailing list
> Beginners at haskell.org
More information about the Beginners