Hi Bas,
I came across Soduko puzzles recently too and had the same reaction:
why waste my time solving the things when it would be much more fun
to write a Python program to do so?
#!/usr/bin/python
import sys
import copy
import EasyDialogs
# Solve functions return these result codes:
kImpossible = -1 # Impossible to solve (a cell has no possible values)
kIndeterminate = 0 # No solution found (a guess will be required)
kSomeFound = 1 # Some solutions found
kAllSolutionsFound = 2 # Puzzle is solved
class CellPossibilities:
def initCell(self, x, y):
self.cellX = x
self.cellY = y
self.values = []
def setPossibleValues(self, values):
self.values = values
def __lt__(self, other):
return len(self.values) < len(other.values)
def appendPossibilities(self, possibilities):
for val in self.values:
possibility = CellPossibility()
possibility.setPossibility(self.cellX, self.cellY, val)
possibilities.append(possibility)
class CellPossibility:
def setPossibility(self, x, y, value):
self.cellX = x
self.cellY = y
self.value = value
class Soduko:
def printpuzzle(self):
print "---"
for by in range(0, 3):
for ry in range(0, 3):
y = by * 3 + ry
rowstr = "|"
for bx in range(0, 3):
for cx in range(0, 3):
x = bx * 3 + cx
cellval = self.puzzle[y][x]
if cellval == 0:
rowstr = rowstr + " "
else:
rowstr = rowstr + str(cellval) + " "
rowstr = rowstr[0:-1] + "|"
print rowstr
print "---"
def leftToSolve(self):
left = 0;
for row in self.puzzle:
for cell in row:
if cell is 0:
left += 1
return left
def puzzleSolved(self):
for row in self.puzzle:
for cell in row:
if cell is 0:
return False
return True
def cellValueUsedInRow(self, x, y, testval):
for x1 in range(0,9):
if x1 != x and self.puzzle[y][x1] == testval:
return True;
return False
def cellValueUsedInColumn(self, x, y, testval):
for y1 in range(0,9):
if y1 != y and self.puzzle[y1][x] == testval:
return True;
return False
def enumerateBox(self, x, y):
x1 = x - x % 3
y1 = y - y % 3
for y2 in range(y1, y1+3):
for x2 in range(x1, x1+3):
if x2 != x or y2 != y:
yield self.puzzle[y2][x2]
def cellValueUsedInBox(self, x, y, testval):
for cellval in self.enumerateBox(x, y):
if cellval == testval:
return True
return False
def isCellValuePossible(self, x, y, testval):
if self.cellValueUsedInRow(x, y, testval):
return False
if self.cellValueUsedInColumn(x, y, testval):
return False
if self.cellValueUsedInBox(x, y, testval):
return False
return True;
def findPossibleValues(self, x, y):
possibles = []
for v in range(1, 10):
if self.isCellValuePossible(x, y, v):
possibles.append(v)
return possibles
def findAllPossibleValues(self):
results = []
for x in range(0, 9):
for y in range(0, 9):
if self.puzzle[y][x] == 0:
possibles = CellPossibilities()
possibles.initCell(x, y)
possibles.setPossibleValues(self.findPossibleValues(x, y))
results.append(possibles)
return results
def validatePuzzle(self):
ok = True;
for x in range(0, 9):
for y in range(0, 9):
if self.puzzle[y][x]:
if not self.isCellValuePossible(x, y, self.puzzle[y][x]):
print "Cell %i, %i contains conflicting value." % (x, y)
ok = False
else:
possibles = self.findPossibleValues(x, y)
if len(possibles) == 0:
print "Cell %i, %i has no possible value." % (x, y)
ok = False
return ok
def solveByPossible(self):
anyfound = False
for x in range(0, 9):
for y in range(0, 9):
if self.puzzle[y][x] == 0:
possibles = self.findPossibleValues(x, y)
if len(possibles) == 1:
self.puzzle[y][x] = possibles[0]
anyfound = True
elif len(possibles) == 0:
print "No possible values for %i, %i." % (x, y)
return kImpossible
if anyfound:
if self.puzzleSolved():
return kAllSolutionsFound
else:
return kSomeFound
else:
return kIndeterminate
def checkSet(self, cellSet):
# Find list of needed values in set
anyfound = False
needed = []
for val in range(1, 10):
for cell in cellSet:
if self.puzzle[cell[1]][cell[0]] == val:
break
else:
needed.append(val)
# For each needed value, count how many cells in the set it can
# possibly be in. If the number is 1, put the value in that cell.
for val in needed:
possibleCell = False
numPossible = 0
for cell in cellSet:
if self.puzzle[cell[1]][cell[0]] == 0:
if self.isCellValuePossible(cell[0], cell[1], val):
possibleCell = cell;
numPossible += 1
if numPossible == 1:
anyfound = True
self.puzzle[possibleCell[1]][possibleCell[0]] = val
elif numPossible == 0:
return kImpossible
if anyfound:
if self.puzzleSolved():
return kAllSolutionsFound
else:
return kS
