Solving an optimization problem by Sage

I would like to know how one can solve the following optimization problem using Sage.

I would like to have a matrix where every element is an integer from 0 to 9. One can read numbers from the matrix by choosing the starting element and direction from one of the eight direction (horizontal, vertical, diagonal) and go to that direction 0 to 5 steps and concatenate the numbers.

For example, one can read the squares of 1 to 10 from the following matrix:

0 0 1 8 2
3 6 4 9 5

Now the problem is to find an $n\times m$ matrix with digits from 0 to 9 where one can read the squares of 1 to 100 in a way described above where $nm$ is the smallest possible. How can I do that on Sage? Can Sage do it for example in the case 12x10 griid? Does for example simulated annealing or genetic algorithm work in here, or is it easy to implement the algorithm in https://stackoverflow.com/questions/9... ? I would like to see how good result we can achieve.

edit retag close merge delete

General note : this marvelous book has a nice set of discussions about various optimization problems...

Sort by » oldest newest most voted

There is a Python program to solve 11x11 case in https://stackoverflow.com/questions/3...

more 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, path
direction = (second-first, second-first)
# 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]-path[i-1], path[i]-path[i-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.

more

1

Thanks for that! I think this proves the minimality of the example. But the case I would like to solve is much bigger. I think it might be solved by genetic algorithm of by simulated annealing but I have no experience of implementing those.