grid = array([2, 1, nan, 4, 3, nan, nan, 7, nan,
nan, nan, nan, nan, nan, nan, 8, 5, nan,
nan, nan, 4, nan, nan, 7, nan, 1, 3,
nan, nan, nan, nan, nan, 2, nan, 9, 5,
nan, nan, nan, 8, 1, 9, nan, nan, nan,
9, 6, nan, 7, nan, nan, nan, nan, nan,
8, 9, nan, 5, nan, nan, 7, nan, nan,
nan, 2, 1, nan, nan, nan, nan, nan, nan,
nan, 3, nan, nan, 7, 8, nan, 6, 9]).reshape((9, 9))
grid
array([[ 2., 1., nan, 4., 3., nan, nan, 7., nan], [ nan, nan, nan, nan, nan, nan, 8., 5., nan], [ nan, nan, 4., nan, nan, 7., nan, 1., 3.], [ nan, nan, nan, nan, nan, 2., nan, 9., 5.], [ nan, nan, nan, 8., 1., 9., nan, nan, nan], [ 9., 6., nan, 7., nan, nan, nan, nan, nan], [ 8., 9., nan, 5., nan, nan, 7., nan, nan], [ nan, 2., 1., nan, nan, nan, nan, nan, nan], [ nan, 3., nan, nan, 7., 8., nan, 6., 9.]])
class sudoku(object):
def __init__(self, grid):
self.grid = grid
def try_cell(self, cell_index, debug=False):
if not isnan(self.grid[cell_index]):
if debug:
print "cell is already occupied! by %s" % (self.grid[cell_index])
return array([])
else:
if debug:
print "cell is not yet occupied:", self.grid[cell_index]
# rows and columns
in_column = filter(lambda n: ~isnan(n), self.grid[:, cell_index[1]])
in_row = filter(lambda n: ~isnan(n), self.grid[cell_index[0], :])
if debug:
print "rows and columns contain:", unique(hstack((in_row, in_column)))
# 3 x 3 block cell
block_coords = [n / 3 for n in cell_index]
if debug:
print block_coords
in_block = self.grid[3 * block_coords[0]:3 * block_coords[0] + 3,
3 * block_coords[1]:3 * block_coords[1] + 3]
in_block = in_block.reshape((1, 9))[0]
in_block = filter(lambda n: ~isnan(n), in_block)
if debug:
print in_block
already_taken = unique(hstack((in_row, in_column, in_block)))
if debug:
print already_taken
return already_taken
def solve_step(self):
for i in range(self.grid.shape[0]):
for j in range(self.grid.shape[1]):
trial = self.try_cell((i, j))
if trial.shape == (8,):
self.grid[i, j] = 45 - sum(trial)
print i, j, 45 - sum(trial)
return True
return False
def solve(self):
can_solve = True
while can_solve:
can_solve = self.solve_step()
sdk = sudoku(grid)
d = sdk.try_cell((0, 2))
%time sdk.solve()
sdk.grid
0 8 6.0 0 5 5.0 0 6 9.0 0 2 8.0 1 1 7.0 2 1 5.0 2 0 6.0 1 0 3.0 1 2 9.0 2 6 2.0 1 8 4.0 2 3 9.0 2 4 8.0 4 1 4.0 3 1 8.0 6 2 6.0 7 8 8.0 8 2 5.0 8 0 4.0 7 0 7.0 3 0 1.0 4 0 5.0 8 6 1.0 6 8 2.0 4 8 7.0 5 8 1.0 6 4 4.0 3 4 6.0 1 4 2.0 3 3 3.0 3 2 7.0 3 6 4.0 5 4 5.0 5 5 4.0 5 6 3.0 4 6 6.0 4 7 2.0 4 2 3.0 5 2 2.0 5 7 8.0 6 7 3.0 6 5 1.0 1 5 6.0 1 3 1.0 7 3 6.0 7 4 9.0 7 5 3.0 7 6 5.0 7 7 4.0 8 3 2.0 CPU times: user 0.21 s, sys: 0.00 s, total: 0.21 s Wall time: 0.21 s
array([[ 2., 1., 8., 4., 3., 5., 9., 7., 6.], [ 3., 7., 9., 1., 2., 6., 8., 5., 4.], [ 6., 5., 4., 9., 8., 7., 2., 1., 3.], [ 1., 8., 7., 3., 6., 2., 4., 9., 5.], [ 5., 4., 3., 8., 1., 9., 6., 2., 7.], [ 9., 6., 2., 7., 5., 4., 3., 8., 1.], [ 8., 9., 6., 5., 4., 1., 7., 3., 2.], [ 7., 2., 1., 6., 9., 3., 5., 4., 8.], [ 4., 3., 5., 2., 7., 8., 1., 6., 9.]])