[Haskell-cafe] Sudoku Solver

[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?

===

import Array
import List
import System

type Field = Array Int (Array Int Int)

isEmpty :: Int -> Bool
isEmpty = (==) 0

done :: Field -> Bool
done a = isFull a && checkField a

isFull::Field -> Bool
isFull a = notElem (0) $ (concat.(map elems).elems) a

readField :: [[Int]]->Field
readField = (listArray (1,9).map (listArray (1,9)))

checkField :: Field -> Bool
checkField a =  check (rows a) &&  check (columns a) && check (squares 	a)
	where
		check b = and $ ((map ((==1).length)).concat.(map group).clean) b
		clean =  map (dropWhile isEmpty.sort)

columns::Field -> [[Int]]
columns a = [[a!i!j|i<-[1..9]]|j<-[1..9]]

rows :: Field -> [[Int]]
rows a = [[a!i!j|j<-[1..9]]|i<-[1..9]]

squares :: Field -> [[Int]]
squares a = [[a!(i+n)!(j+m)|i<-[1..3],j<-[1..3]] |n<-[0,3,6],m<-[0,3,6]]


- -- 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)])])]

play :: [Field] -> Maybe Field
play (f:a)
	| done f= Just f
	| isFull f= play a
	| otherwise = play ((genMoves f)++a)
play [] = Nothing

main :: IO ()
main = do
		  x <- getArgs
		  let field = read (x!!0) :: [[Int]]
		  let erg=play [readField field]
		  case erg of
			Just a -> putStrLn $ concat $ map ((++"\n").show) (rows a)
			Nothing -> putStrLn "Es gibt keine Loesung"
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.7 (MingW32)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org

iD8DBQFGtx0r11V8mqIQMRsRA7P5AJ9lG3mF3fHpUiyOqCeRVOOEGozp1wCeI80C
RfD/U5y+yEgF0fe+kRwDbUI=
=Ngss
-----END PGP SIGNATURE-----