#!/usr/bin/perl
use strict ;

################################################################################
################################################################################

sub check_row {
	my ( $guess, $row, $col ) = @_ ;

	die "Problem in sub check_row" if( $row < 0 || $row > 9 ) ;

	my %eliminate = () ;	
	for( my $i = 0 ; $i < 9 ; $i++ ) {
		next if $i == $col ;
		my @taken = keys %{$guess->[$row][$i]} ;
		$eliminate{ $taken[0] } = 1 if $#taken == 0 ;
	}

	my %c = %{$guess->[$row][$col]} ;
	delete $c{$_} foreach ( keys %eliminate ) ;

	$guess->[$row][$col] = \%c ;
}

################################################################################
################################################################################

sub check_col {
	my ( $guess, $row, $col ) = @_ ;

	die "Problem in sub check_col" if( $row < 0 || $row > 9 ) ;

	my %eliminate = () ;
	for( my $i = 0 ; $i < 9 ; $i++ ) {
		next if $i == $row ;
		my @taken = keys %{$guess->[$i][$col]} ;
		$eliminate{ $taken[0] } = 1 if $#taken == 0 ;
	}

	my %c = %{$guess->[$row][$col]} ;
	delete $c{$_} foreach ( keys %eliminate ) ;

	$guess->[$row][$col] = \%c ;
}

################################################################################
################################################################################

sub check_blk {
	my ( $guess, $row, $col ) = @_ ;

	die "Problem in sub check_blk" if( $row < 0 || $row > 9 ) ;

	my $rblk ;
	$rblk = 0 if( $row == 0 || $row == 1 || $row == 2 ) ;
	$rblk = 3 if( $row == 3 || $row == 4 || $row == 5 ) ;
	$rblk = 6 if( $row == 6 || $row == 7 || $row == 8 ) ;

	my $cblk ;
	$cblk = 0 if( $col == 0 || $col == 1 || $col == 2 ) ;
	$cblk = 3 if( $col == 3 || $col == 4 || $col == 5 ) ;
	$cblk = 6 if( $col == 6 || $col == 7 || $col == 8 ) ;

	my %eliminate = () ;
	for( my $i = 0 ; $i < 3 ; $i++ ) {
		for( my $j = 0 ; $j < 3 ; $j++ ) {
			my $r = $rblk + $i ;
			my $c = $cblk + $j ;
			next if ( $r == $row && $c == $col ) ;
			my @taken = keys %{$guess->[$r][$c]} ;
			$eliminate{ $taken[0] } = 1 if $#taken == 0 ;
		}
	}

	my %c = %{$guess->[$row][$col]} ;
	delete $c{$_} foreach ( keys %eliminate ) ;

	$guess->[$row][$col] = \%c ;
}


################################################################################
################################################################################

sub elimination_round {
	my ( $guess ) = @_ ;

	for( my $i = 0 ; $i < 9 ; $i++ ) {
		for( my $j = 0 ; $j < 9 ; $j++ ) {
			my @taken = keys %{$guess->[$i][$j]} ;
			next if $#taken == 0 ;
			check_row( $guess, $i, $j ) ;
			check_col( $guess, $i, $j ) ;
			check_blk( $guess, $i, $j ) ;
		}
	}
}

################################################################################
################################################################################

sub print_nice {
	my ( $guess ) = @_ ;

	my $string = "" ;
	my $pstring = "" ;
	my $qstring = "" ;

	for( my $i = 0 ; $i < 9 ; $i++ ) {

		$pstring .= "\n" ;
		$qstring .= "\n" ;
		for( my $j = 0 ; $j < 9 ; $j++ ) {
			my @taken = keys %{$guess->[$i][$j]} ;

			if( $#taken == 0 ) {
				$string .= $taken[0] ;
				$pstring .= " " . $taken[0] . " " ;
			} else {
				$string .= "." ;
				$pstring .= " . "
			}

			$qstring .= $_  foreach ( sort @taken ) ;
			for( my $k = 0 ; $k <= 8-$#taken ; $k++ ) {
				$qstring .= " " ;
			}

		}
		$pstring .= "\n" ;
		$qstring .= "\n" ;
	}

	return ( $string, $pstring, $qstring ) ;
}

