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 kSomeFound
else:
return kIndeterminate
def checkRow(self, y):
# y should be from 0 to 8
cellSet = []
for x in range(0, 9):
cellSet.append([x, y])
return self.checkSet(cellSet)
def checkColumn(self, x):
# x should be from 0 to 8
cellSet = []
for y in range(0, 9):
cellSet.append([x, y])
return self.checkSet(cellSet)
def checkBox(self, box):
# box should be from 0 to 8
x = (box // 3) * 3
y = (box % 3) * 3
cellSet = []
for x1 in range(x, x+3):
for y1 in range(y, y+3):
cellSet.append([x1, y1])
return self.checkSet(cellSet)
def solveByNeeded(self):
result = kIndeterminate
numleft = self.leftToSolve()
for i in range(0, 9):
aresult = self.checkRow(i)
if aresult == kImpossible or aresult == kAllSolutionsFound:
return aresult
aresult = self.checkColumn(i)
if aresult == kImpossible or aresult == kAllSolutionsFound:
return aresult
aresult = self.checkBox(i)
if aresult == kImpossible or aresult == kAllSolutionsFound:
return aresult
if numleft < self.leftToSolve():
return kSomeFound
else:
return kIndeterminate
def isSolved(self):
for row in self.puzzle:
for cell in row:
if cell is 0:
return False
return True
def loadTextFileToPuzzle(self, inFilePath):
afile = open(inFilePath, 'r')
outList = []
for line in range(0, 9):
s = afile.readline()
if len(s) == 0:
break
else:
if s[-1:] == '\n':
s = s[:-1]
if len(s) == 9:
linelist = []
for c in s:
if c == " ":
n = 0
else:
n = int(c)
linelist.append(n)
outList.append(linelist)
else:
return False
afile.close()
self.puzzle = outList
return True
def completelySolve(self):
self.validatePuzzle()
left = self.leftToSolve()
print "%i left to solve." % left
while left:
print "Solve by needed"
aresult = self.solveByNeeded()
if aresult == kImpossible or aresult == kAllSolutionsFound:
return aresult
self.validatePuzzle()
print "Solve by possible"
aresult = self.solveByPossible()
if aresult == kImpossible or aresult == kAllSolutionsFound:
return aresult
self.validatePuzzle()
nowleft = self.leftToSolve()
print "%i left to solve." % nowleft
if left == nowleft:
allPossible = self.findAllPossibleValues()
allPossible.sort()
bestGuesses = allPossible[0]
savedPuzzle = self.puzzle
for val in bestGuesses.values:
self.puzzle = copy.deepcopy(savedPuzzle)
self.puzzle[bestGuesses.cellY][bestGuesses.cellX] = val
print "Guessing %i at %i, %i" % (val, bestGuesses.cellX, bestGuesses.cellY)
aresult = self.completelySolve()
if aresult == kAllSolutionsFound:
return aresult
else:
left = nowleft
return kAllSolutionsFound
filelist = sys.argv[1:]
numfiles = len(filelist)
soduko = Soduko()
if numfiles == 1 or numfiles == 2:
filepath = filelist[0]
else:
filepath = EasyDialogs.AskFileForOpen(message='Choose a puzzle file:')
if soduko.loadTextFileToPuzzle(filepath):
soduko.printpuzzle()
soduko.completelySolve()
soduko.printpuzzle()
8 26 9351
8 6
2849
5 29 8
85639
9 87 3
53 26 8
1 8
48 7 52 3
6 1 4 5
83 56
2 1
8 4 7 6
6 3
7 9 1 4
5 2
72 69
4 5 8 7
145 8
58 43 6
68 2
2 4
1 49
9 38 46
8 192
3 5 81
76 9
4
439 5 6
1 7
6 8 193
9
9 86
61 2 8
I've enclosed my script and four puzzle files. The puzzle files are
text files containing nine lines of text, and containing nine digits
or spaces. Your puzzle 3 is the one in the file puzzle4.txt.
Interestingly, the file puzzle3.txt is the first one I ran across
that my earlier version couldn't solve. You must pass in the puzzle
file path as a single parameter to the script.
My script originally used two strategies, which I called solve-by-
needed and solve-by-possible. I found that neither strategy used by
itself completed as much of the difficult puzzles as alternating
between both strategies. However, even both together didn't
completely solve my puzzle 3 (or yours). I found I wasn't even able
to solve it myself unless I narrowed one space down to two
possibilities and took a guess. Of course, sometimes I would guess
wrong and have to keep track of where I was to be able to go back to
that state and make the other guess. Obviously a computer program can
do this more easily than I can, so I incorporated that as a third,
last resort strategy. This, so far, has always worked, and I can't
imagine it not working on a solvable puzzle. It seems like cheating,
though. I wrote it recursively, as making one guess can lead to
another situation where the puzzle is still solvable but strategies
one and two get stuck. I've never seen it recurse more than twice
with a real puzzle. With a really gross test I call "ones test", a
puzzle in which only nine ones are filled in (which obviously has
many possible solutions), it recursed very deeply and still succeeded
in producing a possible solution.
David
On Sep 16, 2005, at 3:45 PM, Bas wrote:
I came across some of these online sudoku games and thought after
playing a game or two that I'd better waste my time writing a solver
than play the game itself any longer. I managed to write a pretty dumb
brute force solver that can at least solve the easy cases pretty fast.
--
http://mail.python.org/mailman/listinfo/python-list
