Brute force sudoku cracker

[Bas]

Hi group,

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.

It basically works by listing all 9 possible numbers for all 81 fields
and keeps on striking out possibilities until it is done.

-any ideas how to easily incorporate advanced solving strategies?
solve(problem1) and solve(problem2) give solutions, but solve(problem3)
gets stuck...

-any improvements possible for the current code? I didn't play a lot
with python yet, so I probably missed some typical python tricks, like
converting for-loops to list expressions.

TIA,
Bas

***********

from itertools import ifilterfalse

problem1 = [' 63 7 ',
' 69 8',
'9 7 2',
' 2 1 8 ',
' 5 8 6 9 ',
' 9 7 2 ',
'6 1 3',
'7 45 ',
' 9 14 ']

problem2 = [' 3 9 7',
' 1 8 ',
' 1 9 ',
' 49 5 6',
' 2 1 ',
'5 6 74 ',
' 5 1 ',
' 4 2 ',
'7 5 3 ']

problem3 = [' 3 5 81 ',
' 76 9 ',
'4 ',
' 439 5 6',
' 1 7 ',
'6 8 193 ',
' 9',
' 9 86 ',
' 61 2 8 ']

#define horizontal lines, vertical lines and 3x3 blocks
groups = [range(9*i,9*i+9) for i in range(9)] + \
[range(i,81,9) for i in range(9)] + \
[range(0+27*i+3*j,3+27*i+3*j) + range(9+27*i+3*j,12+27*i+3*j)
+ \
range(18+27*i+3*j,21+27*i+3*j) for i in range(3) for j in
range(3)]

def display(fields):
for i in range(9):
line = ''
for j in range(9):
if len(fields[9*i+j]) == 1:
line += ' ' + str(fields[9*i+j][0])
else:
line += ' '
print line


def all(seq, pred=bool):
"Returns True if pred(x) is True for every element in the iterable"
for elem in ifilterfalse(pred, seq):
return False
return True

def product(seq):
prod = 1
for item in seq:
prod *= item
return prod

def solve(problem):
fields = [range(1,10) for i in range(81)] #fill with all
posibilities for all fields
for i,line in enumerate(problem):
for j,letter in enumerate(line):
if letter != ' ':
fields[9*i+j]=[int(letter)] #seed with numbers from
problem
oldpos = 0
while True:
pos = product(len(field) for field in fields)
if pos == oldpos: #no new possibilities eliminated, so stop
break
display(fields)
print pos,'possibilities'
oldpos = pos
for group in groups:
for index in group:
field = fields[index]
if len(field) == 1: #if only number possible for field
remove it from other fields in group
for ind in group:
if ind != index:
try:
fields[ind].remove(field[0])
except ValueError:
pass
else: #check if field contains number that does not
exist in rest of group
for f in field:
if all(f not in fields[ind] \
for ind in group if ind!=index):
fields[index] = [f]
break

 

[my.correo.basura]

Bas ha escrito:

Hi group,

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.

It basically works by listing all 9 possible numbers for all 81 fields
and keeps on striking out possibilities until it is done.
[snip]

