## Solve Every Sudoku Puzzle ## See http://norvig.com/sudoku.html ################ General useful utilities ################ import time, sys def time_call(function, *args, **keyword_args): "Return the result of applying function to args, and the number of seconds it took." t0 = time.clock() result = function(*args, **keyword_args) elapsed_time = time.clock()-t0 return result, elapsed_time def grouper(n, items): "Group items n at a time: grouper(3, 'abcdefgh') => ['abc', 'def', 'gh']" return [items[i:i+n] for i in range(0, len(items), n)] def side_by_side(*strings): "Concatenate several strings on a line-by-line basis." rows = map(None, *[s.split('\n') for s in strings]) # Transpose rows = [[('' if x is None else x) for x in row] for row in rows] width = 3 + max(len(x) for row in rows for x in row) return '\n'.join(''.join(x.ljust(width) for x in row) for row in rows) ################ Basics ################ ## Throughout this program we adopt these naming conventions: ## r: a row, an integer 0 to 8 (in the case where N=9) ## c: a column, an integer 0 to 8 ## s: a square, an integer 0 to 80 equal to 9*row + col ## d: a digit, a character '1' to '9' ## u: a unit, nine squares in a row, col, or box ##gridstring: a string, with 81 digit-or-empty chars, e.g. starting with '.18...7...' ## grid: a list, of possible values for each square, e.g. ['12349', '8', ...] def cross(Rows, Cols): "All squares in these rows and columns" return [N*r+c for r in Rows for c in Cols] Nbox = 3 # Each box is of size Nbox x Nbox N = Nbox*Nbox # The whole grid is of size N x N rows = range(N) cols = rows blocks = grouper(Nbox, rows) # E.g., [[0, 1, 2], [3, 4, 5], [6, 7, 8]] for N = 9 squares = range(N*N) digits = '123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ!'[:N] # E.g., '123456789' for N = 9 digitset = set(digits) rowunits = [cross([r], cols) for r in rows] colunits = [cross(rows, [c]) for c in cols] boxunits = [cross(rblock, cblock) for rblock in blocks for cblock in blocks] allunits = rowunits + colunits + boxunits units = [[u for u in allunits if s in u] for s in squares] peers = [set(s2 for u in units[s] for s2 in u if s2!=s) for s in squares] ################ Grids, gridstrings, and solutions ################ def is_solution(grid, puzzle): """A grid is a solution to a puzzle if each unit is a permutation of the digits and if the filled squares remain unchanged.""" filled_squares = [s for s in squares if puzzle[s] in digitset] def is_permutation(unit): return set(grid[s] for s in unit) == digitset return (grid is not False and all(is_permutation(u) for u in allunits) and all(grid[s]==puzzle[s] for s in filled_squares)) ################ Search ################ def solve(gridstring): "Parse gridstring, handle initial constraints, and search for a solution." return search(initialize(parse(gridstring))) def initialize(puzzle): """First set each square in the result grid to have the set of all possible digits. Then assign each filled square to the specified digit.""" assert len(puzzle) == N*N grid = N*N * [digits] for s in squares: if puzzle[s] in digitset: grid = assign(grid, s, puzzle[s]) return grid def search(grid): """Select an unfilled square, try each possible value in order, recursively searching. When all squares filled: success; when no more digits to try: return False for failure.""" if grid is False: return False s = select_square(grid) if s is None: return grid for d in possible_values(grid, s): result = search(assign(grid[:], s, d)) if result: return result return False def possible_values(grid, s): return grid[s] def select_square(grid): "Return an unfilled square with the fewest possible digits; or None if no unfilled squares." unfilled = [s for s in squares if len(grid[s]) > 1] return min(unfilled, key=lambda s: len(grid[s])) if unfilled else None def assign(grid, s, d): """Assign grid[s] = d and eliminate d from the peers of s. Return the updated grid, or return False if inconsistency detected.""" if d not in grid[s]: return False # d is not among the possibilities grid[s] = d if not all(eliminate(grid, p, d) for p in peers[s]): return False return grid def eliminate(grid, s, d): "Remove d from possibilities for grid[s]. If checking finds an inconsistency return False." if d not in grid[s]: return grid # Already eliminated d grid[s] = grid[s].replace(d, '') return check(grid, s, d) def check(grid, s, d): return arc_consistent(grid, s) and dual_consistent(grid, s, d) and naked_pairs(grid, s) def arc_consistent(grid, s): "Return true if s has multiple digits left, or one that we can consistently assign." ndigits = len(grid[s]) return ndigits >= 2 or (ndigits == 1 and assign(grid, s, grid[s])) def dual_consistent(grid, s, d): """After eliminating d from grid[s], check each unit of s and make sure there is some position in the unit for d. If only one possible place left for d, assign it.""" for u in units[s]: places_for_d = [s2 for s2 in u if d in grid[s2]] nplaces = len(places_for_d) if nplaces==0 or (nplaces==1 and not assign(grid, places_for_d[0], d)): return False return True def naked_pairs(grid, s): """Look for two squares in a unit with the same two possible digits. For example, if s and s2 both have the value '35', then we know that 3 and 5 must go in those two squares. We don't know which is which, but we can eliminate 3 and 5 from any other square s3 that is in the unit.""" vals = grid[s] if len(vals) != 2: return True for u in units[s]: for s2 in u: if s2 != s and grid[s2] == vals: # Found naked pair: s and s2; remove their two vals from others in unit for s3 in u: if s != s3 != s2: if not all(eliminate(grid, s3, v) for v in vals): return False return True ################ Input/Output and Benchmarks ################ def parse(gridstring): """Convert a string into a grid: a list of values. Accepts digits (or '.' or '0' for empty); all other characters ignored. In result, '.' used for empty.""" gridstring = gridstring.replace('0', '.') return [c for c in gridstring if c in digits or c == '.'] def show(grid): "Convert a grid to a gridstring laid out in 2D, with lines between boxes." return "INCONSISTENCY" if grid is False else show_template.format(*grid) show_dashes = '\n' + '+'.join(['--'*Nbox]*Nbox) + '\n' show_line_of_boxes = '\n'.join(['|'.join(['{} '*Nbox]*Nbox)]*Nbox) show_template = show_dashes.join([show_line_of_boxes]*Nbox) def benchmark(version, filenames=[f for f in sys.argv[1:] if not f.startswith('-')], printit=('-print' in sys.argv)): "Run benchmark puzzles in files and print summary statistics." print "version name N Hz avg max" for name in filenames: times = [time_solve(g, printit=printit) for g in file(name)] n, total = len(times), sum(times) print "{:9}{:9}{:9}{:9}{:9.3f}{:9.3f}".format( version, name.replace('.txt',''), n, int(0.5 + n/total), total/n, max(times)) def time_solve(gridstring, printit=False): "Solve a puzzle; print if printit=True or if solution is invalid. Return time to solution." result, t = time_call(solve, gridstring) solved = is_solution(result, parse(gridstring)) if printit or not solved: print side_by_side(show(parse(gridstring)), show(result), 'Solved' if solved else "**** FAIL ****") + '\n' return t if __name__ == '__main__': import doctest if '-test' in sys.argv: doctest.testfile("sudoku_test.py", optionflags=doctest.NORMALIZE_WHITESPACE) if '-help' in sys.argv: print """usage: python sudoku.py [-test] [-v] [-help] [-print] filename... -test: runs a test suite -v: gives verbose output for the test suite -help: prints this message -print: prints each puzzle and its solution filename...: a list of filenames; each line of each file is a puzzle.""" benchmark('AC+D+NP')