Public feed
#376526
## Sudoku Solver## Siraj Mithoowani## Feb. 7 '07from copy import deepcopyfrom time import timenumSolutions = 0def 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 knownValuesdef 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 knownValuesdef 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 knownValuesdef 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 simplifieddef 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 simplifieddef 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 simplifieddef 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 simplifieddef 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 Falsedef 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 Truedef 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 tabledef 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()