[Haskell-cafe] Sudoku Solver
-BEGIN PGP SIGNED MESSAGE- Hash: RIPEMD160 Hi, I wrote a brute-force sudoku solver. It takes a [[Int]] and spits out the first solution it finds. Why is it, that [0,0,0,7,0,6,9,0,0] [9,0,0,0,0,4,7,0,0] [7,0,0,0,0,0,4,0,0] [0,2,7,0,3,5,8,0,0] [6,9,5,8,2,0,0,0,0] [0,8,0,0,0,0,5,0,0] [0,3,0,0,0,0,0,0,0] [8,7,0,9,0,0,0,0,0] [0,0,0,0,0,0,0,0,0] is solved instantly, but when I remove just one number my program takes forever? === import Array import List import System type Field = Array Int (Array Int Int) isEmpty :: Int -> Bool isEmpty = (==) 0 done :: Field -> Bool done a = isFull a && checkField a isFull::Field -> Bool isFull a = notElem (0) $ (concat.(map elems).elems) a readField :: [[Int]]->Field readField = (listArray (1,9).map (listArray (1,9))) checkField :: Field -> Bool checkField a = check (rows a) && check (columns a) && check (squares a) where check b = and $ ((map ((==1).length)).concat.(map group).clean) b clean = map (dropWhile isEmpty.sort) columns::Field -> [[Int]] columns a = [[a!i!j|i<-[1..9]]|j<-[1..9]] rows :: Field -> [[Int]] rows a = [[a!i!j|j<-[1..9]]|i<-[1..9]] squares :: Field -> [[Int]] squares a = [[a!(i+n)!(j+m)|i<-[1..3],j<-[1..3]] |n<-[0,3,6],m<-[0,3,6]] - -- creates a list of all allowed entries genMoves :: Field -> [Field] genMoves a = concat [update a i j|i<-[1..9],j<-[1..9],isEmpty (a!i!j)] where update b i j= [b //[(i,b!i //[(j,x)])]|x<-[1..9], checkField (b //[(i,b!i //[(j,x)])])] play :: [Field] -> Maybe Field play (f:a) | done f= Just f | isFull f= play a | otherwise = play ((genMoves f)++a) play [] = Nothing main :: IO () main = do x <- getArgs let field = read (x!!0) :: [[Int]] let erg=play [readField field] case erg of Just a -> putStrLn $ concat $ map ((++"\n").show) (rows a) Nothing -> putStrLn "Es gibt keine Loesung" -BEGIN PGP SIGNATURE- Version: GnuPG v1.4.7 (MingW32) Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org iD8DBQFGtx0r11V8mqIQMRsRA7P5AJ9lG3mF3fHpUiyOqCeRVOOEGozp1wCeI80C RfD/U5y+yEgF0fe+kRwDbUI= =Ngss -END PGP SIGNATURE- ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Sudoku Solver
Note that the "official" way to solve sudoku is to use "dancing links", but I guess you are creating a naive implementation precisely as a base-line against which to measure other implementations? ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Sudoku Solver
Hi, Am Montag, 6. August 2007 15:07 schrieb Adrian Neumann: > -BEGIN PGP SIGNED MESSAGE- > Hash: RIPEMD160 > > Hi, > > I wrote a brute-force sudoku solver. It takes a [[Int]] and spits out > the first solution it finds. > Why is it, that > > [0,0,0,7,0,6,9,0,0] > [9,0,0,0,0,4,7,0,0] > [7,0,0,0,0,0,4,0,0] > [0,2,7,0,3,5,8,0,0] > [6,9,5,8,2,0,0,0,0] > [0,8,0,0,0,0,5,0,0] > [0,3,0,0,0,0,0,0,0] > [8,7,0,9,0,0,0,0,0] > [0,0,0,0,0,0,0,0,0] > > is solved instantly, but when I remove just one number my program takes > forever? > Short answer: because of the enormous number of possibilities to check. You were just incredibly lucky: with the grid above, you needn't backtrack. The problem is genMoves, it produces too many Fields. Point 1: If for, say, the first empty cell, there are no possibilities, you still try out all possibilities for the other empty cells before you backtrack, that's bound to take very long. Point 2: Even if you take care of 1, you have to do it right. Say in one row you have three empty cells with only one or two possibilities altogether. Then it's futile and very time consuming to tinker with the later rows before backtracking. (To see what I mean, make play an IO-action and let it print out the field to be updated, like play :: [Field] -> IO (Maybe Field) play (f:a) | done f = return $ Just f -- | isFull f= play a | otherwise = do printField f getLine play ((genMoves f)++a) play [] = return Nothing ) A solution is to only consider the first empty cell: genMoves a = concat $ take 1 [update a i j|i<-[1..9],j<-[1..9],isEmpty (a!i!j)] That'll be still slow, but should finish before the gnab gib[1]. > - -- creates a list of all allowed entries > genMoves :: Field -> [Field] > genMoves a = concat [update a i j|i<-[1..9],j<-[1..9],isEmpty (a!i!j)] > where update b i j= [b //[(i,b!i //[(j,x)])]|x<-[1..9], checkField (b > //[(i,b!i //[(j,x)])])] > Another thing, I think, it'd look better if You used type Field = Array (Int,Int) Int. Cheers, Daniel [1] Douglas Adams, The Restaurant at the end of the Universe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Sudoku Solver
On 8/7/07, Hugh Perkins <[EMAIL PROTECTED]> wrote: > Note that the "official" way to solve sudoku is to use "dancing links", but > I guess you are creating a naive implementation precisely as a base-line > against which to measure other implementations? > Well, Dancing Links (DLX) is just a data structure + few techniques to help with the backtrack, after modeling Sudoku as a contraint satisfaction problem. You can write a backtracking algorithm that is at least as fast as DLX :-) -- Vimal ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Sudoku Solver
j.vimal: > On 8/7/07, Hugh Perkins <[EMAIL PROTECTED]> wrote: > > Note that the "official" way to solve sudoku is to use "dancing links", but > > I guess you are creating a naive implementation precisely as a base-line > > against which to measure other implementations? > > > Well, Dancing Links (DLX) is just a data structure + few techniques > to help with the backtrack, after modeling Sudoku as a contraint > satisfaction problem. > > You can write a backtracking algorithm that is at least as fast as DLX :-) See also, http://haskell.org/haskellwiki/Sudoku -- Don ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Sudoku Solver
On 8/7/07, Donald Bruce Stewart <[EMAIL PROTECTED]> wrote: > > See also, > > http://haskell.org/haskellwiki/Sudoku > > -- Don > Just out of ... errr curiosity... which of those implementations is the fastest? ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Sudoku Solver
hughperkins: > >On 8/7/07, Donald Bruce Stewart <[EMAIL PROTECTED]> >wrote: > > See also, > [2]http://haskell.org/haskellwiki/Sudoku > -- Don > >Just out of ... errr curiosity... which of those >implementations is the fastest? > No idea. You could compile them all with -O2, run them on a set of puzzles, and produce a table of results :-) I'm a little surprised no one's tried a parallel solution yet, actually. We've got an SMP runtime for a reason, people! -- Don ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Sudoku Solver
On 8/7/07, Donald Bruce Stewart <[EMAIL PROTECTED]> wrote: > > > No idea. You could compile them all with -O2, run them on a set of > puzzles, and produce a table of results :-) Well I could, but I wont ;-) If you had to guess which one is fastest which one would you guess? I'm a little surprised no one's tried a parallel solution yet, actually. > We've got an SMP runtime for a reason, people! > Funny that you should mention that, this was actually one of the Topcoder marathon match contests for multithreading: http://www.topcoder.com/longcontest/?module=ViewProblemStatement&compid=5624&rd=9892 (you'll need to login to see the problem statement, but basically it's Sudoku, on a 16-core Xeon (I think)) ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Sudoku Solver
I am working on a parallel brute-force solver, which will be tested on 25x25 puzzles (my current serial solver requires less than 1 second for the most difficult 9x9 puzzles I've been able to find; while I haven't tried it on 16x16 puzzles on one of the machines in the Brooklyn College Metis cluster, extrapolation from another machine indicates that 16x16 puzzles will take 15-20 minutes; the 25x25 test case I have requires about a week on a cluster machine). Unfortunately, we have a lot of preparatory work to do, so it will be a while before I have any results from a puzzle solver. The parallel work will be done on our parallel version of release 5 Haskell. Murray Gross Brooklyn College On Tue, 7 Aug 2007, Donald Bruce Stewart wrote: hughperkins: On 8/7/07, Donald Bruce Stewart <[EMAIL PROTECTED]> wrote: See also, [2]http://haskell.org/haskellwiki/Sudoku -- Don Just out of ... errr curiosity... which of those implementations is the fastest? No idea. You could compile them all with -O2, run them on a set of puzzles, and produce a table of results :-) I'm a little surprised no one's tried a parallel solution yet, actually. We've got an SMP runtime for a reason, people! -- Don ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Sudoku Solver
On 8/7/07, Murray Gross <[EMAIL PROTECTED]> wrote: > > I am working on a parallel brute-force solver, which will be tested on > 25x25 puzzles (my current serial solver requires less than 1 second for > the most difficult 9x9 puzzles I've been able to find; while I haven't > tried it on 16x16 puzzles on one of the machines in the Brooklyn College > Metis cluster, extrapolation from another machine indicates that 16x16 > puzzles will take 15-20 minutes; the 25x25 test case I have requires about > a week on a cluster machine). > Question: what do you mean by, for example 25x25? Do you mean grids with a total length of 25 on each side, eg: 21 13 4 19 18 17 22 1 6 24 10 11 8 14 12 2 16 23 7 15 25 20 3 5 9 1 16 6 5 10 14 25 2 8 15 23 7 24 21 13 20 3 17 11 9 19 4 18 22 12 3 2 17 9 11 4 18 7 5 12 16 19 25 20 6 22 13 21 24 10 15 14 8 23 1 23 20 25 12 15 11 16 13 19 3 5 9 1 17 22 14 4 18 8 6 7 2 10 21 24 7 14 8 24 22 23 20 9 21 10 4 2 18 15 3 19 12 1 25 5 6 17 16 11 13 18 5 16 11 4 25 23 6 13 1 21 12 10 24 8 15 20 14 3 22 17 9 2 19 7 17 10 22 8 23 15 7 21 20 4 3 6 2 1 19 25 9 5 12 18 11 13 24 16 14 12 19 13 2 6 3 10 14 24 17 7 20 9 11 4 23 1 8 16 21 22 5 25 15 18 15 9 14 20 3 12 8 19 16 5 22 25 17 23 18 11 24 13 2 7 21 6 1 4 10 25 7 1 21 24 2 9 22 11 18 15 5 14 13 16 10 6 19 4 17 23 8 12 3 20 2 17 23 3 19 8 6 12 10 20 14 18 16 25 24 9 21 15 1 4 13 22 11 7 5 13 24 15 1 20 19 21 23 4 7 6 17 5 2 11 16 18 22 10 3 9 12 14 8 25 9 22 12 16 21 1 13 17 18 25 19 8 15 4 7 5 14 2 20 11 24 3 23 10 6 8 6 7 10 14 16 5 3 22 11 12 23 21 9 20 17 25 24 13 19 4 18 15 1 2 11 18 5 4 25 24 2 15 9 14 13 22 3 10 1 8 23 7 6 12 20 16 19 17 21 16 15 19 13 12 10 3 4 17 6 20 21 23 18 25 24 7 9 14 8 1 11 5 2 22 14 21 18 22 9 7 11 16 23 2 8 1 6 12 5 3 19 20 15 13 10 24 17 25 4 6 8 11 7 2 5 1 24 25 9 17 14 13 16 15 18 10 4 22 23 12 19 21 20 3 5 4 20 25 1 13 15 8 12 22 11 24 19 3 10 6 17 16 21 2 18 7 9 14 23 24 3 10 23 17 18 19 20 14 21 9 4 22 7 2 1 11 12 5 25 8 15 13 6 16 10 12 9 6 5 22 14 18 7 13 25 16 11 8 21 4 15 3 17 1 2 23 20 24 19 19 25 24 18 16 20 17 5 2 8 1 10 4 6 23 12 22 11 9 14 3 21 7 13 15 22 23 3 17 7 6 12 25 15 19 2 13 20 5 14 21 8 10 18 24 16 1 4 9 11 4 11 2 15 8 21 24 10 1 16 18 3 7 19 9 13 5 6 23 20 14 25 22 12 17 20 1 21 14 13 9 4 11 3 23 24 15 12 22 17 7 2 25 19 16 5 10 6 18 8 ... or do you mean grids where each subgrid is 25x25, and the entire grid is 625 x 625? ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Sudoku Solver
On 8/7/07, Hugh Perkins <[EMAIL PROTECTED]> wrote: > > Question: what do you mean by, for example 25x25? Do you mean grids with > a total length of 25 on each side, eg: > (because on my super-dooper 1.66GHz Celeron, generating 10 random 25x25 grids such as the one above takes about 1.01 seconds; solving an actual puzzle should be faster because the solution space is more tightly constrained?) ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Sudoku Solver
Yes, by 25x25 puzzles I mean sudoku puzzles with 25 cells on each side, with the smaller squares being 5x5 (i.e., we need to construct rows with the numbers 1-25, and the smaller squares must each contain all of the numbers 1-25). Murray Gross Brooklyn College On Tue, 7 Aug 2007, Hugh Perkins wrote: On 8/7/07, Hugh Perkins <[EMAIL PROTECTED]> wrote: Question: what do you mean by, for example 25x25? Do you mean grids with a total length of 25 on each side, eg: (because on my super-dooper 1.66GHz Celeron, generating 10 random 25x25 grids such as the one above takes about 1.01 seconds; solving an actual puzzle should be faster because the solution space is more tightly constrained?) ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Sudoku Solver
G'day all. Quoting Vimal <[EMAIL PROTECTED]>: > Well, Dancing Links (DLX) is just a data structure + few techniques > to help with the backtrack, after modeling Sudoku as a contraint > satisfaction problem. DLX is one realisation of an algorithm which works on boolean matrices. It's a pointer-based backtracking algorithm with explicit "undo", so that's arguably not the most appropriate realisation in a declarative language, where undo should be close to free. Just for fun, I tried implementing the exact cover algorithm using a more Haskell-esque data realisation. The bit matrix is represented as a pair of maps: one from column to list of rows, and one from rows to list of columns. The first map (column to list of rows) is implemented as a priority search queue keyed on the number of "ones" in each column. This allows fast selection of the smallest column. http://andrew.bromage.org/darcs/sudoku/ I don't claim that it's fast. I didn't spend a lot of time on it. Cheers, Andrew Bromage ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Sudoku Solver
I'm a little surprised no one's tried a parallel solution yet, actually. We've got an SMP runtime for a reason, people! I hacked up a parallel version of Richard Bird's function pearl solver: http://www.haskell.org/sitewiki/images/1/12/SudokuWss.hs It not really optimized, but there are a few neat tricks there. Rather than prune the search space by rows, boxes, and columns sequentially, it represents the sudoku grid by a [[TVar [Int]]], where every cell has a TVar [Int] corresponding to the list of possible integers that would 'fit' in that cell. When the search space is pruned, we can fork off separate threads to prune by columns, rows, and boxes -- the joy of STM! Wouter ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Sudoku Solver
On Saturday 18 August 2007 19:05:04 Wouter Swierstra wrote: > I hacked up a parallel version of Richard Bird's function pearl solver: > > http://www.haskell.org/sitewiki/images/1/12/SudokuWss.hs > > It not really optimized, but there are a few neat tricks there. > Rather than prune the search space by rows, boxes, and columns > sequentially, it represents the sudoku grid by a [[TVar [Int]]], > where every cell has a TVar [Int] corresponding to the list of > possible integers that would 'fit' in that cell. When the search > space is pruned, we can fork off separate threads to prune by > columns, rows, and boxes -- the joy of STM! Is it possible to write a shorter Haskell version, perhaps along the lines of this OCaml: let invalid (i, j) (i', j') = i=i' || j=j' || i/n=i'/n && j/n=j'/n let select p n p' ns = if invalid p p' then filter ((<>) n) ns else ns let cmp (_, a) (_, b) = compare (length a) (length b) let add p n sols = sort cmp (map (fun (p', ns) -> p', select p n p' ns) sols) let rec search f sol = function | [] -> f sol | (p, ns)::sols -> iter (fun n -> search f (Map.add p n sol) (add p n sols)) ns -- Dr Jon D Harrop, Flying Frog Consultancy Ltd. OCaml for Scientists http://www.ffconsultancy.com/products/ocaml_for_scientists/?e ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
