On 5 July 2013 17:25, MRAB <pyt...@mrabarnett.plus.com> wrote: > For comparison, here's my solution: <CODE>
Unfortunately, there are some sudokus that require guessing - your algorithm will not solve those. A combination algorithm would be best, AFAIK. ----- FWIW, this is my interpretation of the original algorithm: from collections import defaultdict from io import StringIO # For printing DONE = defaultdict(lambda: " ") # How many different numbers can go in each slot, indexes are of the form: [position] NUM_POSSIBILITIES = defaultdict(lambda: 9) # How many times each value has been removed from the possibilities, # indexes are of the form: [value, position] TIMES_REMOVED = defaultdict(lambda: 0) # Set of empty spaces in the grid REMAINING = {(i,j) for i in range(9) for j in range(9)} # Cache, would normally be done inline PLACES_TO_REMOVE = {} for row in range(9): for column in range(9): square_top, square_left = 3*(row // 3), 3*(column // 3) # Across the row PLACES_TO_REMOVE[row, column] = {(p_row, column) for p_row in range(9)} # Across the collumn PLACES_TO_REMOVE[row, column] |= {(row, p_collumn) for p_collumn in range(9)} # Inside the square PLACES_TO_REMOVE[row, column] |= { (p_row, p_collumn) for p_row in range(square_top, 3+square_top) for p_collumn in range(square_left, 3+square_left) } def add_at(value, position): """Add value to the position, updating needed globals""" DONE[position] = value # Use "REMAINING &" so that we only change places we care about # It's reversed in a consistent order to allow this for add_pos in REMAINING & PLACES_TO_REMOVE[position]: # Remove possibility if it hasn't already been removed if not TIMES_REMOVED[value, add_pos]: NUM_POSSIBILITIES[add_pos] -= 1 TIMES_REMOVED[value, add_pos] += 1 REMAINING.remove(position) def remove_at(value, position): """The inverse of add_at""" REMAINING.add(position) # Use "REMAINING &" so that we only change places we care about # It's reversed in a consistent order to allow this for remove_pos in REMAINING & PLACES_TO_REMOVE[position]: TIMES_REMOVED[value, remove_pos] -= 1 # Add posibility back if TIMES_REMOVED falls to 0 if not TIMES_REMOVED[value, remove_pos]: NUM_POSSIBILITIES[remove_pos] += 1 del DONE[position] def read_sudoku(input): number_remaining = 81 # StringIO iterates over lines lines = (line.strip() for line in StringIO(input)) lines = (line for line in lines if line and not line.startswith("#")) for row, line in enumerate(lines): line = line.strip().replace(" ", "").replace("\t", "") for column, character in enumerate(line): if character == "_": pass elif character.isdigit(): add_at(int(character), (row, column)) number_remaining -= 1 else: raise ValueError("Invalid character {} in input line {}".format(character, line)) return number_remaining def print_grid(highlight=None): row_seperator = "¦ · · ¦ · · ¦ · · ¦" special_seperator = "·-----------·-----------·-----------·" seperators = " ¦ ¦ ¦" row_seperators = [special_seperator, row_seperator, row_seperator] * 3 for row, row_seperator in enumerate(row_seperators): print(row_seperator) print("¦", end=" ") for column, seperator in enumerate(seperators): if (row, column) == highlight: # These are colors, ignore 'em if you wish # This is to let you see changes when debugging print("\x1b[31;01m{}\x1b[39;49;00m".format(DONE[row, column]), seperator, end=" ") else: print(DONE[row, column], seperator, end=" ") print() print(special_seperator) print() def solve(number_remaining): if not number_remaining: return True # We need to guess -- go for the one where we have the least choice position = min(REMAINING, key=NUM_POSSIBILITIES.__getitem__) for value in range(1, 10): if not TIMES_REMOVED[value, position]: add_at(value, position) if solve(number_remaining-1): return True remove_at(value, position) return False problem = """ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 3 _ 8 5 _ _ 1 _ 2 _ _ _ _ _ _ _ 5 _ 7 _ _ _ _ _ 4 _ _ _ 1 _ _ _ 9 _ _ _ _ _ _ _ 5 _ _ _ _ _ _ 7 3 _ _ 2 _ 1 _ _ _ _ _ _ _ _ 4 _ _ _ 9 """ solve(read_sudoku(problem)) print_grid() -- http://mail.python.org/mailman/listinfo/python-list