Suduko arr(tuple) NotImplemented

game = """
_ _ 4  _ _ _  _ 5 7
2 _ _  _ _ _  8 _ _
3 9 _  5 _ _  _ _ 6

_ 1 _  4 7 5  9 _ _
_ _ _  _ 3 _  _ _ _
_ _ 5  2 1 8  _ 3 _

7 _ _  _ _ 9  _ 4 8
_ _ 9  _ _ _  _ _ 3
1 8 _  _ _ _  2 _ _
"""

game1='''
_ _ _ _ 6 1 _ _ 5
_ 3 _ _ _ _ _ _ 9
_ 4 _ _ _ 3 1 _ _

7 8 _ 3 _ _ _ 5 2
_ _ 2 _ _ _ 9 _ _
5 9 _ _ _ 8 _ 1 6

_ _ 7 1 _ _ _ 9 _
6 _ _ _ _ _ _ 7 _
9 _ _ 6 2 _ _ _ _
'''


game_test='''
_ 2 3 4 5 6 7 8 9
_ 5 _ _ _ _ _ _ _
_ 6 _ _ _ _ _ _ _

_ 3 _ _ _ _ _ _ _
_ 4 _ _ _ _ _ _ _
_ 7 _ _ _ _ _ _ _

_ 8 _ _ _ _ 2 3 4
_ 9 _ _ _ _ 5 6 7
_ _ _ _ _ _ 8 9 _
'''



def BoardFromInput(game):
  res = [[]]
  for ch in game:
    item = None
    if ch.isdigit():
      item = [True, int(ch)]
    elif ch == '_':
      item = [False, None]

    if item:
      if len(res[-1]) >= 9:
        res.append([])
      res[-1].append(item)
  if len(res) != 9 or len(res[-1]) != 9:
    print "ERROR - illegal Suduko input"
  return res


def PrintBoard(board):
  for (li, line) in enumerate(board):
    if li % 3 == 0:
       print "-" * 47
    for (ci, (isset, num)) in enumerate(line):
      if ci % 3 == 0:
        print " | ",
      if num:
        print num, " ",
      else:
        print "_", " ",
    print
  print "-" * 47


def InLine(n, board, line):
    raise NotImplementedError

def InCol(n, board, col):
    raise NotImplementedError

def InSq(n, board, line, col):
    raise NotImplementedError


def _test():
  board = BoardFromInput(game_test)
  assert InLine(2, board, 0)
  assert not InLine(1, board, 0)
  assert InCol(2, board, 1)
  assert not InCol(1, board, 1)
  assert InSq(2, board, 8, 8)
  assert not InSq(1, board, 8, 8)


def validate_game(game):
  board = BoardFromInput(game)
  for l in xrange(9):
    for c in xrange(9):
      if not board[l][c][0]:
        continue  # skip the free cells
      v = board[l][c][1]
      board[l][c][0] = False
      board[l][c][1] = None
      #print "line=", l , "col=", c, "num=", v
      assert not InLine(v, board, l)
      assert not InCol(v, board, c)
      assert not InSq(v, board, l, c)
      # restore
      board[l][c][0] = True
      board[l][c][1] = v



def Solve(board, i):
  #PrintBoard(board)
  #raw_input(">>>")
  if i >= 9 * 9:
    return True
  line = i / 9
  col = i % 9
  if board[line][col][0]:
    return Solve(board, i + 1)
  for n in range(1,10):
    board[line][col][1] = None
    line_bad = InLine(n, board, line)
    row_bad = InCol(n, board, col)
    sq_bad = InSq(n, board, line, col)
    #print "line_bad", line_bad, "row", row_bad, "sq", sq_bad
    if line_bad or row_bad or sq_bad:
      continue
    board[line][col][1] = n
    if Solve(board, i + 1):
      return True
    board[line][col][1] = None
  return False



validate_game(game1)
board = BoardFromInput(game1)
print "SUDUKO:"
PrintBoard(board)

if Solve(board, 0):
  print "SOLUTION:"
  PrintBoard(board)
else:
  print "NO SOUTION"