################################################################################
################################################################################

sub winner {
	my ( $guess ) = @_ ;

	for( my $i = 0 ; $i < 9 ; $i++ ) {
		for( my $j = 0 ; $j < 9 ; $j++ ) {
			my @taken = keys %{$guess->[$i][$j]} ;
			return 0 if( $#taken != 0 ) ;
		}
	}

	return 1 ;
}

################################################################################
################################################################################

sub no_solution {
	my ( $guess ) = @_ ;

	for( my $i = 0 ; $i < 9 ; $i++ ) {
		for( my $j = 0 ; $j < 9 ; $j++ ) {
			my @taken = keys %{$guess->[$i][$j]} ;
			return 1 if( $#taken == -1 ) ;
		}
	}

	return 0 ;
}	

################################################################################
################################################################################

sub subgames {
	my ( $guess ) = @_ ;

	my ( $mr, $mc, $min ) = ( 0, 0, 10 ) ;
	for( my $i = 0 ; $i < 9 ; $i++ ) {
		for( my $j = 0 ; $j < 9 ; $j++ ) {
			my @taken = keys %{$guess->[$i][$j]} ;
			next if $#taken == 0 ;
			( $mr, $mc, $min ) = ( $i, $j, $#taken ) if $#taken < $min ;
			goto GOOD_ENOUGH if $#taken ==  1 ;
		}
	}

	GOOD_ENOUGH:

	my @games = () ;
	foreach my $n ( keys %{$guess->[$mr][$mc]} ) {
		my $string = "" ;
		for( my $i = 0 ; $i < 9 ; $i++ ) {
			for( my $j = 0 ; $j < 9 ; $j++ ) {
				my @taken = keys %{$guess->[$i][$j]} ;

				if ( $i == $mr && $j == $mc ) {
					$string .= $n ;
				} else {
					if( $#taken == 0 ) {
						$string .= $taken[0] ;
					} else {
						$string .= "." ;
					}
				}
			}

		}
		push( @games, $string ) ;
	}

	return \@games ;
}

################################################################################
################################################################################

sub read_board {

	my ( $string ) = @_ ;

	my @board ;

	for( my $i = 0 ; $i < 81 ; $i++ ) {
		my $row = int $i / 9 ; 
		my $col = int $i % 9 ;
		my $c = substr($string, $i, 1 ) ;
		if ( $c eq '.' ) {
			$board[$row][$col] = 0 ;
		} else {
			$board[$row][$col] = $c ;
		}
	}

	return \@board ;
}

################################################################################
################################################################################

sub main {

	my ( $string ) = @_ ;

	my $board = read_board( $string ) ;

	my @guess ;

	for( my $i = 0 ; $i < 9 ; $i++ ) {
		for( my $j = 0 ; $j < 9 ; $j++ ) {
			my %possibilities ;
			if( $board->[$i][$j] == 0 ) {
				%possibilities = ( 1=>1, 2=>1, 3=>1, 4=>1, 5=>1, 6=>1, 7=>1, 8=>1, 9=>1 ) ;
			} else {
				%possibilities = ( $board->[$i][$j] => 1 ) ;
			}
			$guess[$i][$j] = \%possibilities ;
		}
	}

	my $oldstring = "" ;
	for(;;) {
		elimination_round( \@guess ) ;

		my ( $newstring, $pstring, $qstring ) = print_nice( \@guess ) ;

		if ( no_solution( \@guess ) ) {
			return 0 ;
		}

		if ( winner( \@guess ) ) {
			return $newstring ;
		}

		if ( $newstring eq $oldstring ) {
			my $games = subgames( \@guess ) ;
			foreach ( @{$games} ) {
				print $_ . "\n" ;
				my $answer = main($_) ;
				return $answer if $answer != 0 ;
			}
			return 0 ;
		}

		$oldstring = $newstring ;
	}
}

################################################################################
################################################################################

my $string = $ARGV[0] ;
my $answer = main( $string ) ;
print $answer . "\n" ;