[Haskell-beginners] suggestions for optimizing sudoku solver

[KC]

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

search m
  | 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.
> (https://github.com/peterjoel/sudoku/blob/master/src/Sudoku.hs)
> 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?
>
> Peter
>
> _______________________________________________
> Beginners mailing list
> Beginners at haskell.org
> http://www.haskell.org/mailman/listinfo/beginners



-- 
--
Regards,
KC