import Data.Maybe
import Data.List

parseSudoku :: String -> [[Maybe Int]]
parseSudoku string = map parseLine (lines string) where
	parseLine "" = []
	parseLine ('_':rest) = Nothing : parseLine rest
	parseLine (' ':rest) = parseLine rest
	parseLine (char:rest) = Just (read [char]) : parseLine rest

checkDimensions :: [[a]] -> Bool
checkDimensions sudoku = and (map ((==9).length) sudoku) && (length sudoku == 9)

solveSudoku :: [[Maybe Int]] -> [[[Int]]]
solveSudoku sudoku
	| not (checkConsistent sudoku) = []
	| length (concatMap catMaybes sudoku) == 9*9 = [map catMaybes sudoku]
	| otherwise = concatMap solveSudoku (fillFirstNothing sudoku)

fillFirstNothing :: [[Maybe Int]] -> [[[Maybe Int]]]
fillFirstNothing [] = [[]]
fillFirstNothing ([]:rows) = map ([]:) (fillFirstNothing rows)
fillFirstNothing ((Just x : row) : rows) = map (prependJustX x) (fillFirstNothing (row : rows))
fillFirstNothing ((Nothing : row) : rows) = map (flip prependJustX (row:rows)) [1..9]

prependJustX :: Int -> [[Maybe Int]] -> [[Maybe Int]]
prependJustX x (row' : rows) = (Just x : row') : rows

checkConsistent :: [[Maybe Int]] -> Bool
checkConsistent sudoku = checkRows sudoku && checkColumns sudoku && checkSquares sudoku

checkRows :: [[Maybe Int]] -> Bool
checkRows sudoku = and $ map (hasNoDuplicates . catMaybes) sudoku

checkColumns :: [[Maybe Int]] -> Bool
checkColumns = checkRows . transpose

checkSquares :: [[Maybe Int]] -> Bool
checkSquares [] = True
checkSquares ([]:[]:[]:sudoku) = checkSquares sudoku
checkSquares ((x1:x2:x3:row1):(x4:x5:x6:row2):(x7:x8:x9:row3):sudoku) =
	hasNoDuplicates (catMaybes [x1,x2,x3,x4,x5,x6,x7,x8,x9])
	&& checkSquares (row1:row2:row3:sudoku)

hasNoDuplicates :: [Int] -> Bool
hasNoDuplicates list = length list == length (nub list)