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