#
# Sudoku Solver
#
# This program solves a given sudoku puzzle stored in a file. The puzzle
# is represented as a list of rows of cells. Cells that have no fixed value
# are represented by 0. Cells with another specified value are taken to be
# fixed.
#
# The file can be specified as the first argument to the program. If it
# is not specified, the program will ask which file at startup.
#
# This file uses a new data structure in python: a set. Sets are much the
# same as they are in mathematics. The items in a set are unique and
# unordered. A set can be constructed from a list:
#
# S = set([1,2,3])
#
# or it can be created as an empty set:
#
# S = set()
#
# We can use the syntax:
#
# if x in S:
#
# to check if the element x belongs to the set S. These sets also have
# normal operations that we associate with sets such as union, intersection,
# and difference. We can, for example, write the untion of sets S and T as:
#
# S.union(T)
#
# One should note that the result is a new set, and neither of the original
# sets is modified. In order to "merge" one set into another, we could write:
#
# S = S.union(T)
# -or equivalently-
# S.update(T)
#
# We can also add individual elements to a set using S.add(elem).
#
# At each cell we will consider 3 sets:
# 1) The set of values that are in the current row (R)
# 2) The set of values that are in the current column (C)
# 3) The set of values that are in the same "box" (B)
#
# The union of these 3 sets is the set of all values that have already been
# used. Thus, the values we may choose are those values 1-9 that do not
# appear in this set.
#
# Rows and columns are indexed 0..8 top to bottom and left to right
# respectively. Boxes are numbered 0..8 moving left to right from top to
# bottom. The cells are visited left-to-right, top-to-bottom.
#
# ALGORITHM:
#
# For each cell:
# 1) If we have gone one cell past the end of the board, the puzzle is
# solved. Return True.
# 2) If the value of this cell is fixed, recursively call the algorithm
# on the next cell, returning the call's value.
# 3) Else we must attempt to choose a suitable value for this cell.
# a) Compute the set of values that cannot be used for this cell
# (described above).
# Let k = 1
# While k <= 9:
# i) If k is in the set of used values, increment it until it is not.
# If there are no values left, mark the cell empty, return False.
# ii) Assume for now that k is the correct answer for this cell.
# Recursively call the algorithm on the next cell.
# If the call returns True, the puzzle has been solved. Return True.
# Otherwise, add 1 to k and return to step i.
#
# If the algorithm terminates with True, then a solution is now contained
# in M. If the algorithm terminates with False, then the puzzle has no
# solution and the matrix contains the original board, unchanged.
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.
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 (THIS IS THE PART YOU HAVE TO DO):
# 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.
# 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
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
if __name__ == '__main__':
if len(sys.argv) < 2:
filename = raw_input('Input file? ')
else:
filename = sys.argv[1]
M = read_board(filename)
start = time.clock()
if solve(M):
print M
else:
print 'No solution.'
end = time.clock()
print 'Completed in', end - start, 'seconds.'