Prev: Python 2.4 decompiler
Next: triangulation
From: Benji York on 17 Sep 2005 09:42
Sybren Stuvel wrote:
>>def all(seq, pred=bool):
>
> What's this? What is bool?

See http://docs.python.org/lib/built-in-funcs.html#l2h-10
--
Benji York
From: David Durkee on 17 Sep 2005 09:46
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?

From: Bas on 17 Sep 2005 10:07
>> 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

From: Diez B. Roggisch on 18 Sep 2005 06:00
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
From: poissonnier@gmail.com on 18 Sep 2005 08:19
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'

First  |  Prev  |  Next  |  Last
Pages: 1 2 3 4
Prev: Python 2.4 decompiler
Next: triangulation