from itertools import product
import sys


def inRow(i, j):
    """is position 'i' in the same row as position 'j'"""
    return i//9 == j//9


def inCol(i, j):
    """is position 'i' in the same column as position 'j'"""
    return (i - j) % 9 == 0


def inBox(i, j):
    """is position 'i' in the same sub 3x3 box as position 'j'"""
    return (i//27 == j//27) and (i % 9//3 == j % 9//3)


"""
'peers' holds all the indexes of cells that influences the
possibilities the given cell can be.
"""
peers = {i: [] for i in range(81)}
for i, j in product(range(81), range(81)):
    if i == j:
        continue
    if any(f(i, j) for f in (inRow, inCol, inBox)):
        peers[i].append(j)
"""
eg: peers[0]

  [X] X  X | X  X  X | X  X  X
   X  X  X | .  .  . | .  .  .
   X  X  X | .  .  . | .  .  .
  ---------+---------+---------
   X  .  . | .  .  . | .  .  .
   X  .  . | .  .  . | .  .  .
   X  .  . | .  .  . | .  .  .
  ---------+---------+---------
   X  .  . | .  .  . | .  .  .
   X  .  . | .  .  . | .  .  .
   X  .  . | .  .  . | .  .  .

"""


def init(matrix):
    """replace unanswered cells with the possibilities they could be"""
    new_matrix = list(matrix)
    for i, cell in filter(lambda x: x[1] == '0', enumerate(new_matrix)):
        new_matrix[i] = ''.join(constraint(matrix, i))
    return new_matrix


def constraint(matrix, cell_index):
    """return all possibilities for the given cell"""
    return set('123456789') - set(matrix[j] for j in peers[cell_index])


def search(matrix):
    """return an unanswered cell with the least number possibilities"""
    try:
        _, i = min((len(n), i) for i, n in enumerate(matrix) if len(n) > 1)
    except ValueError:
        return False  # we solved it
    return i


def eliminate(matrix, index, value):
    """remove the possibility from the cell and it's peers"""
    if value not in matrix[index]:
        return matrix  # we've already eliminated it

    matrix[index] = matrix[index].replace(value, '')
    num_possibilities = len(matrix[index])

    # if we've eliminated all the possibilities
    # for this cell, we need to backtrack
    if num_possibilities == 0:
        return False

    # if this is the last option for this cell, go ahead
    # and assign it and eliminate that value for it's peers
    if num_possibilities == 1:
        another_value = matrix[index]
        if not all(eliminate(matrix, i, another_value) for i in peers[index]):
            return False  # eliminating that value caused us to backtrack

    return matrix


def assign(matrix, index, value):
    """remove all possibilities except the given value"""
    if all(eliminate(matrix, index, v) for v in matrix[index] if v != value):
        return matrix
    return False


def solve(matrix):
    """
    use recursion until we get to a state where we need to backtrack
    or, return the result after we've filled all cells
    """
    # what cell should we work on next
    index = search(matrix)
    if index is False:
        return matrix  # we've solved it

    # loop through all the possibilities the cell could be
    for possibility in matrix[index]:
        matrix_copy = assign(matrix.copy(), index, possibility)
        if matrix_copy is False:
            continue  # ran into an impossibility, try another number

        # might be possible, try to solve another cell
        result = solve(matrix_copy)
        if result is not False:
            return result

    return False


if __name__ == '__main__':
    """solve each unanswered Sudoku puzzles"""
    for puzzle in sys.argv[1:]:

        # replace unanswered cells with the possible
        # numbers the cell could be
        init_puzz = init(puzzle)

        # solve and print the possibilities
        solved_puzz = solve(init_puzz)
        print(''.join(solved_puzz))