Re: [Haskell-beginners] suggestions for optimizing sudoku solver

I was about to recommend Bird's solution as well. An incredibly eye-opening pearl. I believe that he sticks with lists as the data-structure the entire way through, so that should give an indication that acceptable performance can be achieved without requiring mutable data-structures, etc. The only issue with this approach is that unless you're aware of other invariants available you'll just end up copying Bird's solution... I certainly wasn't aware of some of the invariants used in the paper, and can't think of any others. On Wed, Jan 4, 2012 at 11:01 AM, KC wrote:

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 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@haskell.org http://www.haskell.org/mailman/listinfo/beginners

-- -- Regards, KC

_______________________________________________ Beginners mailing list Beginners@haskell.org http://www.haskell.org/mailman/listinfo/beginners