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