From "Pearls of Functional Algorithm Design", Richard Bird, 2010
"Assuming about a half of the 81 entries are fixed initially (a
generous estimate), there are about 9^40 grids to check."
The main value of the book is that Bird shows how to design by
calculation (how equational reasoning) can be used to solve problems
and then the efficiency of the solution can be improved.
On Sun, Jan 1, 2012 at 7:27 PM, Peter Hall
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