Send Beginners mailing list submissions to beginners@haskell.org To subscribe or unsubscribe via the World Wide Web, visit http://www.haskell.org/mailman/listinfo/beginners or, via email, send a message with subject or body 'help' to beginners-requ...@haskell.org
You can reach the person managing the list at beginners-ow...@haskell.org When replying, please edit your Subject line so it is more specific than "Re: Contents of Beginners digest..." Today's Topics: 1. Re: suggestions for optimizing sudoku solver (Peter Hall) ---------------------------------------------------------------------- Message: 1 Date: Thu, 5 Jan 2012 02:37:58 +0000 From: Peter Hall <peter.h...@memorphic.com> Subject: Re: [Haskell-beginners] suggestions for optimizing sudoku solver To: KC <kc1...@gmail.com> Cc: beginners@haskell.org Message-ID: <caa6hak7ylbutqrmgj22ogjqj3r+_8dfp50ldys7xvdq8ndi...@mail.gmail.com> Content-Type: text/plain; charset=ISO-8859-1 Thanks, I have that book coming any day now :) In the meantime, I started again and tried to avoid accessing the full List-of-Lists inside the algorithm and to make it more linear. So now, I'm starting with a list of hints (ie solved cells) and a list of unsolved cells, each with an index for row, column and block. Each recursion attempts to move a cell from the unresolved list to the hints list. https://github.com/peterjoel/sudoku/blob/master/src/Sudoku/Solver2.hs The result is actually really simple, and far faster than I had before. There are some other functions wrapping it, but this is the meat of it: solveNext :: [((Int,Int,Int),Int)] -> [(Int,Int,Int)] -> Maybe [((Int,Int,Int),Int)] solveNext hints [] = Just hints solveNext hints (r@(x,y,b):rem) = case catMaybes $ map try remaining of [] -> Nothing p:_ -> Just p where try v = solveNext ((r,v):hints) rem remaining = [1..9] \\ (map snd . filter isNeighbour) hints isNeighbour ((x',y',b'),_) = x==x' || y==y' || b==b' For the two "hardest" grids (hard4.txt and hard5.txt) that were taking my first solution 17-18 seconds to solve, it's now doing it in around 0.004 seconds, which is about 4000x faster! Strangely, some of the easier ones are now taking slightly longer. For example this one: https://github.com/peterjoel/sudoku/blob/master/data/hard2.txt , took 0.18s with Solver1, but 0.65s with Solver2. Still within reason though. Peter On Wed, Jan 4, 2012 at 3:01 AM, KC <kc1...@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.h...@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@haskell.org >> http://www.haskell.org/mailman/listinfo/beginners > > > > -- > -- > Regards, > KC ------------------------------ _______________________________________________ Beginners mailing list Beginners@haskell.org http://www.haskell.org/mailman/listinfo/beginners End of Beginners Digest, Vol 43, Issue 7 ****************************************