From b36b76eb55ec364249fcba8661c58137ab400465 Mon Sep 17 00:00:00 2001 From: "W. Trevor King" Date: Thu, 7 Oct 2010 07:38:35 -0400 Subject: [PATCH] Added Python sudoku solution. --- assignments/archive/sudoku/1.cfg | 27 +-- assignments/archive/sudoku/2.cfg | 27 +-- assignments/archive/sudoku/3.cfg | 27 +-- assignments/archive/sudoku/soln/sudoku.py | 265 ++++++++++++++++++++++ 4 files changed, 292 insertions(+), 54 deletions(-) create mode 100755 assignments/archive/sudoku/soln/sudoku.py diff --git a/assignments/archive/sudoku/1.cfg b/assignments/archive/sudoku/1.cfg index 2fd0850..abdfa45 100644 --- a/assignments/archive/sudoku/1.cfg +++ b/assignments/archive/sudoku/1.cfg @@ -1,20 +1,11 @@ +- - - - 2 8 - 5 - +- 7 4 6 1 - 2 8 - +- - 2 - 7 - 9 - 1 - - - - - 2 8 - 5 - +- 8 - - - - 3 9 5 +- - 5 7 - 6 1 - - +3 4 1 - - - - 2 - - - 7 4 6 1 - 2 8 - - - - - 2 - 7 - 9 - 1 - - - - 8 - - - - 3 9 5 - - - - 5 7 - 6 1 - - - - 3 4 1 - - - - 2 - - - - 4 - 9 - 8 - 5 - - - - - 2 8 - 5 3 6 7 - - - - 5 - 4 6 - - - - +4 - 9 - 8 - 5 - - +- 2 8 - 5 3 6 7 - +- 5 - 4 6 - - - - diff --git a/assignments/archive/sudoku/2.cfg b/assignments/archive/sudoku/2.cfg index 714a72a..69637bd 100644 --- a/assignments/archive/sudoku/2.cfg +++ b/assignments/archive/sudoku/2.cfg @@ -1,20 +1,11 @@ +- 6 - - 3 - - - - +- 3 1 9 - 8 - 5 - +2 7 - - - - 6 3 - - - 6 - - 3 - - - - +- - - - 9 1 - - 3 +- 1 - - 2 - - 9 - +9 - - 6 8 - - - - - - 3 1 9 - 8 - 5 - - - 2 7 - - - - 6 3 - - - - - - - - 9 1 - - 3 - - - 1 - - 2 - - 9 - - - 9 - - 6 8 - - - - - - - - 9 6 - - - - 4 7 - - - 4 - 2 - 9 5 6 - - - - - - - 1 - - 8 - +- 9 6 - - - - 4 7 +- 4 - 2 - 9 5 6 - +- - - - 1 - - 8 - diff --git a/assignments/archive/sudoku/3.cfg b/assignments/archive/sudoku/3.cfg index 2e21724..6e0b048 100644 --- a/assignments/archive/sudoku/3.cfg +++ b/assignments/archive/sudoku/3.cfg @@ -1,20 +1,11 @@ +- 2 - - - - 6 - 9 +3 - - 9 - 4 - 5 - +- - - 8 1 - - - - - - 2 - - - - 6 - 9 +6 - - 5 - - - 1 - +8 1 - 3 - 9 - 6 5 +- 4 - - - 1 - - 3 - 3 - - 9 - 4 - 5 - - - - - - 8 1 - - - - - - - 6 - - 5 - - - 1 - - - 8 1 - 3 - 9 - 6 5 - - - 4 - - - 1 - - 3 - - - - - - - 7 6 - - - - - - 6 - 4 - 5 - - 8 - - 9 - 1 - - - - 7 - +- - - - 7 6 - - - +- 6 - 4 - 5 - - 8 +9 - 1 - - - - 7 - diff --git a/assignments/archive/sudoku/soln/sudoku.py b/assignments/archive/sudoku/soln/sudoku.py new file mode 100755 index 0000000..126664f --- /dev/null +++ b/assignments/archive/sudoku/soln/sudoku.py @@ -0,0 +1,265 @@ +#!/usr/bin/env python + +import numpy + + +class Sudoku (object): + r""" + >>> puzzle = '\n'.join([ + ... '5 3 - - 7 - - - -', + ... '6 - - 1 9 5 - - -', + ... '- 9 8 - - - - 6 -', + ... '', + ... '8 - - - 6 - - - 3', + ... '4 - - 8 - 3 - - 1', + ... '7 - - - 2 - - - 6', + ... '', + ... '- 6 - - - - 2 8 -', + ... '- - - 4 1 9 - - 5', + ... '- - - - 8 - - 7 9', + ... ]) + >>> s = Sudoku() + >>> s.load(puzzle) + >>> s._num_solved() + 30 + >>> s.solve() + >>> print s.status + solved in 408 steps + >>> print s.dump() + 5 3 4 6 7 8 9 1 2 + 6 7 2 1 9 5 3 4 8 + 1 9 8 3 4 2 5 6 7 + + 8 5 9 7 6 1 4 2 3 + 4 2 6 8 5 3 7 9 1 + 7 1 3 9 2 4 8 5 6 + + 9 6 1 5 3 7 2 8 4 + 2 8 7 4 1 9 6 3 5 + 3 4 5 2 8 6 1 7 9 + >>> s._num_solved() + 81 + + >>> s._row(0) + array([5, 3, 4, 6, 7, 8, 9, 1, 2]) + >>> s._col(0) + array([5, 6, 1, 8, 4, 7, 9, 2, 3]) + >>> s._cell(0,0) + array([[5, 3, 4], + [6, 7, 2], + [1, 9, 8]]) + """ + def __init__(self): + self._puzzle = numpy.zeros((9,9), dtype=numpy.int) + self._empty = 0 + self._external_empty = '-' + self.status = None + + def load(self, text): + row = 0 + for line in text.splitlines(): + if len(line) == 0 or line.startswith('#'): + continue + assert row < 9, row + for col,value in enumerate(line.split()): + assert col < 9, col + self._puzzle[row,col] = self._convert_to_internal_value(value) + row += 1 + self.status = 'loaded puzzle' + + def _convert_to_internal_value(self, value): + """ + >>> s = Sudoku() + >>> s._convert_to_internal_value(s._external_empty) + 0 + >>> s._convert_to_internal_value('0') + Traceback (most recent call last): + ... + AssertionError: 0 + >>> s._convert_to_internal_value('1') + 1 + >>> s._convert_to_internal_value('9') + 9 + >>> s._convert_to_internal_value('10') + Traceback (most recent call last): + ... + AssertionError: 10 + """ + if value == self._external_empty: + value = self._empty + else: + value = int(value) + assert value >= 1 and value <= 9, value + return value + + def dump(self): + lines = [] + for row in range(9): + if row in [3, 6]: + lines.append('') # blank rows between cells + line = [] + for col in range(9): + if col in [3, 6]: + line.append(' ') # blank columns between cells + line.append(self._convert_to_external_value( + self._puzzle[row,col])) + lines.append(' '.join(line)) + return '\n'.join(lines) + + def _convert_to_external_value(self, value): + """ + >>> s = Sudoku() + >>> s._convert_to_external_value(s._empty) + '-' + >>> s._convert_to_external_value(1) + '1' + >>> s._convert_to_external_value(9) + '9' + """ + if value == self._empty: + value = self._external_empty + else: + assert value >= 1 and value <= 9, value + value = str(value) + return value + + def _row(self, row): + return self._puzzle[row,:] + + def _col(self, col): + return self._puzzle[:,col] + + def _cell(self, cell_row, cell_col): + ri = cell_row * 3 + rf = ri + 3 + ci = cell_col * 3 + cf = ci + 3 + return self._puzzle[ri:rf,ci:cf] + + def _nonempty(self, values): + return [x for x in values if x != self._empty] + + def _is_valid(self): + r""" + >>> puzzle = '\n'.join([ + ... '5 3 - - 7 - - - -', + ... '6 - - 1 9 5 - - -', + ... '- 9 8 - - - - 6 -', + ... '', + ... '8 - - - 6 - - - 3', + ... '4 - - 8 - 3 - - 1', + ... '7 - - - 2 - - - 6', + ... '', + ... '- 6 - - - - 2 8 -', + ... '- - - 4 1 9 - - 5', + ... '- - - - 8 - - 7 9', + ... ]) + >>> s = Sudoku() + >>> s.load(puzzle) + >>> s._is_valid() + True + + Test an invalid row. + + >>> s._puzzle[0,3] = 5 + >>> s._is_valid_row(0) + False + >>> s._is_valid() + False + >>> s._puzzle[0,3] = s._empty + + Test an invalid column. + + >>> s._puzzle[8,0] = 5 + >>> s._is_valid_col(0) + False + >>> s._is_valid() + False + >>> s._puzzle[8,0] = s._empty + + Test and invalid cell. + + >>> s._puzzle[2,0] = 3 + >>> s._is_valid_cell(0, 0) + False + >>> s._is_valid() + False + >>> s._puzzle[2,0] = s._empty + """ + for row in range(9): + if not self._is_valid_row(row): + return False + for col in range(9): + if not self._is_valid_col(col): + return False + for cell_row in range(3): + for cell_col in range(3): + if not self._is_valid_cell(cell_row, cell_col): + return False + return True + + def _is_valid_row(self, row): + values = self._nonempty(self._row(row)) + return len(values) == len(set(values)) + + def _is_valid_col(self, col): + values = self._nonempty(self._col(col)) + return len(values) == len(set(values)) + + def _is_valid_cell(self, cell_row, cell_col): + values = self._nonempty(self._cell(cell_row, cell_col).flatten()) + return len(values) == len(set(values)) + + def _num_solved(self): + return len(self._nonempty(self._puzzle.flatten())) + + def solve(self): + trials = numpy.zeros((9,9,9), dtype=numpy.int) + for row in range(9): + for col in range(9): + if self._puzzle[row,col] == self._empty: + trials[row,col,:] = range(1,10) + else: + x = self._puzzle[row,col] + trials[row,col,x-1] = x + + actions = 0 + while True: + start_actions = 0 + for row in range(9): + for col in range(9): + if self._puzzle[row][col] == self._empty: + for x in self._nonempty(trials[row,col,:]): + self._puzzle[row,col] = x + if not self._is_valid(): + actions += 1 + trials[row,col,x-1] = self._empty + self._puzzle[row,col] = self._empty + if len(self._nonempty(trials[row,col,:])) == 1: + self._puzzle[row][col] = ( + self._nonempty(trials[row,col,:])[0]) + if self._num_solved() == 81: + self.status = 'solved in %d steps' % actions + return # puzzle solved + if actions == start_actions: + self.status = 'aborted after %d steps' % actions + break # puzzle too hard to solve + +def test(): + import doctest + doctest.testmod() + +if __name__ == '__main__': + import sys + + if len(sys.argv) > 1: + assert sys.argv[1] == '--test', sys.argv + test() + sys.exit(0) + + s = Sudoku() + puzzle = sys.stdin.read() + s.load(puzzle) + s.solve() + print >> sys.stderr, s.status + print s.dump() -- 2.26.2