(* Displays all the solution for a sudoku grid.
   Author: Alain Frisch.

   The program reads a description of the problem on stdin.
   You must provide a grid like:

001005300
050490000
000102064
000000750
600000001
035000000
060903000
000020090
003600100

   Zero correspond to unknown digits to be guessed.

*)
   

exception Impossible
  (* Raised when a contradiction has been found *)

(* bit_rank (1 lsl k) = k for k=0..8 *)
let bit_rank =
  let a = Array.create 512 (-1) in
  for i = 0 to 8 do a.(1 lsl i) <- i done;
  fun i -> a.(i)

(* least_bit n keeps only the least significant 1 bit *)
let least_bit n = n land (lnot (n - 1))

(* is there exactly one 1 bit ? *)
let only_one_1 n = (n != 0) && (n == least_bit n)

(* The grid is represented by a one dimensional array with 81 cells.
   Each cell is a bit-mask of all the possible digits.
   coord returns the cell number given its coordinates. *)

let coord x y = x + 9 * y

(* print a grid *)

let print a =
  for y = 0 to 8 do
    for x = 0 to 8 do
      let i = coord x y in
      if only_one_1 a.(i) then
	print_char (Char.chr( 49 + bit_rank a.(i)))
      else
	print_char '.'
    done;
    print_newline ();
  done


(* Assume that one cell has been resolved. Propagate the constraints.
   Accumulate in placed the set of freshly resolved cells. *)

let place a i0 placed =
  assert(only_one_1 a.(i0));
  let x = i0 mod 9 and y = i0 / 9 in
  let m = lnot a.(i0) in
  let f x' y' =
    let i = coord x' y' in
    let old = a.(i) in
    let n = old land m in
    if n = 0 then (if i == i0 then () else raise Impossible)
    else (if (only_one_1 n && (not (only_one_1 old))) 
	  then placed := i :: !placed;
	  a.(i) <- n)
  in
  for y' = 0 to 8 do f x y' done;
  for x' = 0 to 8 do  f x' y done;
  let x0 = (x / 3) * 3 and y0 = (y / 3) * 3 in
  for x' = x0 to x0+2 do for y' = y0 to y0+2 do f x' y' done done
  

let place_all a placed =
  let placed = ref placed in
  let rec loop () = match !placed with
    | i::rest -> placed := rest; place a i placed; loop ()
    | [] -> () in
  loop ()


let rec main_loop a i =
  if (i = 81) then (print a; print_endline "---")
  else if only_one_1 a.(i) then main_loop a (succ i)
  else
    for k = 0 to 8 do
      let m = 1 lsl k in
      if a.(i) land m <> 0 then
	(* Try with this digit *)
	try 
	  let a' = Array.copy a in
	  a'.(i) <- m;
	  place_all a' [i];
	  main_loop a' (succ i);
	with Impossible -> ()
    done
  
let () =
  let a = Array.create 81 511 in
  let placed = ref [] in
  for y = 0 to 8 do
    let s = read_line () in
    for x = 0 to 8 do
      match s.[x] with
	| '0' -> ()
	| '1'..'9' as c ->
	    let i = coord x y in
	    a.(i) <- 1 lsl (Char.code c - 49);
	    placed := i :: !placed
	| _ -> failwith "Invalid input"
    done;
  done;
  place_all a !placed;
  main_loop a 0