This problem is desperately begging for backtracking. The cost is still
exponential but it works nicely with small problems. Fortunately, a 9x9
grid is small enough. I programmed this about two months ago, it's not
really pretty but it works perfectly. Beware, some variable names are
in spansih...
[let's hope the tabs are kept...]
Regards,
Al


from sets import Set

class sudoku:
def __init__(self,cadena):
self.numeros=Set(range(1, 10))
self.m=[['X']*9 for i in range(9)]
for fila in range(9):
for columna in range(9):
if cadena[fila*9 + columna].isdigit():
self.m[fila][columna]=int(cadena[fila*9+columna])
self.posiciones=[(i,j) for i in range(9) for j in range(9) if
self.m[j]=='X']
def __repr__(self):
res=""
for fila in range(9):
if fila%3==0: res+= "-------------------------\n"

for columna in range(9):
if columna%3==0: res+= "| "
res+="%s "%str(self.m[fila][columna])
res+= "|\n"

res+= "-------------------------\n"
return res

def fila(self,fila, columna):
return self.numeros-Set(elem for elem in self.m[fila] if
elem!='X')
def columna(self,fila, columna):
return self.numeros-Set(self.m[columna] for i in range(9)
if self.m[columna]!='X')

def cuadro(self,fila, columna):
s=Set()
f_ini=3*(fila/3)
c_ini=3*(columna/3)
for f in range(f_ini, f_ini+3):
for c in range(c_ini, c_ini+3):
if self.m[f][c]!='X' and self.m[f][c] not in s:
s.add(self.m[f][c])

return self.numeros-s

def resuelve(self):
print "Resolviendo"
def actua(i):
if i==len(self.posiciones):
print self
return
f, c=self.posiciones
posibles=self.fila(f, c).intersection(self.columna(f,
c)).intersection(self.cuadro(f, c))
for num in posibles:
self.m[f][c]=num
actua(i+1)
self.m[f][c]='X'
actua(0)

def main():
problem3=" 3 5 81 76 9 4 439 5 6 1 7 6 8 193
9 9 86 61 2 8 "
t=sudoku(problem3)
print t
t.resuelve()

if __name__=="__main__":
main()

 

[Sybren Stuvel]

Bas enlightened us with:

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.

I've got a solver too - I'm joining the Linux Format programming
contest. My program can solve and create Sudoku puzzles - and not only
9x9 ones. Check http://www.unrealtower.org/sodoku. In the LFX
programming contest they call the puzzle Sodoku, not Sudoku, so that's
why I'm sticking with the name Sodoku for now.

-any improvements possible for the current code? I didn't play a lot
with python yet, so I probably missed some typical python tricks,
like converting for-loops to list expressions.

It all depends on what you want to do. My program can create & solve
puzzles from any size, load and save them to disk, check them for
validity and rank them ('easy', 'medium', 'hard', 'near impossible').
It also implements a puzzle in a class, so it can be used in an OOP
fashion.

def all(seq, pred=bool):

What's this? What is bool?

Sybren

 

[Tom Anderson]

-any ideas how to easily incorporate advanced solving strategies?
solve(problem1) and solve(problem2) give solutions, but solve(problem3)
gets stuck...

the only way to solve arbitrary sudoku problems is to guess.

of course, you have to deal with guessing wrongly, and it helps if you can
make good guesses!

i wrote a solver based entirely on guessing and backtracking a few months
ago; it's fairly simple, although i wrote it in fairly fine-grained java,
so there's actually quite a lot of code. i had a very different program
structure to you, since i was only doing guesswork; i had a recursive
function that looked like this:

def solve(grid):
"""Solves a grid.

The solution is written in the grid; if no solution can be found, does
nothing to the grid. Returns True if a solution was found, False if not.
"""
x, y = pick_an_empty_cell_to_try(grid)
letters = letters_which_can_be_written_in_this_cell(grid, x, y)
if (letters == []):
return False # there are no legal moves; give up
for letter in letters:
grid.write(x, y, letter) # try a move ...
if (solve(grid)):
return True # we win!
grid.erase(x, y) # ... undo it if it didn't work
return False # none of the legal moves work; give up

the implementation of the grid class is pretty straightforward - it's just
a two-dimensional matrix with some bells and whistles.
letters_which_can_be_written_in_this_cell is also fairly simple, although
it can be made a lot faster by keeping summary information in the grid
object: i had a set for each row, column and region saying which letters
had been written already, so the set of available letters was the inverse
of the union of the sets relevant to the cell; the sets were implemented
as bitmaps, so this was all very fast.

the only tricky bit is pick_an_empty_cell_to_try; you can have fun trying
different heuristics here! the nice thing is that it's okay to use quite
computationally expensive heuristics, since a modestly better choice can
save huge numbers of recursions.

there are a number of much, much more advanced algorithms out there, doing
all sorts of clever stuff. however, my algorithm solves any sudoku i can
throw at it (barring seriously unreasonable stuff) in under a second, so
i'm happy with it.

tom

 

[Pierre Barbier de Reuille]

Tom Anderson a écrit :

the only way to solve arbitrary sudoku problems is to guess.

Well, that's true, but most of the sudoku puzzles can be solved in
linear time ! And also having a linear time solving algorithm allows you
to really reduce the time used when you need backtracking.

BTW, the three given examples can be solved without backtracking.

I made one very recently (mmhh ... first complete version made
yesterday, still need a little bit of debug on the backtracking part),
and it's pretty quick (made in Ruby but well, I suppose timing are
similar), it never get stuck for long even if it fails, it fails quickly ...

Pierre

 

[Benji York]

What's this? What is bool?

See http://docs.python.org/lib/built-in-funcs.html#l2h-10

 

[David Durkee]

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?



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

 

[Bas]

def all(seq, pred=bool):

What's this? What is bool?

That came straight out of the manual for itertools:
http://docs.python.org/lib/itertools-recipes.html

 

[Dennis Lee Bieber]

