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