use std::fmt;
use std::io;
use std::io::prelude::*;
use std::ops::{Index, IndexMut, Range};
use std::process::exit;
use std::vec::Vec;
//use std::collections::HashMap;

#[inline]
fn fixed_point<T, F>(x: T, f: F) -> T
    where T: Eq + Clone, F: Fn(T) -> T
{
    let n = f(x.clone());

    if n == x {
        x
    } else {
        fixed_point(n, f)
    }
}

trait FoldWhile: Iterator {
    #[inline]
    fn fold_while<T, F>(self, init: T, mut f: F) -> Option<T> where
        Self: Sized, F: FnMut(T, Self::Item) -> Option<T>,
    {
        let mut accum = init;
        for x in self {
            accum = match f(accum, x) {
                Some(a)     => a,
                None        => return None
            }

        }
        Some(accum)
    }
}

impl<I> FoldWhile for I where I: Iterator {}

#[derive(Eq, PartialEq, Copy, Clone)]
struct BitBoardPos {
    x:          usize,
    y:          usize,
}

struct EachPos {
    i:          Range<usize>,
}

impl Iterator for EachPos {
    type Item = BitBoardPos;

    fn next(&mut self) -> Option<BitBoardPos> {
        self.i.next().map(|i| BitBoardPos { x: i / 9, y: i % 9 })
    }
}

fn each_pos() -> EachPos {
    EachPos { i: (0..81) }
}

struct EachBlock {
    i:          Range<usize>,
}

impl Iterator for EachBlock {
    type Item = BitBoardPos;

    fn next(&mut self) -> Option<BitBoardPos> {
        self.i.next().map(|i| BitBoardPos { x: i / 3 * 3, y: i % 3 * 3 })
    }
}

fn each_block() -> EachBlock {
    EachBlock { i: (0..9) }
}

struct Column {
    x:          usize,
    y:          Range<usize>,
}

impl Iterator for Column {
    type Item = BitBoardPos;

    fn next(&mut self) -> Option<BitBoardPos> {
        self.y.next().map(|y| BitBoardPos { x: self.x, y: y })
    }
}

struct Row {
    x:          Range<usize>,
    y:          usize,
}

impl Iterator for Row {
    type Item = BitBoardPos;

    fn next(&mut self) -> Option<BitBoardPos> {
        self.x.next().map(|x| BitBoardPos { x: x, y: self.y })
    }
}

struct Block {
    start:      BitBoardPos,
    i:          Range<usize>,
}

impl Iterator for Block {
    type Item = BitBoardPos;

    fn next(&mut self) -> Option<BitBoardPos> {
        self.i.next().map(|i| BitBoardPos {
            x: self.start.x + i / 3,
            y: self.start.y + i % 3
        })
    }
}

impl BitBoardPos {
    fn column(self) -> Column {
        Column  { x: self.x, y: (0..9), }
    }

    fn row(self) -> Row {
        Row     { x: (0..9), y: self.y, }
    }

    fn block(self) -> Block {
        Block {
            start: BitBoardPos {
                x: self.x / 3 * 3,
                y: self.y / 3 * 3,
            },
            i: (0..9),
        }
    }

    fn blocknr(self) -> usize {
        self.x / 3  * 3 + self.y / 3
    }
}

const  ALL_NUMS: u16 = ((1 << 9) - 1) << 1;

#[derive(Eq, PartialEq, Hash, Copy, Clone)]
struct BitBoard {
    b:  [[u16; 9]; 9],
}

impl BitBoard {
    fn new() -> BitBoard {
        BitBoard { b: [[ALL_NUMS; 9]; 9], }
    }
}

impl Index<BitBoardPos> for BitBoard {
    type Output = u16;

    fn index<'a>(&'a self, p: BitBoardPos) -> &'a u16 {
        &self.b[p.x][p.y]
    }
}

impl IndexMut<BitBoardPos> for BitBoard {
    fn index_mut<'a>(&'a mut self, p: BitBoardPos) -> &'a mut u16 {
        &mut self.b[p.x][p.y]
    }
}