It basically works by listing all 9 possible numbers for all 81 fields
and keeps on striking out possibilities until it is done.

-any ideas how to easily incorporate advanced solving strategies?
solve(problem1) and solve(problem2) give solutions, but solve(problem3)
gets stuck...

My version doesn't handle the really ugly ones either.

I never incorporated back-tracking, and the "level 3" puzzles in my
book are full of such ... (watch out for line wrap) {I've just converted
the input logic, it isn't fully tested, and should have a way to "erase"
prior rows for correction}

-=-=-=-=-=-=-=-=-=-

import time


class Cell(object):
def __init__(self):
self.locked = False # final value found
self.value = None
self.candidates = [1, 2, 3, 4, 5, 6, 7, 8, 9]

def set(self, value):
self.locked = True
self.value = value
self.candidates = None

def eliminate(self, value):
if not self.locked:
if value in self.candidates:
self.candidates.remove(value)
return True
return False


class Grid(object):
def __init__(self):
self.cells = [ [Cell(), Cell(), Cell()],
[Cell(), Cell(), Cell()],
[Cell(), Cell(), Cell()] ]

def completed(self):
for r in range(3):
for c in range(3):
if not self.cells[r][c].locked:
return False
return True

class Table(object):
def __init__(self):
self.grids = [ [Grid(), Grid(), Grid()],
[Grid(), Grid(), Grid()],
[Grid(), Grid(), Grid()] ]

self.rows = [None] * 9
for r in range(9):
row = [None] * 9
for c in range(9):
row[c] = self.grids[r / 3][c / 3].cells[r % 3][c % 3]

def set(self, row, col, value):
self.grids[row / 3][col / 3].cells[row % 3][col % 3].set(value)

def get(self, row, col):
return self.grids[row / 3][col / 3].cells[row % 3][col % 3]

def eliminate(self, row, col, value):
changed = False
for c in range(9):
changed = (self.grids[row / 3][c / 3].cells[row % 3][c %
3].eliminate(value)
or changed)

for r in range(9):
changed = (self.grids[r / 3][col / 3].cells[r % 3][col %
3].eliminate(value)
or changed)

grid = self.grids[row / 3][col / 3]
for c in range(3):
for r in range(3):
changed = (grid.cells[r][c].eliminate(value) or changed)

return changed

def display(self):
print "\n\n0 1 2 3 4 5 6 7 8\n=================="
for r in range(9):
for c in range(9):
if self.get(r, c).value:
print "%s" % (self.get(r, c).value),
else:
print " ",
print "|%s" % r

def completed(self):
for r in range(3):
for c in range(3):
if not self.grids[r][c].completed():
return False
return True


if __name__ == "__main__":
myTable = Table()
## print "\n\nEnter a value of 0 to exit setup"
## print "\tRow and Column range 0..8"
##
## while True:
## cin = raw_input("Enter the cell Value Row Column (space
separated: ")
## try:
## cv, cr, cc = cin.split()
## value = int(cv)
## if value == 0: break
## row = int(cr)
## col = int(cc)
## myTable.set(row, col, value)
## myTable.display()
## print
## except:
## print "Error processing input: try again"
## pass
print "\n\nEnter row data in the form: x..y.z..."
print "\twhere . represents and empty cell, and"
print "\t x, y, z represent digits in the range 1..9\n"
for cr in range(9):
while True:
while True:
cin = raw_input("Enter Row %s: " % cr)
if len(cin) == 9: break #correct length
print "*** Enter 9 characters only; '%s' is %s
characters" % (cin, len(cin))
good_row = True
for cc in range(9):
if cin[cc] == ".": continue #empty cell
value = int(cin[cc])
if value == 0:
good_row = False #bad character
print "*** Only 1..9, or . are allowed"
for ec in range(9):
myTable.set(cr, ec, None) #clear row
break
else:
myTable.set(cr, cc, value)
if good_row: break #escape from row input loop
myTable.display()



print "\n\nBuilding table ",
for r in range(9):
for c in range(9):
if myTable.get(r, c).locked:
myTable.eliminate(r, c, myTable.get(r, c).value)

myTable.display()

while True:
print "Evaluating "
change = False
done = True
for r in range(9):
for c in range(9):
print ".",
time.sleep(0.01)
if not myTable.get(r, c).locked:
if len(myTable.get(r, c).candidates) == 1:
myTable.set(r, c, myTable.get(r,
c).candidates[0])
change = myTable.eliminate(r, c,
myTable.get(r,
c).value)
myTable.display()
if change: break
if change: break

print

