enigma_1750.py

import itertools
from collections import defaultdict

GRID_SIZE = 3

on_grid = lambda (a, b) : (0 <= a < GRID_SIZE) and (0 <= b < GRID_SIZE)

def gen_neighbours((a, b)):
    for i, j in itertools.product((-1, 0, 1), repeat=2):
        a_prime = a + i
        b_prime = b + j
        if on_grid((a_prime, b_prime)):
            yield (a_prime, b_prime)

def gen_paths(path):
    for square_prime in gen_neighbours(path[-1]):
        if square_prime in path:
            continue
        for result in gen_paths(list(path) + [square_prime]):
            yield result
    else:
        if len(path) == (GRID_SIZE ** 2):
            yield tuple(path)

last_digit = lambda x : x % 10
concat_ints = lambda xs : int(''.join(str(x) for x in xs))
fmt_set = lambda a : '{%s}' % ','.join(map(str, sorted(a)))

divisor_count = lambda x : sum(x % z == 0 for z in xrange(1, (GRID_SIZE ** 2) + 1))

def main():
    # find all paths. represent paths as lists of (y, z) pairs for simplicity
    all_paths = set()
    grid = list(itertools.product(range(GRID_SIZE), repeat=2))
    all_paths = set(p for square in grid for p in gen_paths([square]))
    print 'Generated %d paths on the grid.' % len(all_paths)
    
    # convert paths of (y, x) pairs to numbers
    square_to_number = {x:(i+1) for i, x in enumerate(grid)}
    all_numbers = [concat_ints(square_to_number[x] for x in p) for p in sorted(all_paths)]
    # partition numbers by last digit
    numbers_by_last_digit = defaultdict(list)
    for x in all_numbers:
        numbers_by_last_digit[last_digit(x)].append(x)
    # characterise each partition by set of all divisor-counts
    for d in sorted(numbers_by_last_digit):
        xs = numbers_by_last_digit[d]
        chi = set(divisor_count(x) for x in xs)
        print 'Path-numbers ending with %d are all %s-times divisible.' % (d, fmt_set(chi))
        if chi != set((4, 5)):
            continue
        print '*** FOUND SOLUTION: there are %d such path-numbers.' % len(xs)
        break

if __name__ == '__main__':
    main()