import copy

# A simple brute force sudoku solver.
# Natan Zohar
# Puzzles are in the format:
"""
000100702
030950000
001002003
590000301
020000070
703000098
800200100
000085060
605009000

Note the lack of spacing and that there are 9 characters per line
"""


class SudokuSolver:
    def __init__(self):
        self.unsolvable = False
        self.steps = []
        
    def solve(self, puzzle):
        self.puzzle = puzzle
        self.solution = copy.deepcopy(puzzle)
        self.filled = 0

        for x in puzzle:
            for y in x:
                if y != '0':
                    self.filled+=1
        self.recurse()
        return self.solution

    def output(self):
        print "Puzzle: "
        for x in self.puzzle:
            print x
        print "Solution: "
        for x in self.solution:
            print x
        print "Steps: "
        for x in self.steps:
            print x

    # Solve the puzzle with bruteforce
    def recurseHelper(self, puzzle):
        if self.filled == 81:
            return puzzle
        
        x, y = self.nextpos()
        unused = self.possible(x, y)
        if self.unsolvable:
            return False
        for number in unused:
            puzzle[x][y] = number
            self.steps.append(((x, y), number))
            self.filled += 1
            ret = self.recurseHelper(puzzle)
            if ret != False:
                return ret
            del self.steps[len(self.steps) - 1]
            self.filled -= 1

        puzzle[x][y] = '0'
        return False
        
    def recurse(self):
        return self.recurseHelper(self.solution)
    
    def nextpos(self):
        max = -1
        pos = (-1, -1)
        for x in xrange(0, 9):
            for y in xrange(0, 9):
                if self.solution[x][y] == '0':
                    count = self.count(x, y)
                    if count > max:
                        pos = (x, y)
                        max = count
        return pos
   
    def count(self, x, y):
        count = 0
        # Count the amount of numbers already filled in in the row.
        for char in self.solution[x]:
            if char != '0':
                count+=1
        # in the column
        for n in xrange(0, len(self.solution)):
            if self.solution[n][y] != '0':
                count+=1
        x1 = int((x / 3)) * 3
        x2 = x1 + 3
        y1 = int((y / 3)) * 3
        y2 = y1 + 3

        # in the same section
        for xit in xrange(x1, x2):
            for yit in xrange(y1, y2):
                if self.solution[xit][yit] != '0':
                    count+=1

        return count


    # Find all possible numbers that are valid for cell x,y
    def possible(self, x, y):
        unusedrow = {}
        unusedcol = {}
        unusedbox = {}
        # Find our region numbers
        x1 = int((x / 3)) * 3
        x2 = x1 + 3
        y1 = int((y / 3)) * 3
        y2 = y1 + 3
        
        for n in xrange(1, 10):
            unusedrow[str(n)] = True
            unusedcol[str(n)] = True
            unusedbox[str(n)] = True
        for char in self.solution[x]:
            if char != '0':
                if unusedrow[char] == False:
                    self.unsolvable = True
                unusedrow[char] = False 
        # in the column
        for n in xrange(0, len(self.solution)):
            char = self.solution[n][y]
            if char != '0':
                if unusedcol[char] == False:
                    self.unsolvable = True
                unusedcol[char] = False 

        # In the region
        for xit in xrange(x1, x2):
            for yit in xrange(y1, y2):
                char = self.solution[xit][yit]
                if char != '0':
                    if unusedbox[char] == False:
                        self.unsolvable = True
                    unusedbox[char] = False

        # read our array of bools and make a list of unused to return
        ret = []
        for x in unusedrow:
            if unusedrow[x] and unusedcol[x] and unusedbox[x]:
                ret.append(x)
    
        ret.sort()

        return ret

# Open the file named 'puzzle' and solve the sudoku puzzle within
if __name__ == "__main__":
    solver = SudokuSolver()
    lines = open("puzzle").readlines()
    puzzle = []
    for line in lines:
        line = line.strip()
        linecells = []
        for char in line:
            linecells.append(char)
        puzzle.append(linecells)
    solver.solve(puzzle)
    solver.output()