Prev: Python 2.4 decompilerNext: 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 decompilerNext: triangulation