# check for completion
if myTable.completed():
print "Completed"
break

if not change:
deadlock = True
print "Resolving initial deadlock"
for gr in range(3):
for gc in range(3):
myGrid = myTable.grids[gr][gc]
count = [0] * 9
if deadlock:
for r in range(3):
for c in range(3):
if deadlock and
myGrid.cells[r][c].candidates:
for n in
myGrid.cells[r][c].candidates:
count[n-1] += 1

try:
n = count.index(1) + 1
deadlock = False
for r in range(3):
for c in range(3):
if (myGrid.cells[r][c].candidates
and n in
myGrid.cells[r][c].candidates):
myGrid.cells[r][c].set(n)
myTable.eliminate(gr * 3 + r, gc
* 3 + c, n)
myTable.display()
except:
pass

if deadlock:
print "Deadlocked; must be resolved manually"
cin = raw_input("Enter value row column: ")
cv, cr, cc = cin.split()
value = int(cv)
row = int(cr)
col = int(cc)
myTable.set(row, col, value)
myTable.eliminate(row, col, value)
myTable.display()
-=-=-=-=-=-=-=-

problem3 = [' 3 5 81 ',
' 76 9 ',
'4 ',
' 439 5 6',
' 1 7 ',
'6 8 193 ',
' 9',
' 9 86 ',
' 61 2 8 ']

