module Sudoku where

import List (splitAt, (\\))

type Matrix a = [[a]]
type Board = Matrix Char
type Choices = [Char]

boardsize = 9
boxsize = 3
cellvals = "123456789"
blank = (=='.')

nodups [ ] = True
nodups (x : xs) = notElem x xs && nodups xs

rows = id

cols [xs] = [[x] | x <- xs]
cols (xs : xss) = zipWith (:) xs (cols xss)

boxs = map ungroup . ungroup . map cols . group . map group

group = groupBy boxsize

groupBy n [] = []
groupBy n xs = as : groupBy n bs
               where (as,bs) = splitAt (fromInteger n) xs

ungroup = concat

choices = map (map choose)

single [x] = True
single y = False

choose e = if blank e then cellvals else [e]

fixed = concat . filter single

blocked cm = void cm || not (safe cm)

void = any (any null)

safe cm = all (nodups . fixed) (rows cm) &&
		  all (nodups . fixed) (cols cm) &&
		  all (nodups . fixed) (boxs cm)
		  
expand cm = [rows1 ++ [row1 ++ [c] : row2] ++ rows2 | c <- cs]
			where (rows1, row : rows2) = break (any best) cm
			      (row1,  cs  : row2) = break best row
			      best cs = (length cs == n)
			      n = minchoice cm

minchoice = minimum . filter (> 1) . concat . map (map length)

reduce css = map (remove (fixed css)) css

remove fs cs = if single cs then cs else cs \\ fs

pruneBy f = f . map reduce . f

prune = pruneBy boxs . pruneBy cols . pruneBy rows

search cm	| blocked cm = [ ]
			| all (all single) cm = [cm]
			| otherwise = (concat . map (search . prune) . expand) cm

sudoku = map (map head) . search . prune . choices

sample1 = groupBy 9 "2....1.38........5.7...6..........13.981..25731....8..9..8...2..5..697844..25...."
sample2 = groupBy 9 "3..7.8.....832.9.......5.1.9......7...4.1.8...2......9.5.8.......3.475.....5.3..6"
sample3 = groupBy 9 ".98..........7........15...1...........2....9...9.6.82.......3.5.1.........4...2."
sample4 = groupBy 9 ".5..6...1..48...7.8......522...57.3...........3.69...579......8.1...65..5...3..6."