Krdytkyu

I would like to solve a problem from https://stackoverflow.com/questions/44983929/proving-that-a-particular-matrix-exists?noredirect=1&lq=1

I found this problem in a programming forum Ohjelmointiputka:

https://www.ohjelmointiputka.net/postit/tehtava.php?tunnus=ahdruu and

https://www.ohjelmointiputka.net/postit/tehtava.php?tunnus=ahdruu2

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

Prove that there is a matrix with 117 elements containing the 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.

I found that if there is such a matrix $m times n$, we may assume without loss of generality that $m le n$. Therefore, the matrix must be of the type 1x117, 3x39 or 9x13. But what kind of algorithm will find the matrix?

I have managed to do the program that checks if numbers to be added can be put on the board. But how can I implemented the searching algorithm?

This looks a hard problem but one has solved the case 121 for 11x11 grid in https://stackoverflow.com/questions/3382859/solving-a-recreational-square-packing-problem?noredirect=1&lq=1 .

I was unable to modify this to the 9x13 case.

But can how one can write a code that can be used for any size rectangle?

I was able to write the code for 11x11 case as follows. But is this easy to generalized?

# Coordinates like in unit circle with 45 degree steps.

# means right, 1*45 means up right...

def getnumber(matrix, x, y, length, direction):

    dx = [1, 1, 0, -1, -1, -1, 0, 1]

    dy = [0, -1, -1, -1, 0, 1, 1, 1]

    s = ""

    for i in range(length):

        try:

            s += matrix[y+dy[direction]*i][x+dx[direction]*i]

        except IndexError:

            break

    return s



# This puts number to the board.

def putnumber(matrix, x, y, number, direction,emptychar):

    dx = [1, 1, 0, -1, -1, -1, 0, 1]

    dy = [0, -1, -1, -1, 0, 1, 1, 1]

    for i in range(len(number)):

        if matrix[y+dy[direction]*i][x+dx[direction]*i] not in (number[i],emptychar):

            return None

        matrix[y+dy[direction]*i][x+dx[direction]*i] = number[i]       

    return matrix



# This generates all numbers.

def gen_numbers(limit):

    numbers = 

    i = limit**2

    numbers.append(str(i))



    tmp = ""

    for j in range(limit):

        i = (limit-j)**2

        if str(i) not in tmp:

            if str(i)[::-1] not in tmp:

                numbers.append(str(i))

                tmp += str(i)+" "

    tmp = tmp[0:len(tmp)-1]

    numbers = tmp.split(" ")

    return numbers



# def get_all_indexes(5,8,"10000",2);

def get_all_indexes(x,y,number,direction):

    dx = [1, 1, 0, -1, -1, -1, 0, 1]

    dy = [0, -1, -1, -1, 0, 1, 1, 1]



    j = 

    for i in range(len(number)):

        j.append([x+dx[direction]*i,y+dy[direction]*i])

    return j





def get_numbers_near_index(matrix, x, y, length):

    j = 

    for direction in range(9):

        j.append(getnumber(matrix, x, y, length, direction))

#    print(j)

    j = list(set(j))

    return j



# This method prints a matrix.

def printmatrix(Matrix):

    if Matrix is not None:

        for i in range(w):

            print(Matrix[i])      



# Creates a grid of width 11 and height 11.

w, h = 11, 11

# Defines what we put if an tem in the grid is empty

emptychar = 'X'

# This is the maximum number of integer whose square we put to the table.

limit = 100

# Create an empty array

Matrix = [[emptychar for y in range(w)] for x in range(h)]

# We put to the location Matrix[put_x][put_y] the number "number" going to the direction.

#



coords = [[5,8,2,100**2],

          [3,9,1,99**2],

          [0,4,7,98**2],

          [3,0,7,97**2],

          [0,7,6,96**2],

          [0,1,7,95**2],

          [4,10,4,94**2],

          [3,10,3,93**2],

          [4,10,1,92**2],

          [2,8,0,91**2],

          [7,8,3,90**2],

          [8,0,4,89**2],

          [2,1,0,88**2],

          [9,8,3,87**2],

          [10,1,5,86**2],

          [3,1,6,85**2],

          [8,5,6,84**2],

          [0,6,7,83**2],

          [10,9,4,82**2],

          [6,10,2,81**2],

          [6,8,1,80**2],

          [7,4,2,79**2],

          [1,5,6,78**2],

          [5,3,0,77**2],

          [5,3,3,76**2],

          [8,7,6,75**2],

          [10,3,2,74**2],

          [10,3,3,73**2],

          [6,9,3,72**2],

          [5,3,2,71**2],

          [7,2,5,70**2],

          [4,0,5,69**2],

          [7,9,1,68**2],

          [3,7,4,67**2],

          [10,6,6,66**2],

          [2,7,7,65**2],

          [4,1,7,64**2],

          [9,2,5,63**2],

          [9,2,4,62**2],

          [10,7,5,61**2],

          [2,5,0,60**2],

          [2,5,7,59**2],

          [7,5,1,58**2],

          [9,0,5,57**2],

          [9,0,6,56**2],

          [7,5,7,55**2],

          [0,3,6,54**2],

          [3,8,1,53**2],

          [3,2,0,52**2],

          [3,2,4,51**2],

          [2,3,7,50**2],

          [3,8,3,49**2],

          [7,3,7,48**2],

          [7,3,5,47**2],

          [4,9,1,46**2],

          [6,4,4,45**2],

          [10,4,4,44**2],

          [5,0,7,43**2],

          [10,10,3,42**2],

          [10,4,3,41**2],

          [6,6,0,40**2],

          [7,10,0,39**2],

          [0,9,1,38**2],

          [9,1,6,37**2],

          [0,9,2,36**2],

          [1,3,0,35**2],

          [0,2,7,34**2],

          [6,6,5,33**2],

          [1,3,2,32**2],

          [0,7,2,31**2],

          [6,5,4,30**2],

          [7,8,6,29**2],

          [1,9,1,28**2],

          [2,1,4,27**2],

          [2,0,6,26**2],

          [3,5,1,25**2],

          [8,7,7,24**2],

          [2,4,4,23**2],

          [3,7,7,22**2],

          [2,7,5,21**2],

          [10,6,4,20**2],

          [2,5,4,19**2],

          [3,3,6,16**2],

          [0,2,2,14**2]

          ]

for row in range(0,len(coords)):

#    coords = [coords[4*row+0],coords[4*row+1],coords[4*row+2],coords[4*row+3]]

    datarow = [str(coords[row][3]),coords[row][0],coords[row][1],coords[row][2]] 

    Matrix = putnumber(Matrix, datarow[1], datarow[2], datarow[0], datarow[3], emptychar)

printmatrix(Matrix)

nextrow = coords[row]

print((int(nextrow[3]**0.5)-1)**2)