Welcome, guest | Sign In | My Account | Store | Cart

Yet another solver. Uses knowns to eliminate possibilities, then tries assumptions from remaining possibilities (depth-first search with heuristic to first explore cells with the fewest unknowns).

Python, 72 lines
 ``` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72``` ```n = 3 # Size of inner region n2, n3, n4 = n**2, n**3, n**4 def show(flatline): 'Display grid from a string (values in row major order with blanks for unknowns)' fmt = '|'.join(['%s' * n] * n) sep = '+'.join(['-' * n] * n) for i in range(n): for j in range(n): offset = (i*n+j)*n2 print fmt % tuple(flatline[offset:offset+n2]) if i != n-1: print sep def _find_friends(cell): 'Return tuple of cells in same row, column, or subgroup' friends = set() row, col = cell // n2, cell % n2 friends.update(row * n2 + i for i in range(n2)) friends.update(i * n2 + col for i in range(n2)) nw_corner = row // n * n3 + col // n * n friends.update(nw_corner + i + j for i in range(n) for j in range(0,n3,n2)) friends.remove(cell) return tuple(friends) friend_cells = map(_find_friends, range(n4)) def select_an_unsolved_cell(possibles, heuristic=min): # Default heuristic: select cell with fewest possibilities # Other possible heuristics include: random.choice() and max() return heuristic((len(p), cell) for cell, p in enumerate(possibles) if len(p)>1)[1] def solve(possibles, pending_marks): # Apply pending_marks (list of cell,value pairs) to possibles (list of str). # Mutates both inputs. Return solution as a flat string (values in row-major order) # or return None for dead-ends where all possibilites have been eliminated. for cell, v in pending_marks: possibles[cell] = v for f in friend_cells[cell]: p = possibles[f] if v in p: p = possibles[f] = p.replace(v, '') # exclude value v from friend f if not p: return None # Dead-end: all possibilities eliminated if len(p) == 1: pending_marks.append((f, p[0])) # Check to see if the puzzle is fully solved (each cell has only one possible value) if max(map(len, possibles)) == 1: return ''.join(possibles) # If it gets here, there are still unsolved cells cell = select_an_unsolved_cell(possibles) for v in possibles[cell]: # try all possible values for that cell ans = solve(possibles[:], [(cell, v)]) if ans is not None: return ans # ----- Examples ----- for given in [ '53 7 6 195 98 6 8 6 34 8 3 17 2 6 6 28 419 5 8 79', ' 75 4 5 8 17 6 36 2 7 1 5 1 1 5 8 96 1 82 3 4 9 48 ', ' 9 7 4 1 6 2 8 1 43 6 59 1 3 97 8 52 7 6 8 4 7 5 8 2 ', '67 38 921 85 736 1 8 4 7 5 1 8 4 2 6 8 5 175 24 321 61 84', '27 15 8 3 7 4 7 5 1 7 9 2 6 2 5 8 6 5 4 8 59 41', ]: show(given) pending_marks = [(i,v) for i, v in enumerate(given) if v != ' '] possibles = ['123456789'] * len(given) result = solve(possibles, pending_marks) print show(result) print '=-' * 20 ```

Data structures: * input is a flat string of cell values (blanks for unknowns) in row-major order * possibles: list of strings -- a string such as "146" means that any of those three values are possible for the cell * friends: list of tuples -- friends[c] lists the 20 other cells in the same row, column, or region as c * pending_marks -- list of (cell, value) pairs to be applied against the remaining possibilities

Algorithm recursively explores the tree depth-first, returning the solution string when found or None when dead-ends are reached.

 Created by Raymond Hettinger on Wed, 15 Feb 2006 (PSF)

### Required Modules

• (none specified)