[Haskell-cafe] Sudoku Solver
daniel.is.fischer at web.de
Mon Aug 6 20:38:00 EDT 2007
Am Montag, 6. August 2007 15:07 schrieb Adrian Neumann:
> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: RIPEMD160
> I wrote a brute-force sudoku solver. It takes a [[Int]] and spits out
> the first solution it finds.
> Why is it, that
> is solved instantly, but when I remove just one number my program takes
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)
| done f = return $ Just f
-- | isFull f= play a
| otherwise = do printField f
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
That'll be still slow, but should finish before the gnab gib.
> - -- 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.
 Douglas Adams, The Restaurant at the end of the Universe
More information about the Haskell-Cafe