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 news:
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
--
http://mail.python.org/mailman/listinfo/python-list
