Return to Answer

There should be a puzzle name: puzzle dictionary that is used to search for puzzles. I would also try and format the grid more explicitly.

There should be a puzzle name: puzzle dictionary that is used to search for puzzles. I would also try to format the grid more explicitly.

# encoding: utf8 """ A puzzle-solving masterpiece! Solves Soduko. """ from __future__ import print_function import functools import time from collections import Counter def group_at(row, col): return row // 3 + col // 3 * 3 # The row, column and group number for each item in the grid POSITIONS = tuple((row, col, group_at(row, col)) for row in range(9) for col in range(9)) # The number of bits for each value 0 <= i < 512 BIT_COUNTS = tuple(bin(i).count("1") for i in range(512)) # For looping BITS = tuple(1<<i for i in range(9)) # Inverse of above for printing DECODE_BIT = {1<<i: i+1 for i in range(9)} DECODE_BIT[0] = 0 def find_taken(puzzle): """ Return three lists of what numbers are taken in each row, column and group and one list of which positions (row, column, group) are untaken. """ rows = [0] * 9 columns = [0] * 9 groups = [0] * 9 untaken = [] for position, bit in zip(POSITIONS, puzzle): if bit: row, column, group = position rows[row] |= bit columns[column] |= bit groups[group] |= bit else: untaken.append(position) return rows, columns, groups, untaken def get_next_moves(puzzle): """ Return the (index, missing_values) pair with the fewest possible moves. index is an integer 0 <= index < 81 and missing_values is a bitset of length 9. Returns None if there are no candidate moves. """ rows, columns, groups, untaken = find_taken(puzzle) other_option = None len_option = 9 for row, column, group in untaken: missing_values = 0b111111111 & ~rows[row] & ~columns[column] & ~groups[group] set_bits = BIT_COUNTS[missing_values] if set_bits == 1: return 9*row+column, missing_values elif set_bits < len_option: len_option = set_bits other_option = 9*row+column, missing_values return other_option def possible_moves(puzzle, index, moves): """ Yield the states of the grid for after taking the given moves at index on puzzle. index is an integer 0 <= index < 81 and moves is a bitset of length 9. """ for bit in BITS: if moves & bit: yield puzzle[:index] + (bit,) + puzzle[index + 1:] def validate(puzzle): """ Validate that the puzzle contains 9 of each number and is length 81. This does not fully validate that the solution is valid. """ return Counter(puzzle) == dict.fromkeys(BITS, 9) def depth_first_search(puzzle): """ Do a depth-first search of the solution space for the input Soduku puzzle. Yields solutions. May yield duplicates. """ stack = [puzzle] while stack: vertex = stack.pop() if 0 not in vertex: assert validate(vertex) yield vertex else: stack.extend(possible_moves(vertex, *get_next_moves(vertex))) def print_grid(puzzle): """ Print a pretty representation of the input Soduku puzzle. """ for i, bit in enumerate(puzzle, 1): value = DECODE_BIT[bit] or "·" if i % 9 == 0: print(value) else: print(value, end="") if i % 9 and not i % 3: print(" ", end="") if i == 27 or i == 54: print() def main(puzzle_name): _ = 0 puzzles = { 'easy': [ 5,3,_, _,7,_, _,_,_, 6,_,_, 1,9,5, _,_,_, _,9,8, _,_,_, _,6,_, 8,_,_, _,6,_, _,_,3, 4,_,_, 8,_,3, _,_,1, 7,_,_, _,2,_, _,_,6, _,6,_, _,_,_, 2,8,_, _,_,_, 4,1,9, _,_,5, _,_,_, _,8,_, _,7,9, ], 'hard': [ 8,_,_, _,_,_, _,_,_, _,_,3, 6,_,_, _,_,_, _,7,_, _,9,_, 2,_,_, _,5,_, _,_,7, _,_,_, _,_,_, _,4,5, 7,_,_, _,_,_, 1,_,_, _,3,_, _,_,1, _,_,_, _,6,8, _,_,8, 5,_,_, _,1,_, _,9,_, _,_,_, 4,_,_, ] } grid = tuple(i and 1<<(i-1) for i in puzzles[puzzle_name]) print("Puzzle:") print_grid(grid) for _ in range(10): [result] = set(depth_first_search(grid)) print() print("Result:") print_grid(result) if __name__ == '__main__': main('hard') 

