suduku obj

import sys
import unittest

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 _ _
"""

class FixedCell(object):
  """An item on the Sudoku board. Can be fixed or free.
  """
  pass

class FreeCell(object):
  """An item on the Sudoku board. Can be fixed or free.
  """
  pass

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


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


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


def BoardFromInput(game):
    """Parse string into a list of lists of cells"""
    res = [[]]
    for ch in game:
        item = None
        if ch.isdigit():
            item = FixedCell(int(ch))
        elif ch == '_':
            item = FreeCell()
        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 Sudoku input"
    return res


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


def Solve(board, i):
    # Yo can add the following lines to see advance step by step
    #PrintBoard(board)
    #raw_input("??>")
    if i >= 9 * 9:
        return True
    line = i / 9
    col = i % 9
    if isinstance(board[line][col], FixedCell):
        return Solve(board, i + 1)
    for n in range(1,10):
        board[line][col].clear_val()
        line_bad = InLine(n, board, line)
        row_bad = InCol(n, board, col)
        sq_bad = InSq(n, board, line, col)
        if line_bad or row_bad or sq_bad:
            continue
        board[line][col].set_val(n)
        if Solve(board, i + 1):
            return True
        board[line][col].clear_val()
    return False


def main(argv):
  board = BoardFromInput(game)
  print "SUDOKU:"
  PrintBoard(board)

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


if __name__ == "__main__":
    sys.exit(main(sys.argv))


class TestSudoku(unittest.TestCase):

  def setUp(self):
    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 _
'''
    self.board = BoardFromInput(game_test)

  def test_InLine(self):
    self.assertTrue(InLine(2, self.board, 0))
    self.assertFalse(InLine(1, self.board, 0))

  def test_InCol(self):
    self.assertTrue(InCol(2, self.board, 1))
    self.assertFalse(InCol(1, self.board, 1))

  def test_InSq(self):
    self.assertTrue(InSq(2, self.board, 8, 8))
    self.assertFalse(InSq(1, self.board, 8, 8))