[Haskell-beginners] suggestions for optimizing sudoku solver
maydwell at gmail.com
Wed Jan 4 04:25:47 CET 2012
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 <kc1956 at gmail.com> 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 <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
> Beginners mailing list
> Beginners at haskell.org
More information about the Beginners