# encoding: utf8 """ A puzzle-solving masterpiece! Solves Soduko. """ from __future__ import print_function import functools import time from collections import Counter def group_at(row, col): return row // 3 + col // 3 * 3 # The row, column and group number for each item in the grid POSITIONS = tuple((row, col, group_at(row, col)) for row in range(9) for col in range(9)) # The number of bits for each value 0 <= i < 512 BIT_COUNTS = tuple(bin(i).count("1") for i in range(512)) # For looping BITS = tuple(1<<i for i in range(9)) # Inverse of above for printing DECODE_BIT = {1<<i: i+1 for i in range(9)} DECODE_BIT[0] = 0 def find_taken(puzzle): """ Return three lists of what numbers are taken in each row, column and group and one list of which positions (row, column, group) are untaken. """ rows = [0] * 9 columns = [0] * 9 groups = [0] * 9 untaken = [] for position, bit in zip(POSITIONS, puzzle): if bit: row, column, group = position rows[row] |= bit columns[column] |= bit groups[group] |= bit else: untaken.append(position) return rows, columns, groups, untaken def get_next_moves(puzzle): """ Return the (index, missing_values) pair with the fewest possible moves. index is an integer 0 <= index < 81 and missing_values is a bitset of length 9. Returns None if there are no candidate moves. """ rows, columns, groups, untaken = find_taken(puzzle) other_option = None len_option = 9 for row, column, group in untaken: missing_values = 0b111111111 & ~rows[row] & ~columns[column] & ~groups[group] set_bits = BIT_COUNTS[missing_values] if set_bits == 1: return 9*row+column, missing_values elif set_bits < len_option: len_option = set_bits other_option = 9*row+column, missing_values return other_option def possible_moves(puzzle, index, moves): """ Yield the states of the grid for after taking the given moves at index on puzzle. index is an integer 0 <= index < 81 and moves is a bitset of length 9. """ for bit in BITS: if moves & bit: yield puzzle[:index] + (bit,) + puzzle[index + 1:] def validate(puzzle): """ Validate that the puzzle contains 9 of each number and is length 81. This does not fully validate that the solution is valid. """ return Counter(puzzle) == dict.fromkeys(BITS, 9) def depth_first_search(puzzle): """ Do a depth-first search of the solution space for the input Soduku puzzle. Yields solutions. May yield duplicates. """ stack = [puzzle] while stack: vertex = stack.pop() if 0 not in vertex: assert validate(vertex) yield vertex else: stack.extend(possible_moves(vertex, *get_next_moves(vertex))) def print_grid(puzzle): """ Print a pretty representation of the input Soduku puzzle. """ for i, bit in enumerate(puzzle, 1): value = DECODE_BIT[bit] or "·" if i % 9 == 0: print(value) else: print(value, end="") if i % 9 and not i % 3: print(" ", end="") if i == 27 or i == 54: print() def main(puzzle_name): _ = 0 puzzles = { 'easy': [ 5,3,_, _,7,_, _,_,_, 6,_,_, 1,9,5, _,_,_, _,9,8, _,_,_, _,6,_, 8,_,_, _,6,_, _,_,3, 4,_,_, 8,_,3, _,_,1, 7,_,_, _,2,_, _,_,6, _,6,_, _,_,_, 2,8,_, _,_,_, 4,1,9, _,_,5, _,_,_, _,8,_, _,7,9, ], 'hard': [ 8,_,_, _,_,_, _,_,_, _,_,3, 6,_,_, _,_,_, _,7,_, _,9,_, 2,_,_, _,5,_, _,_,7, _,_,_, _,_,_, _,4,5, 7,_,_, _,_,_, 1,_,_, _,3,_, _,_,1, _,_,_, _,6,8, _,_,8, 5,_,_, _,1,_, _,9,_, _,_,_, 4,_,_, ] } grid = tuple(i and 1<<(i-1) for i in puzzles[puzzle_name]) print("Puzzle:") print_grid(grid) [result] = set(depth_first_search(grid)) print() print("Result:") print_grid(result) if __name__ == '__main__': main('hard') 

• Try returning early,

• Raise an exception if not win, as you would have entered an invalid state.

• Don't use the top-level Exception type; use more precise variants.

  def depth_first_search(start): stack = [start] solution = None

   while stack: vertex = stack.pop() if 0 not in vertex: assert win(vertex) if solution and vertex != solution: raise ValueError("More than one solution") solution = vertex else: stack.extend(possible_moves(vertex)) if solution is None: raise ValueError("No solution found") return solution 

• Try returning early,
• Raise an exception if not win, as you would have entered an invalid state.
• Don't use the top-level Exception type; use more precise variants.

def depth_first_search(start): stack = [start] solution = None while stack: vertex = stack.pop() if 0 not in vertex: assert win(vertex) if solution and vertex != solution: raise ValueError("More than one solution") solution = vertex else: stack.extend(possible_moves(vertex)) if solution is None: raise ValueError("No solution found") return solution