Welcome, guest | Sign In | My Account | Store | Cart
NOTE: Recipes have moved! Please visit GitHub.com/activestate/code for the current versions.

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)
Python recipes (4591)
Raymond Hettinger's recipes (97)
HongxuChen's Fav (39)

Required Modules

  • (none specified)

Other Information and Tasks