#!/usr/bin/env python
+import itertools
+
import numpy
+TEST_PUZZLE_STRING = '\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',
+ ])
+
+
+def power_set(iterable):
+ """Return the power set of `iterable`.
+
+ >>> for i in power_set([1,2,3]):
+ ... print i
+ ()
+ (1,)
+ (2,)
+ (3,)
+ (1, 2)
+ (1, 3)
+ (2, 3)
+ (1, 2, 3)
+ """
+ s = list(iterable)
+ return itertools.chain.from_iterable(
+ itertools.combinations(s, r) for r in range(len(s)+1))
+
+
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.load(TEST_PUZZLE_STRING)
>>> s._num_solved()
30
>>> s.solve()
self._empty = 0
self._external_empty = '-'
self.status = None
+ self.solvers = [self._direct_elimination_solver,
+ self._slice_completion_solver]
def load(self, text):
row = 0
def _col(self, col):
return self._puzzle[:,col]
- def _cell(self, cell_row, cell_col):
+ def _cell_bounds(self, cell_row, cell_col):
ri = cell_row * 3
rf = ri + 3
ci = cell_col * 3
cf = ci + 3
+ return (ri, rf, ci, cf)
+
+ def _cell(self, cell_row, cell_col):
+ ri,rf,ci,cf = self._cell_bounds(cell_row, cell_col)
return self._puzzle[ri:rf,ci:cf]
+ def _slices(self):
+ """
+ >>> s = Sudoku()
+ >>> s.load(TEST_PUZZLE_STRING)
+ >>> for type,slice,index in s._slices():
+ ... print type,slice,index # doctest: +ELLIPSIS
+ row [5 3 0 0 7 0 0 0 0] 0
+ ...
+ row [0 0 0 0 8 0 0 7 9] 8
+ col [5 6 0 8 4 7 0 0 0] 0
+ ...
+ col [0 0 0 3 1 6 0 5 9] 8
+ cell [[5 3 0]
+ [6 0 0]
+ [0 9 8]] (0, 0)
+ ...
+ cell [[2 8 0]
+ [0 0 5]
+ [0 7 9]] (2, 2)
+ """
+ for row in range(9):
+ yield ('row', self._row(row), row)
+ for col in range(9):
+ yield ('col', self._col(col), col)
+ for cell_row in range(3):
+ for cell_col in range(3):
+ yield ('cell', self._cell(cell_row, cell_col),
+ (cell_row, cell_col))
+
+ def _point_to_cell_coords(self, row, col):
+ """
+ >>> s = Sudoku()
+ >>> s._point_to_cell_coords(4, 6)
+ (1, 2, 3)
+
+ The point in question:
+
+ - - - - - - - - -
+ - 0 - - 1 - - 2 -
+ - - - - - - - - -
+
+ - - - - - - 0 1 2
+ - 1 - - - - * - -
+ - - - - - - - - -
+
+ - - - - - - - - -
+ - - - - - - - - -
+ - - - - - - - - -
+ """
+ cell_row_residual = row % 3
+ cell_col_residual = col % 3
+ return (row/3, col/3,
+ cell_row_residual*3 + cell_col_residual)
+
+ def _cell_to_point_coords(self, cell_row, cell_col, i):
+ """
+ >>> s = Sudoku()
+ >>> s._cell_to_point_coords(1, 2, 3)
+ (4, 6)
+
+ The point in question:
+
+ 0 1 2 3 4 5 6 - -
+ 1 - - - - - - - -
+ 2 - - - - - - - -
+
+ 3 - - - - - - - -
+ 4 - - - - - * - -
+ - - - - - - - - -
+
+ - - - - - - - - -
+ - - - - - - - - -
+ - - - - - - - - -
+ """
+ row = cell_row * 3 + (i / 3)
+ col = cell_col * 3 + (i % 3)
+ return (row, col)
+
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.load(TEST_PUZZLE_STRING)
>>> 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):
+ for type,slice,index in self._slices():
+ values = self._nonempty(slice.flat)
+ if len(values) != len(set(values)):
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):
+ actions = 0
+ trials = self._setup_trials()
+ while True:
+ start_actions = actions
+ for solver in self.solvers:
+ acts,trials = solver(trials)
+ self._apply_trials(trials)
+ actions += acts
+ if acts > 0:
+ break # don't use slow solvers unless they're required
+ if self._num_solved() == 81:
+ self.status = 'solved in %d steps' % actions
+ return # puzzle solved
+ elif actions == start_actions:
+ self.status = 'aborted after %d steps' % actions
+ return # puzzle too hard to solve
+
+ def _setup_trials(self):
trials = numpy.zeros((9,9,9), dtype=numpy.int)
for row in range(9):
for col in range(9):
else:
x = self._puzzle[row,col]
trials[row,col,x-1] = x
+ return trials
+
+ def _apply_trials(self, trials):
+ for row in range(9):
+ for col in range(9):
+ if len(self._nonempty(trials[row,col,:])) == 1:
+ self._puzzle[row][col] = (
+ self._nonempty(trials[row,col,:])[0])
+ assert self._is_valid(), (
+ 'error setting [%d,%d] to %d'
+ % (row, col, self._puzzle[row][col]))
+
+ def _trial_slice(self, trials, type, index):
+ """Return a slice from the trials array.
+
+ >>> s = Sudoku()
+ >>> s.load(TEST_PUZZLE_STRING)
+ >>> trials = s._setup_trials()
+ >>> t = s._trial_slice(trials, 'row', 0)
+ >>> t # doctest: +REPORT_UDIFF
+ array([[0, 0, 0, 0, 5, 0, 0, 0, 0],
+ [0, 0, 3, 0, 0, 0, 0, 0, 0],
+ [1, 2, 3, 4, 5, 6, 7, 8, 9],
+ [1, 2, 3, 4, 5, 6, 7, 8, 9],
+ [0, 0, 0, 0, 0, 0, 7, 0, 0],
+ [1, 2, 3, 4, 5, 6, 7, 8, 9],
+ [1, 2, 3, 4, 5, 6, 7, 8, 9],
+ [1, 2, 3, 4, 5, 6, 7, 8, 9],
+ [1, 2, 3, 4, 5, 6, 7, 8, 9]])
+ For `row` and `column` slices, the original `trials` array
+ responds to changes in `t`.
+
+ >>> trials[0,2,:]
+ array([1, 2, 3, 4, 5, 6, 7, 8, 9])
+ >>> t[2,:] = 0
+ >>> t[2,3] = 4
+ >>> trials[0,2,:]
+ array([0, 0, 0, 4, 0, 0, 0, 0, 0])
+
+ `cell` slices don't work with "flat" indexing, because the
+ stride would not be constant. You'll have to push changes
+ back to `trials` by hand.
+
+ >>> t = s._trial_slice(trials, 'cell', (0, 0))
+ >>> t # doctest: +REPORT_UDIFF
+ array([[0, 0, 0, 0, 5, 0, 0, 0, 0],
+ [0, 0, 3, 0, 0, 0, 0, 0, 0],
+ [0, 0, 0, 4, 0, 0, 0, 0, 0],
+ [0, 0, 0, 0, 0, 6, 0, 0, 0],
+ [1, 2, 3, 4, 5, 6, 7, 8, 9],
+ [1, 2, 3, 4, 5, 6, 7, 8, 9],
+ [1, 2, 3, 4, 5, 6, 7, 8, 9],
+ [0, 0, 0, 0, 0, 0, 0, 0, 9],
+ [0, 0, 0, 0, 0, 0, 0, 8, 0]])
+ >>> trials[1,1,:]
+ array([1, 2, 3, 4, 5, 6, 7, 8, 9])
+ >>> t[4,:] = 0
+ >>> t[4,6] = 7
+ >>> trials[1,1,:] = t[4,:]
+ >>> trials[1,1,:]
+ array([0, 0, 0, 0, 0, 0, 7, 0, 0])
+ """
+ if type == 'row':
+ t = trials[index,:,:]
+ elif type == 'col':
+ t = trials[:,index,:]
+ else:
+ assert type == 'cell', type
+ cell_row,cell_col = index
+ ri,rf,ci,cf = self._cell_bounds(cell_row, cell_col)
+ t = trials[ri:rf,ci:cf,:]
+ t = t.reshape((t.shape[0]*t.shape[1], t.shape[2])).copy()
+ if type in ['row', 'col']:
+ assert t.flags.owndata == False, t.flags.owndata
+ assert t.base is trials, t.base
+ else:
+ assert t.flags.owndata == True, t.flags.owndata
+ return t
+
+ def _direct_elimination_solver(self, trials):
+ r"""Eliminate trials if a point already has the trial digit in
+ its row/col/cell.
+
+ >>> puzzle = '\n'.join([
+ ... '1 2 3 - - - - - -',
+ ... '4 5 6 - - - - - -',
+ ... '7 8 - - - - - - -',
+ ... '',
+ ... '- - - - - - - - -',
+ ... '- - - - - - - - -',
+ ... '- - - - - - - - -',
+ ... '',
+ ... '- - - - - - - - -',
+ ... '- - - - - - - - -',
+ ... '- - - - - - - - -',
+ ... ])
+ >>> s = Sudoku()
+ >>> s.load(puzzle)
+ >>> trials = s._setup_trials()
+ >>> actions,trials = s._direct_elimination_solver(trials)
+
+ The solver eliminated three numbers for two columns and rows
+ and two numbers for three columns and rows, which makes for
+ 104 = 8 # point 2,2 (the solved point)
+ + 6*3 # row 0
+ + 6*3 # row 1
+ + 6*2 # row 2
+ + 6*3 # col 0
+ + 6*3 # col 1
+ + 6*2 # col 2
+ eliminations.
+
+ >>> actions
+ 104
+ >>> s._apply_trials(trials)
+ >>> print s.dump()
+ 1 2 3 - - - - - -
+ 4 5 6 - - - - - -
+ 7 8 9 - - - - - -
+ <BLANKLINE>
+ - - - - - - - - -
+ - - - - - - - - -
+ - - - - - - - - -
+ <BLANKLINE>
+ - - - - - - - - -
+ - - - - - - - - -
+ - - - - - - - - -
+ """
actions = 0
- while True:
- start_actions = actions
- 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():
+ 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
+ return (actions, trials)
+
+ def _slice_completion_solver(self, trials):
+ r"""Eliminate trials if a set of N points have trials drawn
+ only from a list of N options.
+
+ For example, a slice like
+ [1, 2, 3, {4,5}, {4,6}, {4,5,6}, {4,5,6,7,8,9},
+ {4,5,6,7,8,9}, {4,5,6,7,8,9}]
+ has three points {4,5}, {4,6}, and {4,5,6}, with three possible
+ numbers: 4, 5, and 6. That means, 4, 5, and 6 would definitely
+ occupy the three points and other points should not have those
+ numbers.
+
+ >>> puzzle = '\n'.join([
+ ... '1 2 3 - - - - - -',
+ ... '- - - 7 - - - - -',
+ ... '- - - - 8 9 - - -',
+ ... '',
+ ... '- - - 6 5 - - - -',
+ ... '- - - - - - - - -',
+ ... '- - - - - - - - -',
+ ... '',
+ ... '- - - - - - - - -',
+ ... '- - - - - - - - -',
+ ... '- - - - - - - - -',
+ ... ])
+ >>> s = Sudoku()
+ >>> s.load(puzzle)
+ >>> trials = s._setup_trials()
+
+ Take a first pass through `_direct_elimination_solver()` to
+ eliminate trial values in the rows/columns/cells blocked by
+ the initialized points.
+
+ >>> actions,trials = s._direct_elimination_solver(trials)
+
+ The solver eliminated the following possibilities (by number)
+ 142 = 6 + 6 + 6 # number 1, cell+row+col
+ + 6 + 6 + 6 # number 2, cell+row+col
+ + 6 + 6 + 6 # number 3, cell+row+col
+ + 7 + 6 + 5 # number 5, cell+row+col
+ + 7 + 6 + 5 # number 6, cell+row+col
+ + 6 + 6 + 5 # number 7, cell+row+col
+ + 6 + 6 + 5 # number 8, cell+row+col
+ + 6 + 6 + 6 # number 9, cell+row+col
+
+ >>> actions
+ 142
+
+ However the direct solver was unable to actually solve any new
+ points.
+
+ >>> s._apply_trials(trials)
+ >>> print s.dump()
+ 1 2 3 - - - - - -
+ - - - 7 - - - - -
+ - - - - 8 9 - - -
+ <BLANKLINE>
+ - - - 6 5 - - - -
+ - - - - - - - - -
+ - - - - - - - - -
+ <BLANKLINE>
+ - - - - - - - - -
+ - - - - - - - - -
+ - - - - - - - - -
+ >>> trials[0,:,:] # doctest: +REPORT_UDIFF
+ array([[1, 0, 0, 0, 0, 0, 0, 0, 0],
+ [0, 2, 0, 0, 0, 0, 0, 0, 0],
+ [0, 0, 3, 0, 0, 0, 0, 0, 0],
+ [0, 0, 0, 4, 5, 0, 0, 0, 0],
+ [0, 0, 0, 4, 0, 6, 0, 0, 0],
+ [0, 0, 0, 4, 5, 6, 0, 0, 0],
+ [0, 0, 0, 4, 5, 6, 7, 8, 9],
+ [0, 0, 0, 4, 5, 6, 7, 8, 9],
+ [0, 0, 0, 4, 5, 6, 7, 8, 9]])
+
+ Now we proceed with the slice comparison solver.
+
+ >>> actions,trials = s._slice_completion_solver(trials)
+
+ The solver reduced trials in the following points
+ 12 = 1 # point 0,6, removed 4,5,6 must be in center of row 0
+ + 1 # point 0,7, removed 4,5,6 must be in center of row 0
+ + 1 # point 0,8, removed 4,5,6 must be in center of row 0
+ + 1 # point 1,4, removed 4,6 must be in top of cell 0,1
+ + 1 # point 1,5, removed 4,5,6 must be in top of cell 0,1
+ + 1 # point 2,3, removed 4,5 must be in top of cell 0,1
+ + 1 # point 1,6, removed 8,9 must be in top of cell 0,2
+ + 1 # point 1,7, removed 8,9 must be in top of cell 0,2
+ + 1 # point 1,8, removed 8,9 must be in top of cell 0,2
+ + 1 # point 2,6, removed 7 must be in top of cell 0,2
+ + 1 # point 2,7, removed 7 must be in top of cell 0,2
+ + 1 # point 2,8, removed 7 must be in top of cell 0,2
+
+ >>> actions
+ 12
+ >>> trials[0,:,:] # doctest: +REPORT_UDIFF
+ array([[1, 0, 0, 0, 0, 0, 0, 0, 0],
+ [0, 2, 0, 0, 0, 0, 0, 0, 0],
+ [0, 0, 3, 0, 0, 0, 0, 0, 0],
+ [0, 0, 0, 4, 5, 0, 0, 0, 0],
+ [0, 0, 0, 4, 0, 6, 0, 0, 0],
+ [0, 0, 0, 4, 5, 6, 0, 0, 0],
+ [0, 0, 0, 0, 0, 0, 7, 8, 9],
+ [0, 0, 0, 0, 0, 0, 7, 8, 9],
+ [0, 0, 0, 0, 0, 0, 7, 8, 9]])
+ """
+ actions = 0
+ for _type,slice,index in self._slices():
+ assert slice.size == 9, slice
+ trial_slice = self._trial_slice(trials, _type, index)
+ missing = set(self._nonempty(trial_slice.flat))
+ for possible in power_set(missing):
+ possible = set(possible)
+ if possible in [set(), missing]:
+ continue
+ points = []
+ for k in range(slice.size):
+ trial_set = set(self._nonempty(trial_slice[k,:]))
+ if trial_set.issubset(possible):
+ points.append(k)
+ if len(points) == len(possible):
+ possible_trial_slice = [0]*9
+ for p in possible:
+ possible_trial_slice[p-1] = p
+ for k in range(slice.size):
+ if k in points:
+ ts = numpy.array(possible_trial_slice)
+ for i,p in enumerate(ts):
+ if trial_slice[k,i] == self._empty:
+ ts[i] = self._empty
+ else:
+ ts = trial_slice[k,:].copy()
+ for i,p in enumerate(ts):
+ if p in possible:
+ ts[i] = self._empty
+ if _type == 'cell':
+ cell_row,cell_col = index
+ row,col = self._cell_to_point_coords(
+ cell_row, cell_col, k)
+ if (ts != trials[row,col,:]).any():
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
+ #print _type, index, k, row, col, trial_slice[k,:], ts
+ trials[row,col,:] = ts
+ trial_slice[k,:] = ts
+ else: # row or column
+ if (ts != trial_slice[k,:]).any():
+ actions += 1
+ #print _type, index, k, trial_slice[k,:], ts
+ trial_slice[k,:] = ts
+ return (actions, trials)
+
def test():
import doctest
doctest.testmod()
if __name__ == '__main__':
+ import optparse
import sys
- if len(sys.argv) > 1:
- assert sys.argv[1] == '--test', sys.argv
+ p = optparse.OptionParser()
+ p.add_option('--test', dest='test', default=False, action='store_true',
+ help='Run unit tests and exit.')
+ p.add_option('-d', '--disable-direct', dest='direct', default=True,
+ action='store_false',
+ help='Disable the direct elimination solver')
+ p.add_option('-c', '--disable-completion', dest='completion', default=True,
+ action='store_false',
+ help='Disable the slice completion solver')
+
+ options,args = p.parse_args()
+
+ if options.test:
test()
sys.exit(0)
s = Sudoku()
+ if not options.direct:
+ s.solvers.remove(s._direct_elimination_solver)
+ if not options.completion:
+ s.solvers.remove(s._slice_completion_solver)
+
puzzle = sys.stdin.read()
s.load(puzzle)
try:
projects / parallel_computing.git / commitdiff