Daniel Fischer daniel.is.fischer at web.de
Mon Aug 6 20:38:00 EDT 2007

```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

```