#!/usr/bin/python

# A simple Sudoku solver by Neil Campbell
# Written December 2005.

import sys;

# Where the actual numbers live.
grid = [];

# A handy set for doing differences.
allNums = set([ 1, 2, 3, 4, 5, 6, 7, 8, 9 ]);

def missing(present):
  return allNums.difference(present);

# Get all the numbers from a row.
def getRow(row):
  nums = [];
  for i in range(9):
    if grid[row][i] != ' ':
      nums.append(grid[row][i]);
  return set(nums);

# Get all the numbers from a column.
def getColumn(column):
  nums = [];
  for i in range(9):
    if grid[i][column] != ' ':
      nums.append(grid[i][column]);
  return set(nums);

# Get all the numbers from a 9x9 square.
def getSquare(row, col):
  squareRow = row / 3;
  squareCol = col / 3;
  
  startRow = squareRow * 3;
  startCol = squareCol * 3;
  
  nums = [];
  
  for x in range(3):
    for y in range(3):
      digit = grid[startRow + x][startCol + y];
      nums.append(digit);
  return set(nums); 
 
# Read in the data from stdin.  Very little validation here.
for l in sys.stdin.readlines():
  if len(l.strip('\n')) == 9:
    row = [];
    for c in l.strip('\n'):
      if c == ' ':
        row.append(0);
      else:
        row.append(int(c));
    grid.append(row);
      
  else:
    print "ignoring: " + l.strip();
  
# Print the grid to see how far we've got.
def showGrid():
  print "";
  for row in range(9):
    for col in range(9):
      digit = grid[row][col];
      if digit == 0:
        print '*',
      else:
        print digit,
    print "";

def getBlanks():
  tmpBlanks = [];
  for row in range(9):
    for col in range(9):
      digit = grid[row][col];
      if digit == 0:
        tmpBlanks.append( { 'col': col, 'row': row } );
  return tmpBlanks;

def getPossibilitiesForSquare(row, col):
  rowPossible = missing(getRow(row));
  colPossible = missing(getColumn(col));
  squPossible = missing(getSquare(row, col));
  return rowPossible & colPossible & squPossible;

def lookForDuplicates(listOfPossiblities):
  removes = [];
  for i in range(len(listOfPossiblities)):
    for j in range(len(listOfPossiblities)):
      if i != j:
        if listOfPossiblities[i] == listOfPossiblities[j]:
          if len(listOfPossiblities[i]) <= 2:
            for val in listOfPossiblities[i]:
              removes.append(val);
          # If there are 3 with 3 in, we could remove them too.
          # Or 4 with 4, etc.
          #else:
          #  print "Need to be more clever!";

  return set(removes);
  
def searchForOtherRemovals(row, col):
  rowUnknowns = [];
  colUnknowns = [];
  squUnknowns = [];
  
  # row
  for i in range(9):
    # another unknown in the row
    if (0 == grid[row][i]) and (i != col):
      rowUnknowns.append(getPossibilitiesForSquare(row, i));

  #column
  for i in range(9):
    # another unknown in the column
    if (0 == grid[i][col]) and (i != row):
      colUnknowns.append(getPossibilitiesForSquare(i, col));

  rowRemoves = lookForDuplicates(rowUnknowns);
  colRemoves = lookForDuplicates(colUnknowns);
  removes = rowRemoves | colRemoves;
      
  # I don't search squares yet!
  
  return removes;
  
# Here's where we start actually working.

# First get a list of blank squares that we need to solve.
blanks = getBlanks();

# While there are blanks left, try to solve them.
while len(blanks) > 0:

  showGrid();
  
  # Keep track of how many we solved, if we didn't get any we have to stop,
  # otherwise we'll loop forever.
  solved = 0;
  
  # Look at each blank in turn.
  for pair in blanks:
    row = pair['row'];
    col = pair['col'];
    
    # Find out what could possibly go in this square, based on the contents of
    # its row, column and square.
    possible = getPossibilitiesForSquare(row, col);
    
    if len(possible) == 0:
      # Gah! It's all gone King Kong.
      print "Yikes, something is wrong, I have no possibilities left.\n";
      sys.exit(1);

    # There are several possibilities here, so we look for any way to cancel
    # some of them.
    elif len(possible) > 1:
      removes = searchForOtherRemovals(row, col);
      if len(removes) > 0:
        possible = possible - removes;
      
    if len(possible) == 1:
      # W00t! We have an answer.
      answer = possible.pop();
      grid[row][col] = answer;
      print "Solved: " + str(pair) + "; it is " + str(answer);
      solved += 1;
      
  # Update our list of blanks.
  blanks = getBlanks();
  if solved == 0:
    print "Getting nowhere, giving up";
    break;

# Success or no, we're finished here.  Show the solution, or as close as we got.
showGrid();