Proving the existence of a given matrix

Question

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 9×13 matrix containing the digits such that one can read the square 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 grid (9*13 = 117 digits, to be precise) that you have to put all those square numbers so densely that finding such a matrix is difficult, at least for me.

TL;DR  In other words, make a "number-search" puzzle (like a word-search, but with digits) where the numbers to be included are the squares of the numbers from 1 to 100.  The puzzle grid must be 9×13 digits.

Answer 1

The only way to prove is to make it, which is very tedious.

It is trivial to show it might possibly exist or not - we require at least N 1s, M 2s etc to build all numbers with that digit. If we consider every instance of a digit to be a part of max 4 numbers (lower bound as long as the digit is not on the edge or in the corner), we can easily show this might indeed be possible.

Now let's say we want to build it.

We need to focus mostly on 4 digit numbers - there are more of these and they are harder to obtain than 3 digit numbers (which are sometimes contained in 4 digit ones anyway). All 1 or 2 digit ones are trivially present as part of (5X)^2.

We have in total 358 digits

0: 40
1: 48
2: 44
3: 21
4: 50
5: 27
6: 48
7: 19
8: 24
9: 37

So, lets start looking at 3 and 7 as those two are the rarest. Numbers that are interesting with 3 or 7 are 3364, 3721, 7396, 8836 (double 8s, 8 is not that common either), 5776 and 7744. Out of these, 3721 and 7396 have 3 and 7 together (and are the only two with both). It would make sense to have number 127396 to have a single 3+7 junction. 5776 should be a part of something that has 57, say 965776. There is no 67 - there is no 76xx and a square never ends with 7. Now lets link these 2 and obtain a nice 10 digit number 1273965776, which contains 4 squares. No way to (relevantly) stuff it further with 3 or 7 in this direction. Let's move to the same number, other direction. There is a single 3, let's put double 3 on that number and make it along a diagonal to avoid making another 37 which would be irrelevant. Now we see we have obtained 36 by that new 3 and existing 6. It might be a part of 8836, fill that out. Out of 7s already here, we can use one to make the other double 7, in such a way there is no additional 77 generated, nor is there 37. Suppose it is the first 7 and also goes in the same half-space as 3364 (perpendicular to it).

Etc etc. I can't be bothered to continue further. You can if you wish.

There is no meaningful analysis and thinking to do, it is a programming exercise. Start with a number in top left corner, say we are starting from big to small and go with 10000. Put the next number (9801) to have highest overlap with current numbers. Then put the next one (9604) to maximize overlap again etc etc, until you reach 1 and end. On contradiction (no spaces left), remove last placed number and put it on the next best spot. Repeat until you find a solution. Keep going, and if you find 4 solutions in the end, it is unique, just mirrored (horizontally, vertically or both).

EDIT: This programming exercise did not work. Sure, it is increasing number of placed numbers, but far too slow to be worth waiting for an eventual solution. I might later try to make it work using better approaches, like first placing all numbers with 7 (minimizing number of 7s in the process), then with 3 etc - by rarity. Maybe. Who knows if it works. The thingy is incredibly dense and it isn't merely required to wiggle numbers a little bit and have it all fit.

Answer 2

Probably this should be a comment, but it's too long for that.
Here's a description of the complete list of numbers to be included in the matrix.

Squares of numbers for which $x\le10$ holds, are contained by the square of $10\times x$ (e.g. $7^2=49$, $70^2=4900$). Furthermore $20^2=400$ is contained by $80^2=6400$ and $30^2=900$ by $70^2=4900$.

$12^2=144$ and the reversal of $21^2=441$ are both contained by $38^2=1444$.

$13^2=169$ is a reversal of $31^2=961$.

$15^2=225$ and $25^2=625$ are contained by $35^2=1225$ and $75^2=5625$ respectively.

$18^2=324$ is contained by $57^2=3249$.

$33^2=1089$ is a reversal of $99^2=9801$.

So the numbers to be placed in the grid are the squares of integers in the range of $[11, 100]$, except $12$, $13$, $15$, $18$, $20$, $21$, $25$, $30$ and $33$.

Answer 3

Partial solution. Here is a 9x13 grid that has the first 94 squares:

1115628965776
5265341929255
2900180239226
1720344770511
2533942328012
1369547612066
6400676748033
3844896291698
5184946889118