from visual import label, color, scene
from numpy import matrix, zeros, int16
import sys
import time
def next_coordinate(row, col):
"""
Returns the next coordinate to explore in a sudoku puzzle, regardless of
whether or not the cell is actually empty. The order is left to right,
top to bottom.
"""
if col == 8:
return row + 1, 0
else:
return row, col + 1
def solve(M, row=0, col=0):
"""
Recursively solves a Sudoku puzzle starting at the given row and column.
Note that two assumptions are made:
1. All positions to the left and above of the starting position are filled
2. All filled in cells are valid (no duplicates as in the Sudoku rules)
Note that the second assumption does NOT imply that the puzzle is solvable.
M - A numpy matrix representing a Sudoku board. Initially, cells with
value 0 are considered empty, and cells with other values are
considered fixed.
row - the current row
col - the current column
"""
# Find the first empty cell from [row, col]. Stop if we pass the end of the
# puzzle.
# Pause so that the simulation doesn't run too fast
global Labels
time.sleep(.03)
while row < 9 and M[row,col] != 0:
row, col = next_coordinate(row, col)
# If we passed the last row (row 8) then we've solved the puzzle, so just
# return true.
if row == 9:
return True
# Otherwise, we need to do the standard guessing logic below:
# Find forbidden values.
F = set()
# Find all values in the same column
for k in range(9):
F.add(M[row,k])
# Find all values in the same row
for k in range(9):
F.add(M[k,col])
# Slightly trickier, we also need the numbers in the 3x3 grid containing
# the number. box_row and box_col are the row and column of the top left
# cell in the current box.
box_row = row - row%3
box_col = col - col%3
# Now check the 3x3 box starting at box_row, box_col
for k in range(3):
for l in range(3):
F.add(M[box_row+k, box_col+l])
# General idea:
# For the cell at location [row, col] consider all possible values between
# 1 and 9 not creating a conflict with earlier values currently in M.
# For every legal choice, check whether it leads to a solution by making a
# recursive call.
#
# If a solution exists, the recursive call returns True and True is
# returned (this means no further values need to be considered for cell
# M[row, col].
#
# If no solution exists, the next possible value is tried. After all
# possible values have been considered and none led to success, False is
# returned.
for val in xrange(1, 10):
# Locate the next lowest value that is available
if not val in F:
M[row,col] = val
Labels[row][col].text = str(val)
# Find out whether the choice M[row,col] = val leads to a solution
# Set up the arguments for the recursive vall
next_row, next_col = next_coordinate(row, col)
# make the recursive call and check what it returns
# take actions as described above
if solve(M, next_row, next_col):
return True
# We get to this statement if no possible assignment to M[row,col] led to
# a solution. Set the cell back to empty and return False.
M[row,col] = 0
Labels[row][col].text = ' '
return False
def read_board(filename):
f = open(filename)
M = matrix(zeros((9,9),dtype=int16))
k = 0
for s in f:
l = []
for t in s.split():
l.append(int(t))
M[k] = l
k += 1
return M
def init_viz(M):
"""
Initialize VPython scene and set up label matrix as a list of lists.
The visualization works by changing the label text by indexing
Labels[row][col].text.
"""
global Labels
scene.background=(1,1,1)
scene.userzoom = 0
scene.userspin = 0
scene.autoscale = 0
scene.title = 'Sudoku'
scene.width = scene.height = 500
Labels = [[None]*9 for j in range(9)]
for i in range(9):
for j in range(9):
if M[i,j] != 0:
Labels[i][j] = label(pos=(j-4,4-i,0), text=str(M[i,j]),
border=10, box=False,
color=color.black)
else:
Labels[i][j] = label(pos=(j-4,4-i,0), text=' ',
border=10, box=False,
color=color.white)
if __name__ == '__main__':
filename = raw_input('Input file? ')
M = read_board(filename)
init_viz(M)
start = time.clock()
if solve(M):
print M
else:
print 'No solution.'
end = time.clock()
print 'Completed in', end - start, 'seconds.'