Yes, that is a deadlock set... (You'll need fixed width font)

0 1 2 3 4 5 6 7 8
==================
3 5 8 1 |0
1 7 6 9 |1
4 |2
8 4 3 9 7 5 1 2 6 |3
1 6 7 8 |4
6 8 1 9 3 |5
1 5 7 9 |6
9 8 6 1 |7
6 1 9 2 8 |8
Evaluating
.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
.. . . . . . . . . . . .
.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Resolving initial deadlock


0 1 2 3 4 5 6 7 8
==================
3 5 8 1 |0
1 7 6 9 |1
4 1 |2
8 4 3 9 7 5 1 2 6 |3
1 6 7 8 |4
6 8 1 9 3 |5
1 5 7 9 |6
9 8 6 1 |7
6 1 9 2 8 |8
Evaluating
.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
.. . . . . . . . . . . .
.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Resolving initial deadlock
Deadlocked; must be resolved manually
Enter value row column:

Given a set like that, the next approach would be to add recursion:
clone (deep copy) the tableau, find the first empty cell, pick the first
available number for it (saving a list of those tried), then recursively
try to finish the puzzle after using that number... Next deadlock,
clone, pick next empty cell, pick candidate... If you get to a deadlock
where there is an empty cell and NO viable candidates, pop back to the
previous saved tableau and try the next candidate at that location. If
all candidates fail, pop back yet again...



--

 

[Diez B. Roggisch]

As everyone posts his, I'll do the same It uses some constraint based
solving techniques - but not too complicated ones. When stuck, it
backtracks. So far it never failed me, but I haven't tested it too
thouroughly.

Diez

import copy

def condense(vals):

if len(vals) == 0:
return ""
ranges = [0]
ranges += [i+1 for i, v in enumerate(vals[:-1]) if vals[i+1] - v > 1]
ranges.append(len(vals))
ranges = zip(ranges[:-1], ranges[1:])
def f(l):
if len(l) > 1:
return "%i-%i" % (l[0], l[-1])
return "%i" % l[0]
return ", ".join([f(vals[a:b]) for a,b in ranges])


riddle1 = """
1**83***2
57***1***
***5*9*64
7*4**859*
**3*1*4**
*514**3*6
36*7*4***
***6***79
8***52**3
"""
riddle2 = """
**2*9*1*7
*386*****
4********
*****5***
**9*1*3**
***4*****
********4
*****792*
8*6*3*7**
"""
class Constraint(object):
def __init__(self, fields):
self.__fields = fields

def apply(self, sudoko, all_nums = set(xrange(1,10))):
changed = False
placed = set()
[placed.update(sudoko[x][y]) for x,y in self.__fields if len(sudoko[x][y]) == 1]
news = []
for x,y in self.__fields:
old = sudoko[x][y]
if len(old) > 1:
new = old.intersection(all_nums.difference(placed))
if len(new) == 0:
raise ValueError()
if old != new:
changed = True
sudoko[x][y] = new
news.append(((x,y), new))
# naked pair elimination
if changed:
return True
pair_found = False
#print "-" * 30
#print sudoko
#print "-" * 30
for i in xrange(2, 5):
all = [list(n) for f,n in news if len(n) == i]
[l.sort() for l in all]
all = [tuple(l) for l in all]
all.sort()
#print "all ", all
for j, l in enumerate(all[:-1]):
if len(all[j:j+i]) == i and len(set(all[j:j+i])) == 1:
np = set(l)
#print "naked pair", np
for k, (f, n) in enumerate(news):
if n != np:
#print "Adjusted ", f, n
new = n.difference(np)
if len(new) == 0:
raise ValueError()

if new != n:
pair_found =True
news[k] = (f, new)
if pair_found:
for (x,y), n in sudoko[x][y] = n
return pair_found

class Sudoku(object):
def __init__(self, parent=None):
if parent is None:
self.__field = [[set(xrange(1, 10)) for i in xrange(9)] for j in xrange(9)]
self.__constraints = []
# row constraints
for y in xrange(9):
self.__constraints.append(Constraint([(x,y) for x in xrange(9)]))
# column constraints
for x in xrange(9):
self.__constraints.append(Constraint([(x,y) for y in xrange(9)]))
# field constraints
for xx in xrange(0,9,3):
for yy in xrange(0,9,3):
self.__constraints.append(Constraint([(x+xx, y+yy) for x in xrange(3) for y in xrange(3)]))
else:
self.__field = copy.deepcopy(parent.__field)
self.__constraints = parent.__constraints


def __getitem__(self, index):
class Column(object):
def __init__(self, column, field):
self.__column = column
self.__field = field

def __setitem__(self, index, value):
self.__field[self.__column][index] = value

def __getitem__(self, index):
return self.__field[self.__column][index]

return Column(index, self.__field)

def __repr__(self):
res = [[None for i in xrange(9)] for j in xrange(9)]
col_widths = [0 for i in xrange(9)]
for x in xrange(9):
for y in xrange(9):
vals = list(self[x][y])
vals.sort()
r = condense(vals)
res[x][y] = r
if col_widths[x] < len(r):
col_widths[x] = len(r)

rows = []
for y in xrange(9):
rows.append(" ".join(["%s%s" % (res[x][y], " " * (col_widths[x] - len(res[x][y]))) for x in xrange(9)]))

return "\n".join(rows)

def load(self, instance):
lines = [line for line in instance.split() if line]
for x in xrange(9):
for y in xrange(9):
v = lines[y][x]
if v != "*":
self[x][y] = set([int(v)])


def solve(self):
changed = set([True])
while True in changed:
changed = set([c.apply(self) for c in self.__constraints])
if not self.solved:
#print self
def enum_squares():
sqs = [(len(sq), (pos, sq)) for pos, sq in self.squares if len(sq) > 1]
sqs.sort()
for _, (pos, square) in sqs:
for v in square:
yield pos, v
for (x, y), v in enum_squares():
child = Sudoku(self)
child[x][y] = set([v])
try:
child.solve()
if child.solved:
self.__field = child.__field
return
except ValueError:
pass

def squares(self):
for x in xrange(9):
for y in xrange(9):
yield (x,y), self[x][y]
squares = property(squares)

def solved(self):
return len([1 for _, square in self.squares if len(square) == 1]) == 81
solved = property(solved)



if __name__ == "__main__":
s = Sudoku()
s.load(riddle2)
s.solve()
print s

 

[poissonnier]

Had the same reaction as everyone when I saw theses puzzles a month or
so ago, so here is my solution...
the solve function is recursive, so it can also solve the 'deadlock
set' (example3). find_cell looks for an empty cell with the most filled
cells in it's row and column, so the search tree doesn't grow too
'wide'.

-----------------------------------

example1 = """8 9 - - - - 3 - 4
- - 5 - 3 - - - -
- 7 - - 8 1 5 - -
- 4 - - - 7 - - 3
- - - 5 4 3 - - -
2 - - 1 - - - 5 -
- - 7 9 1 - - 4 -
- - - - 7 - 2 - -
9 - 8 - - - - 7 5"""

example2 = """- 5 2 - - - - - -
9 - - 1 - - - 5 -
- - 4 8 3 - - - 2
- 3 - - 9 - 1 - 5
- - - - - - - - -
5 - 7 - 6 - - 4 -
1 - - - 7 3 6 - -
- 7 - - - 9 - - 3
- - - - - - 2 7 -"""

example3 = """- 3 - 5 - - 8 1 -
1 - - 7 6 - - 9 -
4 - - - - - - - -
8 4 3 9 7 5 1 2 6
- 1 - 6 - - - 7 8
6 - - 8 - 1 9 3 -
- - - 1 5 7 - - 9
- 9 - - 8 6 - - 1
- 6 1 - 9 2 - 8 -"""

class ImpossibleException(Exception): pass


def field_from_string(field_str):
def mapper(x):
if x == '-': return None
else: return int(x)
return [map(mapper, line.split()) for line in
field_str.split('\n')]


def field_from_file(filename):
f = open(filename)
field = field_from_string(f.read())
f.close()
return field


def print_field(field):
def mapper(x):
if x == None: return ' '
else: return str(x)+' '
str_rows = [map(mapper, x) for x in field]
str_rows = ['| ' + " ".join(str_row) + '|' for str_row in str_rows]
print 'x'+'-'*27+'x'
print "\n".join(x for x in str_rows)
print 'x'+'-'*27+'x'


def check_constraint(field, (x,y), num):
"""Checks if putting num at (x,y) is valid."""
#row constraint
occ = [elem for elem in field[x] if elem == num]
if occ:
return False
#column constraint
occ = [field[k][y] for k in range(9) if field[k][y] == num]
if occ:
return False
#subfield constraint
sub_x, sub_y = x//3, y//3
occ = [field[k+3*sub_x][l+3*sub_y] for k in range(3) for l in
range(3)
if field[k+3*sub_x][l+3*sub_y] == num]
if occ:
return False
return True


def find_cell(field):
"""Returns coords of an empty cell or None if all cells are filled.
Returns cells with most row and column 'neighbours' first."""
def count(row):
return len([x for x in row if x is not None])

#[(count, index), ... ]
x_counts = zip((count(row) for row in field), range(9))
sorted_x_counts = sorted(x_counts, reverse=True)
x_keys = [l for k,l in sorted_x_counts]

columns = [[field[k][y] for k in range(9)] for y in range(9)]
y_counts = zip((count(column) for column in columns), range(9))
sorted_y_counts = sorted(y_counts, reverse=True)
y_keys = [l for k,l in sorted_y_counts]

for x in x_keys:
for y in y_keys:
if field[x][y] == None:
return (x,y)
else:
return None


def set_value(field, (x,y), num):
"""Returns copy of field with cell (x,y) set to num."""
#new_field = copy.deepcopy(field)
new_field = [row[:] for row in field]
new_field[x][y] = num
return new_field


def solve(field):
xy = find_cell(field)
if not xy:
return field
poss = [e for e in range(1,10) if check_constraint(field, xy, e)]
for e in poss:
new_field = set_value(field, xy, e)
try:
return solve(new_field)
except ImpossibleException:
pass #try next possibility
raise ImpossibleException()


if __name__ == '__main__':
field = field_from_string(example3)
print 'initial field:'
print_field(field)
print 'solution:'
try:
print_field(solve(field))
except ImpossibleException:
print 'not solvable'

 

[Anton Vredegoor]

As everyone posts his, I'll do the same It uses some constraint based
solving techniques - but not too complicated ones. When stuck, it
backtracks. So far it never failed me, but I haven't tested it too
thouroughly.

Thanks to all for sharing. I like to program sudoku and review such
code. So below here is my current file, I think it uses some techniques
not yet posted here. It also has a difficult 16x16 puzzle which I know
to be solvable (barring typing mistakes) but which my file can't solve
before I get tired of waiting, this might draw some heavyweights in the
ring

I have also read the sudoku wiki page:

http://en.wikipedia.org/wiki/Sudoku

which was very helpfull and interesting (especially the link to Knuths
paper about dancing links was nice, even though I think (but maybe
wrongly so) that we don't need dancing links now that we've got sets,
but it's still a very very interesting paper)

I think the first important step is to realize that some variations
have fewer values so that it is possible to reduce the search space
early. Currently I'm exploring ideas about contigengies as explained in
the wiki above which seems promising, but I haven't found a nice way to
implement them yet. Maybe an easy optimization would be to find values
that don't come up often and choose variations containing those. And
maybe I should switch to an approach that has possibility values inside
the cells instead of computing them on the fly each time, that could
make contigency elimination easier.

Anton


from __future__ import generators
from sets import Set as set

problem1 = ['063000700','000690008','900007002',
'002010080','050806090','090070200',
'600100003','700045000','009000140']

problem2 = ['030009007','010080000','000100090',
'004905006','020000010','500607400',
'050001000','000040020','700500030']

problem3 = ['030500810','000760090','400000000',
'043905006','010000070','600801930',
'000000009','090086000','061002080']

problem4 = ['004530080','060009000','900000005',
'000800350','000000000','027006000',
'800000007','000300040','090072600']

X =[' 1 0 0 0 0 12 0 10 11 7 6 0 0 4 0 0',
' 0 7 0 0 15 13 0 0 0 0 2 0 0 8 0 0',
' 3 0 0 0 4 0 0 0 0 5 0 12 0 16 0 0',
' 0 0 14 2 0 9 0 0 0 0 1 0 0 0 0 0',
'10 15 0 1 0 0 0 2 0 16 0 0 3 0 0 0',
'12 0 0 3 0 0 15 0 0 13 0 4 0 1 9 5',
' 5 0 11 0 7 0 8 0 0 0 0 0 0 15 0 0',
' 7 13 0 16 0 0 0 6 0 0 0 14 0 10 0 0',
' 0 0 13 0 11 0 0 0 10 0 0 0 1 0 12 0',
' 0 0 7 0 0 0 0 0 0 3 0 16 0 14 0 13',
'16 8 0 0 14 0 5 0 0 15 0 0 4 0 0 6',
' 0 0 0 9 0 0 4 0 1 0 0 0 2 0 0 7',
' 0 0 0 0 0 16 0 0 0 0 8 0 10 5 0 0',
' 0 0 4 0 12 0 6 0 0 0 16 7 0 0 0 14',
' 0 0 6 0 0 1 0 0 0 0 12 13 0 0 11 0',
' 0 0 15 0 0 8 11 3 2 0 9 0 0 0 0 1']

problem5 = [row.split() for row in X]

class State:

def __init__(self,solved,unsolved):
self.solved = solved
self.unsolved = unsolved
self.size = int((len(solved)+len(unsolved))**.25)

def choiceset(self,x,y):
"the set of possible choices for an empty cell"
sz = self.size
res = set(range(1,sz*sz+1))
r,c = x/sz*sz,y/sz*sz
for (i,j),v in self.solved.iteritems():
if x == i or y == j or (r<=i<r+sz and c<=j<c+sz):
res.discard(v)
return res

def celldict(self):
"""dictionary of (cellcoords,choiceset) for each empty cell
if *any* empty cell cannot be filled return an empty dict
to signal an illegal position
"""
res = {}
for x,y in self.unsolved:
c = self.choiceset(x,y)
if not c:
return {}
res[x,y] = c
return res

class Node:

def __init__(self,state):
self.state = state
self.issolved = not bool(state.unsolved)

def children(self):
state = self.state
cd = state.celldict()
if cd: #position is still legal
ml = min([len(x) for x in cd.itervalues()])
#select empty cells which have the minimum number of
choices
items = [(k,v) for k,v in cd.iteritems() if len(v) == ml]
(x,y),S = min(items) #arbitrary choice of cell here
for v in S:
solved,unsolved =
dict(state.solved),dict(state.unsolved)
solved[x,y] = v
del unsolved[x,y]
yield Node(State(solved,unsolved))

def __repr__(self):
R = range(self.state.size**2)
res = [["__" for i in R] for j in R]+['']
for (i,j),v in self.state.solved.iteritems():
res[j] = "%02i" %v
return '\n'.join(map(' '.join,res))

def solutions(N):
if N.issolved:
yield N
else:
for child in N.children():
for g in solutions(child):
yield g

def todicts(P):
M = [map(int,row) for row in P]
solved = {}
unsolved = {}
for i,row in enumerate(M):
for j,x in enumerate(row):
if x:
solved[i,j] = x
else:
unsolved[i,j] = x
return solved,unsolved

def test():
solved,unsolved = todicts(problem4)
N = Node(State(solved,unsolved))
print N
for S in solutions(N):
print S

if __name__=='__main__':
test()

 

[Gregory Bond]

My current solver does 1 level of backtracking (i.e. constant space, and
bounded time) only, and it has been able to solve every puzzle I've
thrown at it. It's based on the usual logic and book-keeping for the
most part. (It also explains how it comes up with each answer step as
it goes, which is handy...)

Once it gets to the stage where it needs to guess, it arranges all the
unknowns then tries them in some arbitary order. It saves the state,
applies the guess (square x,y is N) and then re-applies all the logic
rules. There are 3 possible outcomes from here:

- We've solved it, which is good (this happens surprisingly often....)

- We can't solve it using this guess (so ignore this possibility,
restore the state & try the next guess)

- The Resulting puzzle is badly formed / inconsistant (represented by
a python exception, naturally!) In this case, we know the guessed
square/number is not valid, so we backtrack (restore the state before we
made this guess), remove that possibility (x,y is N) and then apply all
the logic rules again. Often times, this is enough to solve, but it
usually progreses things a little even if it doesn't solve it.

I've not yet found a (9x9) puzzle that this cannot solve. The downside
is that it cannot detect cases where there are multiple solutions.

 

[Antoon Pardon]

Bas ha escrito:

Hi group,

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.

It basically works by listing all 9 possible numbers for all 81 fields
and keeps on striking out possibilities until it is done.
[snip]

This problem is desperately begging for backtracking.

I don't think so. I regularly solve one and I never needed
to try something out, to see if it worked or not except
when there were muliple solutions.

I think it is a beautifull problem, to make people think of
how they could code some of their thought processes, which
would be a more fruitfull experience as programming this
with backtracking.

 

[Antoon Pardon]

the only way to solve arbitrary sudoku problems is to guess.

That is strange, in al the puzzles that I have solved untill now,
I never needed to guess, unless the puzzle had multiple solutions,
which personnally I find inferior.

 

[Gerard Flanagan]

I like to program sudoku and review such
code.

Some non-Python examples:


APL (The Horror! The Horror!...):

http://www.vector.org.uk/archive/v214/sudoku.htm

and my own effort with Excel/C# (very humble - needs work):

http://exmachinis.net/code/cs/2005/08/4.html

 

[Caleb Hattingh]

Very interesting that sudoku solving appears on the python group - there
is a programming competition at mathschallenge.net (euler) where one of
the puzzles is developing a sudoku solving algorithm...

Actually the python entrants are giving the C guys a good run!

Op 2005-09-16, (e-mail address removed) schreef

Bas ha escrito:

Hi group,

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.

It basically works by listing all 9 possible numbers for all 81 fields
and keeps on striking out possibilities until it is done.
[snip]

This problem is desperately begging for backtracking.

I don't think so. I regularly solve one and I never needed
to try something out, to see if it worked or not except
when there were muliple solutions.

I think it is a beautifull problem, to make people think of
how they could code some of their thought processes, which
would be a more fruitfull experience as programming this
with backtracking.

 

[david.blume]

Bas, you and I are both a little late to the sudoku python experience.
Here's my feeble attempt:
http://home.earthlink.net/~daliblume/Download/sudoku/index.html
Inspired by this article: http://somethinkodd.com/oddthinking/?p=21

Excellent strategies are provided by Dan Rice's blog:
http://sudokublog.typepad.com/sudokublog/2005/08/two_and_three_i.html

You won't find any better solver than this:
http://sudoku.sourceforge.net/

 

[Tom Anderson]

Excellent strategies are provided by Dan Rice's blog:
http://sudokublog.typepad.com/sudokublog/2005/08/two_and_three_i.html

There's an interesting remark in this post:

http://sudokublog.typepad.com/sudokublog/2005/08/where_do_sudoko.html

"Some Sudoku generators skip the step of generating a board altogether.
It's enough to place some random numbers in the board and see if it has a
solution. For a backtracking solver, which can solve puzzles very quickly,
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
the time wasted analyzing impossible sets of clues will be minor. For a
human-style solver, it seems reasonable to exclude the possibility of
self-contradictory clues by first generating a consistent underlying
board."

He seems to think that backtrackers are faster than reasoners. That's
somewhat counter-intuitive; i wonder if it's really true. It would
certainly be rather sad if it was.

You won't find any better solver than this:
http://sudoku.sourceforge.net/

That's a fairly straightforward backtracker. In fact, it's the solver
which inspired me to write mine - which i believe has a more sophisticated
heuristic (i haven't compared them formally, but my heuristic
sophistication estimation heuristic - which is itself, of course, fairly
sophisticated - suggests that it is). Clearly, what we need is a sudoku
solver shootout.

tom

 

[Tom Anderson]

That is strange, in al the puzzles that I have solved untill now, I
never needed to guess, unless the puzzle had multiple solutions, which
personnally I find inferior.

Well, if we are to believe Lance Fortnow, a fairly expert comptational
complexionist, that's probably not generally true:

http://weblog.fortnow.com/2005/08/sudoku-revisited.html

It's this bit:

"Since we don't believe that NP has fast probabilistic algorithms, we
expect that there are no efficient procedures to completing a generalized
Sudoku grid"

That makes me think that there probably isn't a non-backtracking method,
since that would almost certainly be polynomial-time.

The thing is, the puzzles you encounter in the wild have been designed to
be solved by humans, using non-backtracking methods; they're much easier
to solve than the general class of Sudoku.

tom