aboutsummaryrefslogtreecommitdiffstats
path: root/python
diff options
context:
space:
mode:
authorBryan Brattlof <bryanbrattlof@gmail.com>2019-09-10 17:50:20 -0500
committerBryan Brattlof <bryanbrattlof@gmail.com>2019-09-10 17:50:20 -0500
commit1f03a920288ed566fb79a3a30d7c29bc19b61e41 (patch)
treedf2b0c0f031ff253aff6f00cffaf71bba95d9262 /python
downloadsudoku-1f03a920288ed566fb79a3a30d7c29bc19b61e41.tar.gz
sudoku-1f03a920288ed566fb79a3a30d7c29bc19b61e41.tar.bz2
batman! ... initial commit
Diffstat (limited to 'python')
-rw-r--r--python/sudoku.py134
1 files changed, 134 insertions, 0 deletions
diff --git a/python/sudoku.py b/python/sudoku.py
new file mode 100644
index 0000000..2f481ae
--- /dev/null
+++ b/python/sudoku.py
@@ -0,0 +1,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))