# Sudoku Solver
# 7th July 2006

def printDebug(message):
    """This just prints out the message. To turn off debugging, just comment it out"""

    print message    

def loadPuzzle():
    """Opens sudoku.txt which should contain a sudoku puzzle with x where the number is unknown
    Returns a multi-dimensional dictionary with sudoku square values"""

    f = open("E:/Documents/Python/sudoku.txt", "r")
    lines = f.readlines()

    # We want to create a multi-dimensional dictionary with the first key being the row
    # and the next key being the column
    puzzle = {}
    for i in range(0, 9):
        line = lines[i]
        puzzle[i] = {}
        for j in range(0, 9):
            puzzle[i][j] = line[j]

    return puzzle

def solveSquare(puzzle, x, y):
    """Attempts to solve a square in the sudoku"""
    
    # We try to solve the value of the square by process of elimination
    solutions = range(1,10)
    
    # First we eliminate numbers on this row
    row = puzzle[x]
    for i in range(0, 9): # Loops through each value in the row
        value = row[i]
        if value != 'x':
            value = int(value)
            if value in solutions:
                solutions.remove(value)

    # Then we eliminate numbers on this column
    for i in range(0, 9):
        value = puzzle[i][y]
        if value != 'x':
            value = int(value)
            if value in solutions:
                solutions.remove(value)

    # This is a bit more difficult, find all the values in this 3x3 block
    if x < 3:
        sx = [0,1,2]
    elif x < 6:
        sx = [3,4,5]
    else:
        sx = [6,7,8]

    if y < 3:
        sy = [0,1,2]
    elif y < 6:
        sy = [3,4,5]
    else:
        sy = [6,7,8]

    for i in sx:
        row = puzzle[i]
        for j in sy:
            value = row[j]
            if value != 'x':
                value = int(value)
                if value in solutions:
                    solutions.remove(value)

    # If we have one single solution, return it and have it filled in
    if len(solutions) == 1:
        printDebug('Solved square ('+str(x)+','+str(y)+') Solution: '+str(solutions[0]))
        return solutions[0]
    else:
        return False

def countBlanks(puzzle):
    """Returns the number of blank squares in the sudoku."""

    blanks = 0    

    for i in range(0, 9): # Loops through every row    
        row = puzzle[i]
        for j in range(0, 9): # Loops through each value in the row
            value = row[j]
            if (value == 'x'):
                blanks = blanks + 1

    return blanks                
                
def passPuzzle(puzzle):
    """Passes through the sudoku trying to solve possible squares"""

    # This is a pretty crappy algorithm and could probably improved in a million
    # ways, but it will do for this exercise

    for i in range(0, 9): # Loops through every row
        row = puzzle[i]
        for j in range(0, 9): # Loops through each value in the row
            value = row[j]
            if value == 'x': # We only need to try and solve it if the value is unknown (e.g. x)
                s = solveSquare(puzzle,i,j)
                if (s):
                    puzzle[i][j] = s

    return puzzle

def exportPuzzle(puzzle):
    """Prints the puzzle out as a string"""
    e = ''

    for i in range(0, 9): # Loops through every row
        row = puzzle[i]
        for j in range(0, 9): # Loops through each value in the row
            e = e+str(row[j])
        e = e+"\n"

    print e        

sudoku = loadPuzzle()

c = True
passn = 0
b=0

while c:
    passn = passn+1
    
    passPuzzle(sudoku)
    if countBlanks(sudoku) != b:
        b = countBlanks(sudoku)
        printDebug('Pass #'+str(passn)+', '+str(b)+' squares unsolved')

        if b == 0:
            c = False
            exportPuzzle(sudoku)
        else:
            c = True
    else:
        c = False
        printDebug('Pass #'+str(passn)+', '+str(countBlanks(sudoku))+' squares unsolved; terminated')
        exportPuzzle(sudoku)