[Haskell-beginners] suggestions for optimizing sudoku solver

[Lyndon Maydwell]

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.
>> (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
>
> _______________________________________________
> Beginners mailing list
> Beginners at haskell.org
> http://www.haskell.org/mailman/listinfo/beginners