aboutsummaryrefslogtreecommitdiffstats
path: root/python/sudoku.py
blob: 2f481aeb0336521620f8ff4e2130726d6498f93f (plain) (blame)
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
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
from itertools import product
import sys


def inRow(i, j):
    """is position 'i' in the same row as position 'j'"""
    return i//9 == j//9


def inCol(i, j):
    """is position 'i' in the same column as position 'j'"""
    return (i - j) % 9 == 0


def inBox(i, j):
    """is position 'i' in the same sub 3x3 box as position 'j'"""
    return (i//27 == j//27) and (i % 9//3 == j % 9//3)


"""
'peers' holds all the indexes of cells that influences the
possibilities the given cell can be.
"""
peers = {i: [] for i in range(81)}
for i, j in product(range(81), range(81)):
    if i == j:
        continue
    if any(f(i, j) for f in (inRow, inCol, inBox)):
        peers[i].append(j)
"""
eg: peers[0]

  [X] X  X | X  X  X | X  X  X
   X  X  X | .  .  . | .  .  .
   X  X  X | .  .  . | .  .  .
  ---------+---------+---------
   X  .  . | .  .  . | .  .  .
   X  .  . | .  .  . | .  .  .
   X  .  . | .  .  . | .  .  .
  ---------+---------+---------
   X  .  . | .  .  . | .  .  .
   X  .  . | .  .  . | .  .  .
   X  .  . | .  .  . | .  .  .

"""


def init(matrix):
    """replace unanswered cells with the possibilities they could be"""
    new_matrix = list(matrix)
    for i, cell in filter(lambda x: x[1] == '0', enumerate(new_matrix)):
        new_matrix[i] = ''.join(constraint(matrix, i))
    return new_matrix


def constraint(matrix, cell_index):
    """return all possibilities for the given cell"""
    return set('123456789') - set(matrix[j] for j in peers[cell_index])


def search(matrix):
    """return an unanswered cell with the least number possibilities"""
    try:
        _, i = min((len(n), i) for i, n in enumerate(matrix) if len(n) > 1)
    except ValueError:
        return False  # we solved it
    return i


def eliminate(matrix, index, value):
    """remove the possibility from the cell and it's peers"""
    if value not in matrix[index]:
        return matrix  # we've already eliminated it

    matrix[index] = matrix[index].replace(value, '')
    num_possibilities = len(matrix[index])

    # if we've eliminated all the possibilities
    # for this cell, we need to backtrack
    if num_possibilities == 0:
        return False

    # if this is the last option for this cell, go ahead
    # and assign it and eliminate that value for it's peers
    if num_possibilities == 1:
        another_value = matrix[index]
        if not all(eliminate(matrix, i, another_value) for i in peers[index]):
            return False  # eliminating that value caused us to backtrack

    return matrix


def assign(matrix, index, value):
    """remove all possibilities except the given value"""
    if all(eliminate(matrix, index, v) for v in matrix[index] if v != value):
        return matrix
    return False


def solve(matrix):
    """
    use recursion until we get to a state where we need to backtrack
    or, return the result after we've filled all cells
    """
    # what cell should we work on next
    index = search(matrix)
    if index is False:
        return matrix  # we've solved it

    # loop through all the possibilities the cell could be
    for possibility in matrix[index]:
        matrix_copy = assign(matrix.copy(), index, possibility)
        if matrix_copy is False:
            continue  # ran into an impossibility, try another number

        # might be possible, try to solve another cell
        result = solve(matrix_copy)
        if result is not False:
            return result

    return False


if __name__ == '__main__':
    """solve each unanswered Sudoku puzzles"""
    for puzzle in sys.argv[1:]:

        # replace unanswered cells with the possible
        # numbers the cell could be
        init_puzz = init(puzzle)

        # solve and print the possibilities
        solved_puzz = solve(init_puzz)
        print(''.join(solved_puzz))