fn read_board() -> BitBoard {
    let mut b = BitBoard::new();

    for i in 0..9 {
        let mut line = String::new();

        if io::stdin().read_line(&mut line).unwrap() < 9 {
            println!("didn't get sudoku line");
            exit(1);
        }

        for (j, c) in line.chars().enumerate() {
            if c == '\n' {
                break;
            }

            b.b[i][j] = if c == '.' {
                ALL_NUMS
            } else {
                1 << ((c as u32) - ('0' as u32)) as u16
            }
        }
    }

    b
}

impl fmt::Display for BitBoard {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        for i in self.b.iter() {
            for j in i.iter() {
                if j.is_power_of_two() {
                    try!(write!(f, "{}", j.trailing_zeros()));
                } else {
                    try!(write!(f, "."));
                }
            }

            try!(write!(f, "\n"));
        }

        Ok(())
    }
}

/*
 * Check if a board configuration is valid: not actually used in the solver,
 * just an additional check:
 */
fn check(b: &BitBoard) -> bool {
    let origin = BitBoardPos { x: 0, y: 0 };

    /* Check a column/row/block for duplicates - true if no duplicates */
    fn check_iter(b: &BitBoard, iter: &mut Iterator<Item=BitBoardPos>) -> bool {
        iter.filter(|i| b[*i].is_power_of_two())
            .fold_while(0u16, |v, i|
                        if v & b[i] != 0 { None }
                        else { Some(v | b[i]) })
            .is_some()
    }

    origin.row()    .all(|i| check_iter(b, &mut i.column())) &&
    origin.column() .all(|i| check_iter(b, &mut i.row())) &&
    each_block()    .all(|i| check_iter(b, &mut i.block()))
}

/* Start of solver: */

fn strike_solved(b: BitBoard, p: BitBoardPos) -> Option<BitBoard> {
    /*
     * if @p is solved, strike it from every other cell in the same
     * row/column/block:
     */
    assert!(b[p].is_power_of_two());

    let mut b = b;

    for i in p.column()
        .chain(p.row())
        .chain(p.block())
        .filter(|i| *i != p) {
        if (b[i] & b[p]) != 0 {
            b[i] ^= b[p];
            if b[i] == 0 {
                println!("inconsistent at:\n{} {}", b, check(&b));
                return None;
            }
        }
    }

    Some(b)
}

/*
 * Check every other cell in the same row/column/block as this cell - if
 * there is a number that we've determined can't be in any of those cells,
 * then it must be in this cell:
 */
fn constrain_single(b: BitBoard, p: BitBoardPos,
                    iter: &mut Iterator<Item=BitBoardPos>) -> Option<BitBoard> {
    if !b[p].is_power_of_two() {
        let m = iter
            .filter(|i| *i != p)
            .fold(0u16, |a, i| a | b[i])
            ^ ALL_NUMS;

        if m.is_power_of_two() {
            if (b[p] & m) == 0 {
                println!("inconsistent at:\n{} {}", b, check(&b));
                return None;
            }

            let mut b = b;
            b[p] = m;

            return strike_solved(b, p);
        }
    }

    Some(b)
}

/*
fn constrain_multiple_block_col(
    mut b: BitBoard,
    block: &mut Iterator<Item=BitBoardPos>,
    iter: &mut Iterator<Item=BitBoardPos>) -> Option<BitBoard> {
    let by_block = [0u16; 9];

    for i in iter {
    }

    Some(b)
}

fn constrain_multiple_block(
    mut b: BitBoard,
    block: &mut Iterator<Item=BitBoardPos>) -> Option<BitBoard> {
}

fn constrain_multiple(mut b: BitBoard) -> Option<BitBoard> {
    each_block()
        .fold_while(b, |b, i| constrain_multiple_block(b, &mut i.block()))
}
*/

