from itertools import product import sys def inRow(i, j): """is position 'i' in the same row as position 'j'""" return i//9 == j//9 def inCol(i, j): """is position 'i' in the same column as position 'j'""" return (i - j) % 9 == 0 def inBox(i, j): """is position 'i' in the same sub 3x3 box as position 'j'""" return (i//27 == j//27) and (i % 9//3 == j % 9//3) """ 'peers' holds all the indexes of cells that influences the possibilities the given cell can be. """ peers = {i: [] for i in range(81)} for i, j in product(range(81), range(81)): if i == j: continue if any(f(i, j) for f in (inRow, inCol, inBox)): peers[i].append(j) """ eg: peers[0] [X] X X | X X X | X X X X X X | . . . | . . . X X X | . . . | . . . ---------+---------+--------- X . . | . . . | . . . X . . | . . . | . . . X . . | . . . | . . . ---------+---------+--------- X . . | . . . | . . . X . . | . . . | . . . X . . | . . . | . . . """ def init(matrix): """replace unanswered cells with the possibilities they could be""" new_matrix = list(matrix) for i, cell in filter(lambda x: x[1] == '0', enumerate(new_matrix)): new_matrix[i] = ''.join(constraint(matrix, i)) return new_matrix def constraint(matrix, cell_index): """return all possibilities for the given cell""" return set('123456789') - set(matrix[j] for j in peers[cell_index]) def search(matrix): """return an unanswered cell with the least number possibilities""" try: _, i = min((len(n), i) for i, n in enumerate(matrix) if len(n) > 1) except ValueError: return False # we solved it return i def eliminate(matrix, index, value): """remove the possibility from the cell and it's peers""" if value not in matrix[index]: return matrix # we've already eliminated it matrix[index] = matrix[index].replace(value, '') num_possibilities = len(matrix[index]) # if we've eliminated all the possibilities # for this cell, we need to backtrack if num_possibilities == 0: return False # if this is the last option for this cell, go ahead # and assign it and eliminate that value for it's peers if num_possibilities == 1: another_value = matrix[index] if not all(eliminate(matrix, i, another_value) for i in peers[index]): return False # eliminating that value caused us to backtrack return matrix def assign(matrix, index, value): """remove all possibilities except the given value""" if all(eliminate(matrix, index, v) for v in matrix[index] if v != value): return matrix return False def solve(matrix): """ use recursion until we get to a state where we need to backtrack or, return the result after we've filled all cells """ # what cell should we work on next index = search(matrix) if index is False: return matrix # we've solved it # loop through all the possibilities the cell could be for possibility in matrix[index]: matrix_copy = assign(matrix.copy(), index, possibility) if matrix_copy is False: continue # ran into an impossibility, try another number # might be possible, try to solve another cell result = solve(matrix_copy) if result is not False: return result return False if __name__ == '__main__': """solve each unanswered Sudoku puzzles""" for puzzle in sys.argv[1:]: # replace unanswered cells with the possible # numbers the cell could be init_puzz = init(puzzle) # solve and print the possibilities solved_puzz = solve(init_puzz) print(''.join(solved_puzz))