How to simplify square finding program?

[meknowsnothing]

I found this problem in a programming forum Ohjelmointiputka:

https://www.ohjelmointiputka.net/postit/...nus=ahdruu and
https://www.ohjelmointiputka.net/postit/...us=ahdruu2

Somebody said that there is a solution found by a computer, but I was unable to find a proof.

Find the smallest rectangle digits such that one can read the squares of the numbers 1, 2, ..., 100.

Here read means that you fix the starting position and direction (8 possibilities) and then go in that direction, concatenating the numbers. For example, if you can find for example the digits 1,0,0,0,0,4 consecutively, you have found the integer 100004, which contains the square numbers of 1, 2, 10, 100 and 20, since you can read off 1, 4, 100, 10000, and 400 (reversed) from that sequence.

But there are so many numbers to be found (100 square numbers, to be precise, or 81 if you remove those that are contained in another square number with total 312 digits) and so few integers in a matrix that you have to put all those square numbers so densely that finding such a matrix is difficult, at least for me.

What kind of algorithm will find the matrix?

I saw from https://stackoverflow.com/questions/3382...ng-problem that the following program solves the problem in the case 11x11:

#
# An attempt to solve a nice problem from SO using a random search approach
#
# The problem is to place the squares of all numbers from 1 to 100 in
# a 11x11 grid writing them either horizontally, vertically or in diagonal.
# 11*11 is only 121 and this means that the required packing is very tight
# (the total number of digits is 358, giving that on average each grid
# cell needs to be used for 2.95 different square numbers).
#
# Do whatever you want with this code, just don't blame me if it doesn't
# do what you think or if it even doesn't do what I say it does.
#
# Andrea "6502" Griffini
#

import random, time, sys

N = 11
K = 100

# These are the numbers we would like to pack
numbers = [str(i*i) for i in xrange(1, K+1)]

# Build the global list of digits (used for weighted random guess)
digits = "".join(numbers)

def random_digit(n=len(digits)-1):
    return digits[random.randint(0, n)]

# By how many lines each of the numbers is currently covered
count = dict((x, 0) for x in numbers)

# Number of actually covered numbers
covered = 0

# All lines in current position (row, cols, diags, counter-diags)
lines = (["*"*N for x in xrange(N)] +
         ["*"*N for x in xrange(N)] +
         ["*"*x for x in xrange(1, N)] + ["*"*x for x in xrange(N, 0, -1)] +
         ["*"*x for x in xrange(1, N)] + ["*"*x for x in xrange(N, 0, -1)])

# lines_of[x, y] -> list of line/char indexes
lines_of = {}
def add_line_of(x, y, L):
    try:
        lines_of[x, y].append(L)
    except KeyError:
        lines_of[x, y] = [L]
for y in xrange(N):
    for x in xrange(N):
        add_line_of(x, y, (y, x))
        add_line_of(x, y, (N + x, y))
        add_line_of(x, y, (2*N + (x + y), x - max(0, x + y - N + 1)))
        add_line_of(x, y, (2*N + 2*N-1 + (x + N-1 - y), x - max(0, x + (N-1 - y) - N + 1)))

# Numbers covered by each line
covered_numbers = [set() for x in xrange(len(lines))]

# Which numbers the string x covers
def cover(x):
    c = x + "/" + x[::-1]
    return [y for y in numbers if y in c]

# Set a matrix element
def setValue(x, y, d):
    global covered
    for i, j in lines_of[x, y]:
        L = lines[i]
        C = covered_numbers[i]
        newL = L[:j] + d + L[j+1:]
        newC = set(cover(newL))
        for lost in C - newC:
            count[lost] -= 1
            if count[lost] == 0:
                covered -= 1
        for gained in newC - C:
            count[gained] += 1
            if count[gained] == 1:
                covered += 1
        covered_numbers[i] = newC
        lines[i] = newL

def do_search(k, r):
    start = time.time()

    for i in xrange(r):
        x = random.randint(0, N-1)
        y = random.randint(0, N-1)
        setValue(x, y, random_digit())

    best = None
    attempts = k
    while attempts > 0:
        attempts -= 1
        x = random.randint(0, N-1)
        y = random.randint(0, N-1)
        old = lines[y][x]
        setValue(x, y, random_digit())
        if best is None or covered > best[0]:
            now = time.time()
            sys.stdout.write(str(covered) + chr(13))
            sys.stdout.flush()
            attempts = k
        if best is None or covered >= best[0]:
            best = [covered, lines[:N][:]]
        else:
            setValue(x, y, old)
    print
    sys.stdout.flush()
    return best

for y in xrange(N):
    for x in xrange(N):
        setValue(x, y, random_digit())

best = None
while True:
    if best is not None:
        for y in xrange(N):
            for x in xrange(N):
                setValue(x, y, best[1][y][x])
    x = do_search(100000, N)
    if best is None or x[0] > best[0]:
        print x[0]
        print "\n".join(" ".join(y) for y in x[1])
    if best is None or x[0] >= best[0]:
        best = x[:]

But how this can be generalized to solve the problem in non-square cases? I heard that the squares if integers 1–100 can be put to the grid of 117 elements (https://www.ohjelmointiputka.net/postit/...us=ahdruu2) . And how this code can be simplified?