[Haskell-cafe] Sudoku Solver

[Daniel Fischer]

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