#!/usr/bin/python
# A simple Sudoku solver by Neil Campbell
# Written December 2005.
import sys;
# Where the actual numbers live.
grid = [];
# A handy set for doing differences.
allNums = set([ 1, 2, 3, 4, 5, 6, 7, 8, 9 ]);
def missing(present):
return allNums.difference(present);
# Get all the numbers from a row.
def getRow(row):
nums = [];
for i in range(9):
if grid[row][i] != ' ':
nums.append(grid[row][i]);
return set(nums);
# Get all the numbers from a column.
def getColumn(column):
nums = [];
for i in range(9):
if grid[i][column] != ' ':
nums.append(grid[i][column]);
return set(nums);
# Get all the numbers from a 9x9 square.
def getSquare(row, col):
squareRow = row / 3;
squareCol = col / 3;
startRow = squareRow * 3;
startCol = squareCol * 3;
nums = [];
for x in range(3):
for y in range(3):
digit = grid[startRow + x][startCol + y];
nums.append(digit);
return set(nums);
# Read in the data from stdin. Very little validation here.
for l in sys.stdin.readlines():
if len(l.strip('\n')) == 9:
row = [];
for c in l.strip('\n'):
if c == ' ':
row.append(0);
else:
row.append(int(c));
grid.append(row);
else:
print "ignoring: " + l.strip();
# Print the grid to see how far we've got.
def showGrid():
print "";
for row in range(9):
for col in range(9):
digit = grid[row][col];
if digit == 0:
print '*',
else:
print digit,
print "";
def getBlanks():
tmpBlanks = [];
for row in range(9):
for col in range(9):
digit = grid[row][col];
if digit == 0:
tmpBlanks.append( { 'col': col, 'row': row } );
return tmpBlanks;
def getPossibilitiesForSquare(row, col):
rowPossible = missing(getRow(row));
colPossible = missing(getColumn(col));
squPossible = missing(getSquare(row, col));
return rowPossible & colPossible & squPossible;
def lookForDuplicates(listOfPossiblities):
removes = [];
for i in range(len(listOfPossiblities)):
for j in range(len(listOfPossiblities)):
if i != j:
if listOfPossiblities[i] == listOfPossiblities[j]:
if len(listOfPossiblities[i]) <= 2:
for val in listOfPossiblities[i]:
removes.append(val);
# If there are 3 with 3 in, we could remove them too.
# Or 4 with 4, etc.
#else:
# print "Need to be more clever!";
return set(removes);
def searchForOtherRemovals(row, col):
rowUnknowns = [];
colUnknowns = [];
squUnknowns = [];
# row
for i in range(9):
# another unknown in the row
if (0 == grid[row][i]) and (i != col):
rowUnknowns.append(getPossibilitiesForSquare(row, i));
#column
for i in range(9):
# another unknown in the column
if (0 == grid[i][col]) and (i != row):
colUnknowns.append(getPossibilitiesForSquare(i, col));
rowRemoves = lookForDuplicates(rowUnknowns);
colRemoves = lookForDuplicates(colUnknowns);
removes = rowRemoves | colRemoves;
# I don't search squares yet!
return removes;
# Here's where we start actually working.
# First get a list of blank squares that we need to solve.
blanks = getBlanks();
# While there are blanks left, try to solve them.
while len(blanks) > 0:
showGrid();
# Keep track of how many we solved, if we didn't get any we have to stop,
# otherwise we'll loop forever.
solved = 0;
# Look at each blank in turn.
for pair in blanks:
row = pair['row'];
col = pair['col'];
# Find out what could possibly go in this square, based on the contents of
# its row, column and square.
possible = getPossibilitiesForSquare(row, col);
if len(possible) == 0:
# Gah! It's all gone King Kong.
print "Yikes, something is wrong, I have no possibilities left.\n";
sys.exit(1);
# There are several possibilities here, so we look for any way to cancel
# some of them.
elif len(possible) > 1:
removes = searchForOtherRemovals(row, col);
if len(removes) > 0:
possible = possible - removes;
if len(possible) == 1:
# W00t! We have an answer.
answer = possible.pop();
grid[row][col] = answer;
print "Solved: " + str(pair) + "; it is " + str(answer);
solved += 1;
# Update our list of blanks.
blanks = getBlanks();
if solved == 0:
print "Getting nowhere, giving up";
break;
# Success or no, we're finished here. Show the solution, or as close as we got.
showGrid();