fn do_solve(b: Option<BitBoard>) -> Option<BitBoard> {
    b.and_then(|b| each_pos().fold_while(b, |b, i| 
                                         constrain_single(b, i, &mut i.column())))
     .and_then(|b| each_pos().fold_while(b, |b, i| 
                                         constrain_single(b, i, &mut i.row())))
     .and_then(|b| each_pos().fold_while(b, |b, i| 
                                         constrain_single(b, i, &mut i.block())))
     //.and_then(|b| constrain_multiple(b))
}

fn strike_initial_solved(b: Option<BitBoard>) -> Option<BitBoard> {
    b.and_then(|b| each_pos()
               .filter(|i| b[*i].is_power_of_two())
               .fold_while(b, |b, i| strike_solved(b, i)))
}

fn solve(b: BitBoard) -> Vec<BitBoard> {
    let b = match fixed_point(Some(b), strike_initial_solved) {
        Some(b) => b,
        None    => return Vec::new(),
    };

    let b = match fixed_point(Some(b), do_solve) {
        Some(b) => b,
        None    => return Vec::new(),
    };

    /*
     * When we get stuck, if there's unsolved cells left switch to backtracking:
     */
    match each_pos().find(|i| !b[*i].is_power_of_two()) {
        None        => vec![b],
        Some(i)     => {
            println!("backtracking at:\n{}", b);

            let v = b[i];

            (1..10)
                .filter(|j| (v & (1 << *j)) != 0)
                .flat_map(|j| {
                    let mut r = b;

                    r[i] = 1 << j;

                    solve(r)})
                .collect()
        }
    }
}

fn main() {
    let b = read_board();

    println!("{} {}", b, check(&b));

    let solutions = solve(b);

    for i in solutions {
        println!("{} {}", i, check(&i));
    }
}


/*
type Memoize = HashMap<BitBoard, Vec<BitBoard>>;

fn solve_memoized(b: &BitBoard, memo: &mut Memoize) -> Vec<BitBoard> {
    match memo.get(b) {
        Some(i)     => return i.clone(),
        None        => ()
    }

    let ret = solve(*b);

    memo.insert(*b, ret.clone());

    if memo.len() % 1000 == 0 {
        println!("cached {} solutions", memo.len());
    }

    ret
}

fn make_harder_recurse(b: &BitBoard, memo: &mut Memoize) -> Vec<BitBoard> {
    let nr_solutions = solve_memoized(&b, memo).len();

    assert!(nr_solutions != 0);

    if nr_solutions > 1 {
        //println!("{} solutions at:\n{}", nr_solutions, b);
        return Vec::new();
    }

    each_pos()
        .filter(|i| b[*i].is_power_of_two())
        .flat_map(|i| {
            let mut r = *b;

            r[i] = ALL_NUMS;

            make_harder_recurse(&mut r, memo)})
        .chain(vec![*b].into_iter())
        .collect()
}

fn nr_set(b: &BitBoard) -> usize {
    each_pos()
        .filter(|i| b[*i].is_power_of_two())
        .count()
}

fn make_harder(_b: BitBoard, memo: &mut Memoize) -> BitBoard {
    let mut b = _b;
    let mut nr_ret = nr_set(&b);

    for i in each_pos() {
        if !b[i].is_power_of_two() {
            b[i] = ALL_NUMS;
        }
    }

    let boards = make_harder_recurse(&b, memo);

    assert!(boards.len() != 0);

    for i in boards {
        let nr_i = nr_set(&i);

        if nr_i < nr_ret {
            nr_ret = nr_i;
            b = i;
        }
    }

    b
}

fn main() {
    let mut memo: Memoize = HashMap::new();

    let b = read_board();

    println!("{} {}", b, check(&b));

    /*
    let harder = make_harder(b, &mut memo);

    println!("harder version: {} set, orig {} \n{}",
             nr_set(&b),
             nr_set(&harder),
             harder);
             */

    let solutions = solve_memoized(&b, &mut memo);

    println!("{} solutions:", solutions.len());

    for i in solutions {
        println!("{} {}", i, check(&i));
        /*

        let harder = make_harder(&i, &mut memo);

        println!("harder version: {} set, orig {} \n{}",
                 nr_set(&i),
                 nr_set(&harder),
                 harder);
                 */
    }
}
*/