## Sudoku Solver
## Siraj Mithoowani
## Feb. 7 '07

from copy import deepcopy
from time import time
numSolutions = 0

def printSolution (table):
    """
    Prints the solved table.
    """

    global numSolutions
    numSolutions += 1
    for row in table:
        print row
    

def knownsInRows (table, x):
    """
    Finds the 'known values' in rows of the table.
    A value is added to the list knownValues when a spot in the table
    only has ONE possibility.
    """
    
    knownValues = []
    for y in range (9):
        if (len(table[y][x]) == 1):
            knownValues.append(table[y][x])
    return knownValues

def knownsInCols (table, x):
    """
    Finds the 'known values' in columns of the table.
    A value is added to the list knownValues when a spot in the table
    only has ONE possibility.
    """
    
    knownValues = []
    for y in range (9):
        if (len(table[x][y]) == 1):
            knownValues.append(table[x][y])
    return knownValues

def knownsInSquares (table, x, y):
    """
    Finds the 'known values' in squares of the table.
    A value is added to the list knownValues when a spot in the table
    only has ONE possibility.
    """
    
    knownValues = []
    for a in range (3):
        for b in range (3):
            if len(table[x+a][y+b]) == 1:
                knownValues.append(table[x+a][y+b])
    return knownValues

def elimKnownValues (knownValues, squareValues):
    """
    Eliminates known values from an unsimplified square in the table.
    """
    
    simplified = 0
    for value in knownValues:
        if value in squareValues:
            del squareValues[squareValues.index(value)]
            simplified += 1
    return simplified

def examineRows (table):
    """
    Rules out possibilities by examining the ROWS of the table.
    Returns the number of possibilities the function eliminated.
    """
    
    simplified = 0
    for x in range (9):
        squareValues = []
        knownValues = knownsInRows(table, x)
        for y in range (9):
            if (len(table[y][x]) > 1):
                squareValues = list(table[y][x])
                simplified += elimKnownValues(knownValues, squareValues)
                table[y][x] = ''.join(squareValues)
    return simplified

def examineColumns (table):
    """
    Rules out possibilities by examining the COLUMNS of the table.
    Returns the number of possibilities the function eliminated.
    """
    
    simplified = 0
    for x in range (9):
        squareValues = []
        knownValues = knownsInCols(table, x)
        for y in range (9):
            if (len(table[x][y]) > 1):
                squareValues = list(table[x][y])
                simplified += elimKnownValues(knownValues, squareValues)
                table[x][y] = ''.join(squareValues)
    return simplified

def examineSquares (table):
    """
    Rules out possibilities by examining the SQUARES of the table.
    Returns the number of possibilities the function eliminated.
    """
    
    simplified = 0
    for x in range (0, 8, 3):
        for y in range (0, 8, 3):
            squareValues = []
            knownValues = knownsInSquares(table, x, y)
            for a in range (3):
                for b in range(3):
                    if len(table[x+a][y+b]) > 1:
                        squareValues = list(table[x+a][y+b])
                        simplified += elimKnownValues(knownValues, squareValues)
                        table[x+a][y+b] = ''.join(squareValues)
    return simplified

def findSimplestBox (table):
    """
    Finds box with the lowest number of possible values, and returns
    the coordinates of that box in the table. If a valid box
    is not found, the coordinates (-1,-1) are returned.
    """
    
    r,c = -1, -1
    shortest = 10
    for row in range(len(table)):
        for col in range (len(table)):
            if 1 < len(table[row][col]) < shortest:
                shortest = len(table[row][col])
                r = row
                c = col
    return (r,c)

def simplify (table):
    """
    Loops the simplification procedure until the puzzle can't be simplified
    any further.
    """
    
    while True:
        eliminated = 0
        eliminated += examineRows(table)
        eliminated += examineColumns(table)
        eliminated += examineSquares(table)
        if eliminated == 0:
            break 

def solved (table):
    """
    Checks if puzzle is solved.
    The puzzle is 'solved' if each spot in the grid contains only one value.
    """
    
    counter = 0
    for row in table:
        for box in row:
            if len(box) == 1:
                counter += 1
    if counter == 81:
        return True
    else:
        return False

def valid (table):
    """
    Check if Sudoku table can still be simplified, or whether it has to
    be discarded, due to a wrong entry. If the table has values
    that are EMPTY, or it has duplicate values in a row, column, or square,
    it is considered to be unsolvable (function returns False),
    and is therefore discarded.
    """
    
    # Look for spots in grid that are empty (that can't be filled for any
    # number, 1-9).
    for row in table:
        for box in row:
            if len(box) == 0:
                return False

    # Look for duplicate values in squares.      
    for x in range (0, 8, 3):
        for y in range (0, 8, 3):
            knownValues = knownsInSquares(table, x, y)
            temp = set(knownValues)
            if (len(temp)) != len(knownValues):
                return False

    # Look for duplicate values in rows.        
    for x in range(9):
        knownValues = knownsInRows(table, x)
        temp = set(knownValues)
        if (len(temp)) != len(knownValues):
            return False

        # Look for duplicate values in columns.
        knownValues = knownsInCols(table, x)
        temp = set(knownValues)
        if (len(temp)) != len(knownValues):
            return False
        
    return True

def initTable ():
    """
    Reads known values from a textfile called "puzzle.txt" which is
    placed in the same folder as the script and fills the values into
    the Sudoku grid. A value of "0" in the text file is an unknown
    value, and is therefore filled as "123456789" in the Sudoku table.
    """
    
    # Initialize 2D array to represent Sudoku grid.
    # "123456789" values are 'unknown' squares.
    table = [["123456789"]*9 for x in range (9)]
    
    f = open("puzzle.txt","r")
    for row in range(9):
        line = f.readline()
        for column in range (9):
            if line[column] == "0":
                table[row][column] = "123456789"
            else:
                table[row][column] = line[column]

    return table

def solve (table):
    """
    Recursive algorithm which solves the Sudoku puzzle.
    """
    
    # Finds the 'simplest' box in the puzzle,
    # (one with the least number of possibilities).
    r, c = findSimplestBox(table)

    # If a simple box is not found, r and c are returned as -1.
    # This occurs when the puzzle is already solved by the time
    # the solve() function is called.
    if r != -1 and c != -1:
        for possibility in table[r][c]:
            newTable = deepcopy(table)
            newTable[r][c] = possibility
            simplify(newTable)
            if (solved(newTable) and valid(newTable)):
                print "Solution:"
                printSolution (newTable)
                print
                break
            else:
                # Only continue the solving procedure of the puzzle
                # if it's still valid (solvable).
                if valid(newTable):
                    solve(newTable)
    else:
        if (valid(table)):
            print "Solution:"
            printSolution(table)
            print
         
def main ():
    """
    Main program.
    """
    
    time1 = time()
    table = initTable()
    simplify(table)
    solve(table)
    time2 = time()
    
    print "Found a total of",numSolutions,"solution(s)."
    print "Time taken for solution(s):",round(time2-time1, 3),"seconds."
    raw_input("Press <enter> to quit.")
    
if __name__ == "__main__":
    main()