Solving an optimization problem by Sage

edit

Nice problem! Here is a brute force solution. First we define some convenient helper functions:

import itertools

def digit_matrix_to_digit_positions(M):
    positions = { d: [] for d in range(0,10)}
    for i in range(0, M.nrows()):
        for j in range(0, M.ncols()):
            positions[M[i,j]].append((i,j))
    return positions

def digit_paths_for_number(digit_positions, number):
    digits = map(int, str(number))
    return itertools.product(*[digit_positions[d] for d in digits])

def is_digit_path_allowed(path):
    if len(path) == 0: return False
    if len(path) == 1: return True
    # determine direction of path
    first, second = path[0], path[1]
    direction = (second[0]-first[0], second[1]-first[1])
    # check if direction is valid
    if not all(d in [-1,0,1] for d in direction): return False
    # check if the rest of the path goes in this direction
    if len(path) == 2: return True
    return all((path[i][0]-path[i-1][0], path[i][1]-path[i-1][1]) == direction for i in range(2, len(path)))

def digit_matrix_contains_numbers(M, numbers):
    digit_positions = digit_matrix_to_digit_positions(M)
    for number in numbers:
        if len(filter(is_digit_path_allowed, digit_paths_for_number(digit_positions, number))) == 0:
            return False
    return True

Now we can e.g. verify your example:

sage: M = Matrix(ZZ, [[0,0,1,8,2], [3,6,4,9,5]])
sage: digit_matrix_contains_numbers(M, [x^2 for x in range(0, 11)])
True
sage: filter(is_digit_path_allowed, digit_paths_for_number(digit_matrix_to_digit_positions(M), 100))
[((0, 2), (0, 1), (0, 0))]

To find the smallest digit matrix with this property, we iterate over $n\times m$ digit matrices with $N=nm \geq 9$:

numbers = [x^2 for x in range(0, 11)]
needed_digits = set(sum((map(int,str(y)) for y in numbers), []))
found = False
N = len(needed_digits)
while True:
    for n in divisors(N):
        m = N/n
        if m < n: continue # equivalent to m x n anyway
        print 'Trying', n, 'x', m
        for matrix_entries in itertools.product(range(0,10), repeat=n*m):
            if len(needed_digits & set(matrix_entries)) < len(needed_digits): continue
            matrix = Matrix(ZZ, [[matrix_entries[i*m+j] for j in range(0,m)] for i in range(0,n)])
            if digit_matrix_contains_numbers(matrix, numbers):
                found = True
                print 'Found one!'
                print matrix
                break
        if found: break
    if found: break
    N += 1

The output after several hours is:

Trying 1 x 9
Trying 3 x 3
Trying 1 x 10
Trying 2 x 5
Found one!
[0 0 1 3 2]
[9 4 6 8 5]

So $2 \times 5$ (or $5 \times 2$ after transposition) is minimal. You can also let the code print all the solutions, if you want.

It would be interesting to see other approaches.