#! /usr/bin/env python
'''Very simple sudoku solver. Based on the method outlined at:

  http://www.instructables.com/id/EJLUBKN48JEPD7QXGR/?ALLSTEPS

It is stated in the comments on that page that this solver will not solve
complex sudoku puzzles where approximately < 25 numbers are on the board.
I haven't found an example of such a board yet though. All of the ones I
can find on the internets labelled "hard" have at least 27 numbers, and
they've been solvable using this code.

In any case, a simple extension would be to add a brute-force solver to the
end of the code in the case where the logic-based solver can do no more.

Version 1.0 by Richard Jones, <richard@mechanicalcat.net> and released
into the Public Domain.
'''

# step 1 - the board
input='''
060104050
008305600
200000001
800407006
006000300
700901004
500000002
007206900
040508070
'''

# step 2 -fill in the "Missing Grid"
board = {}
known = 0
for i,line in enumerate(input.strip().splitlines()):
    for j,cell in enumerate(map(int, line.strip())):
        if not cell: board[i,j] = set(range(1,10))
        else:
            board[i,j] = cell
            known += 1
print 'Solving board, knowing %s cells'%known

def solve(board):
    changed = False
    for i in range(9):
        for j in range(9):
            num = board[i,j]
            if not isinstance(num, int): continue

            # step 3 - Erase "Across"
            for k in range(9):
                cell = board[i,k]
                if isinstance(cell, set) and num in cell:
                    cell.remove(num)
                    if len(cell) == 1:
                        board[i,k] = cell.pop()
                        changed = True
            # step 5 - Erase "All Around"
            imaj = i/3 * 3
            jmaj = j/3 * 3
            for k in range(imaj, imaj + 3):
                for l in range(jmaj, jmaj + 3):
                    cell = board[k,l]
                    if isinstance(cell, set) and num in cell:
                        cell.remove(num)
                        if len(cell) == 1:
                            board[k,l] = cell.pop()
                            changed = True

    for j in range(9):
        for i in range(9):
            num = board[i,j]
            if not isinstance(num, int): continue

            # step 4 - Erase "Down"
            for k in range(9):
                cell = board[k,j]
                if isinstance(cell, set) and num in cell:
                    cell.remove(num)
                    if len(cell) == 1:
                        board[k,j] = cell.pop()
                        changed = True

    # step 8
    for i in range(9):
        for j in range(9):
            cell = board[i,j]
            if not isinstance(cell, set): continue

            # check row for number that only appears in one block
            for num in list(cell):
                for k in range(9):
                    if k == j: continue
                    other_cell = board[i,k]
                    if isinstance(other_cell, set) and num in other_cell:
                        # not unique
                        break
                    if isinstance(other_cell, int) and num == other_cell:
                        # not unique
                        break
                else:
                    board[k,j] = num
                    changed = True
                    break

                # check column for number that only appears in one block
                for k in range(9):
                    if k == i: continue
                    other_cell = board[k,j]
                    if isinstance(other_cell, set) and num in other_cell:
                        break
                    if isinstance(other_cell, int) and num == other_cell:
                        break
                else:
                    board[k,j] = num
                    changed = True
                    break

                # step 8 - look around a quadrant
                imaj = i/3 * 3
                jmaj = j/3 * 3
                for k in range(imaj, imaj + 3):
                    for l in range(jmaj, jmaj + 3):
                        if (k,l) == (i,j): continue
                        other_cell = board[k,l]
                        if isinstance(other_cell, set) and num in other_cell:
                            break
                        if isinstance(other_cell, int) and num == other_cell:
                            break
                    else:
                        # didn't break - keep looking
                        continue
                    break
                else:
                    board[k,j] = num
                    changed = True
                    break

    return changed

def is_solved(board):
    for i in range(9):
        for j in range(9):
            if isinstance(board[i,j], set): return False
    return True

while 1:
    changed = solve(board)
    solved = is_solved(board)
    if not changed:
        break

if solved:
    # display
    print 'SOLVED!'
    for i in range(9):
        print ''.join([str(board[i,j]) for j in range(9)])
else:
    print 'NOT SOLVED!'