import Char(intToDigit, digitToInt, isDigit)
import List ((\\), sortBy)

data Board = Board [Square]
	deriving (Show)

data Square = Square ColDigit RowDigit BoxDigit (Either [Digit] Digit)
	deriving (Show)

type ColDigit = Digit
type RowDigit = Digit
type BoxDigit = Digit
type Digit = Char	-- '1' .. '9'

initialBoard :: Board
initialBoard = Board [ Square col row (boxDigit col row) (Left allDigits) |
		       row <- allDigits, col <- allDigits ]
  where allDigits = ['1' .. '9']

boxDigit :: ColDigit -> RowDigit -> BoxDigit
boxDigit c r = intToDigit $ (digitToInt c - 1) `div` 3 + (digitToInt r - 1) `div` 3 * 3 + 1

printBoard :: Board -> String
printBoard (Board sqs) = concatMap prSquare sqs
  where prSquare (Square col row _ ds) = prDigits ds ++
		(if col == '3' || col == '6' then "|"
		 else if col == '9' then "\n"
		 else "") ++
		(if (row == '3' || row == '6') && col == '9' then "---+---+---\n" else "")
	prDigits (Right d) = [d]
	prDigits _   = " "

parseBoard :: String -> [Square]
parseBoard s = parse ('1', '1') s
  where parse _ "" = []
	parse rc (' ':cs) = parse (incr rc) cs
	parse rc ('0':cs) = parse (incr rc) cs
	parse rc@(row,col) (c:cs) | isDigit c = Square col row (boxDigit col row) (Right c) : parse (incr rc) cs
	parse rc (_:cs) = parse rc cs
	incr (r,'9') = (succ r, '1')
	incr (r, c) = (r, succ c)

setSquare :: Square -> Board -> Board
setSquare sq@(Square scol srow sbox (Right d)) (Board sqs) = Board (map set sqs)
  where set osq@(Square col row box ds) =
	    if col == scol && row == srow then sq
	    else if col == scol || row == srow || box == sbox then (Square col row box (sub ds))
	    else osq
	sub (Left ds) = Left (ds \\ [d])
	sub dd = dd
setSquare _ _ = error "Bad setSquare"

getLeftSquares :: Board -> [Square]
getLeftSquares (Board sqs) = [ sq | sq@(Square _ _ _ (Left _)) <- sqs ]

makeBoard :: String -> Board
makeBoard = foldr setSquare initialBoard . parseBoard

solveMany :: Board -> [Board]
solveMany brd =
    case getLeftSquares brd of
    [] -> return brd
    sqs -> do
	let Square c r b (Left ds) : _ = sortBy leftLen sqs
	    leftLen (Square _ _ _ (Left ds1)) (Square _ _ _ (Left ds2)) = compare (length ds1) (length ds2)
	    leftLen _ _ = error "bad leftLen"
        sq <- [ Square c r b (Right d) | d <- ds ]
        solveMany (setSquare sq brd)

solve :: Board -> Board
solve b =
    case solveMany b of
    [] -> error "No solutions"
    b' : _ -> b'

main :: IO ()
main = interact $ unlines . map (printBoard . solve . makeBoard) . lines