8 replies to this topic

[puuhikki]

Prove that there is a 11x11 -grid filled with digits such that one can read the squares of 1,...,100 on it. Reading means there you can fix the starting square on the direction (8 possibilities) and go to that direction as many steps as you like. Solutions found by computer are allowed.

[WingedPanther]

And your question is...?

[puuhikki]

What kind of algorithm would solve the problem?

[WingedPanther]

I would probably slowly fill in the grid, marking off numbers that exist in it as I go, and making sure that each new number I fill in enables me to cross off several of the remaining numbers.

[puuhikki]

Hmm. I found a C++-program which tries to put numbers 100^2, then 99^2 and so on to the grid. It looks like it uses the best-first search. But after running the program three days, it is able to put the numbers 46^2 to 100^2 to the board. So I think a better method is needed or at least a huge amount of CPU time.

[Hoffmann Peter]

Just to understand the problem:
You would like to have a grid filled with square numbers from 1^2 to 100^2. Can you repeat the condition? I think I didn't get it

[puuhikki]

I mean there is a 11x11 grid filled with digits. If we fix a starting grid and a direction (8 possibilities) and we can find digits 9, 6, 0, 4 consecutively we have found 98^2 on the board. For example the 2x2 grid
1 6
8 4

contains the squares of 1, 2, 4, 8, and 9.

[Hoffmann Peter]

So I will reformulate the problem:
Is it possible (and if yes, how) to arrange the decimal representation of all numbers from 1² to 100² on a 11x11 grid?

1. Step: Create a list of all numbers.
2. Step: Remove all numbers from you list that are contained in another number in both directions (81 numbers to go).

1 is contained in 16
4 is contained in 49
9 is contained in 49
16 is contained in 169
25 is contained in 225
36 is contained in 361
49 is contained in 1849
64 is contained in 1764
81 is contained in 1681
100 is contained in 8100
144 is contained reversed in 441
169 is contained reversed in 961
225 is contained in 1225
324 is contained in 3249
400 is contained in 6400
441 is contained reversed in 1444
625 is contained in 5625
900 is contained in 4900
1089 is contained reversed in 9801

3. Step: Count the remaining number of digits that need to be placed inside the grid (312) - thus count the number of digits that need to be "overlayed" (191).
4. Step: In progress

[zoranh]

All numbers you're looking for are less or equal to 100^2, i.e. up to 5 digits, there are 11^2 cells in the grid and 8 directions. So why not brute force?

It's only 5 * 121 * 8 steps which is less than 5000 comparisons. Shouldn't take much more than 1 msec to complete...