Sudoku arr(tuple) fork()

import os
import sys

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):
  for isset, num in board[line]:
    if n == num:
      return True
  return False

def InCol(n, board, col):
  for line in board:
    isset, num = line[col]
    if n == num:
      return True
  return False

def InSq(n, board, line, col):
  sqY = line / 3
  sqX = col / 3
  for l in xrange(sqY * 3, sqY * 3 + 3):
    for c in xrange(sqX * 3, sqX * 3 + 3):
      isset, num = board[l][c]
      if n == num:
        return True
  return False


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 SolveFork(board, i , use_fork=False, childs_set = None):
    """Call Solve(board, i).
    if use_fork=False - just call it and return its value
    when use_fork==True - open a child process to run Solve()
    and at the parent - add the child's pid to childs_set and return False.
    """
    if not use_fork:
        return Solve(board, i)
    # using fork
    child_pid = os.fork()
    if child_pid == 0:
        # inside child process
        solved = Solve(board, i)
        if solved:
            sys.exit(1)
        else:
            sys.exit(0)
    else:
        childs_set.add(child_pid)
    return False


def Solve(board, i):
  #PrintBoard(board)
  #raw_input(">>>")
  if i >= 9 * 9:
    print "SOLUTION:"
    PrintBoard(board)
    return True
  line = i / 9
  col = i % 9
  if board[line][col][0]:
    return Solve(board, i + 1)
  childs = set()
  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
    use_fork = i < 2
    solved = SolveFork(board, i + 1, use_fork=use_fork, childs_set=childs)
    if solved:
        return True
    board[line][col][1] = None
  # after starting all child processes
  # wait for them to end
  # NOte that if for was NOT used - childs={} and False is returned here
  solved = False
  while childs:
      finished_pid, exit_status = os.wait()
      # print "DEBUG finished_pid = ", finished_pid, exit_status
      childs.remove(finished_pid)
      if exit_status > 0:
          solved = True
  return solved


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

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