import Data.List
--import Data.List.Split (chunksOf)
 
solve field | elem '-' field = filter (not.null) $ concatMap solve $ nextstep field
            | otherwise      = [field]
 
nextstep field | m == 0      = [[]]
               | otherwise   = map (\c -> take i field ++ c : drop (i+1) field) v
    where
        freecells = elemIndices '-' field
        (m, i, v) = minimum $ map (\i -> let v = variants i in (length v,i,v)) freecells
 
        variants i  = "123456789" \\ (rownums ++ colnums ++ squnums) where
            (r,c)   = divMod i 9
            rownums = take 9 . drop (r*9) $ field
            colnums = map ((field!!).(+c)) [0,9..80]
            [r',c'] = map (\x -> x `div` 3 * 3) [r,c]
            squnums = concatMap (take 3 . flip drop field . (\x -> (x+r')*9+c')) [0..2]
 
showres fields | null fields = "No solution"
--               | otherwise   = (' ':).intersperse ' '.unlines.chunksOf 9.head $ fields
               | otherwise   = head fields
 
main = do
    let f = "--7---34-\
            \2---38---\
            \1--4----2\
            \-2-9-64--\
            \-7--4--8-\
            \--58-2-1-\
            \8----4--1\
            \---65---9\
            \-32---7--"
    putStr $ showres $ solve f