Mythic squares/rectangles
 

While we have heard of magic squares. I started to wonder about a different kind of square (or rectangle). Most of us have worked a word search in our day. I thought about a number search.

The question is what is the minimum size and proper configuration such that you can find within the square/rectangle all numbers from 1->n? This is using the conventional word search rules: straight lines only, continuous, either direction.

The following is the minimum for 1->9. The configuration is irrelevant.
[CODE][FONT="Fixedsys"]1 2 3
4 5 6
7 8 9[/FONT][/CODE]
With a careful rearrangement and going from a 3 x 3 square to a 4 x 3 rectangle we can go much further. The following yields 1-> 21
[CODE][FONT="Fixedsys"]5 9 3 0
6 1 2 1
7 8 4 1
[/FONT][/CODE]

So what would it take to get to n = 50 or n = 100 or n =1000?
I have put only a very little effort into this. And I have to be AFT for a few hours. Figured that it would be an interesting challenge, either by hand, programmatically, or in theory.

I misunderstood your "straight lines only" rule and thought you meant only horizontal and vertical lines. Once i realized you also include diagonal lines, I see how your 4x3 could get from 1->21. I found a small improvement to get from 1->24 with:
[code]
5932
6124
7810
[/code]
If we treat the grid like a torus then that same group will go from 1->32.

I really like this puzzle. I think the flat x,y grid will be able to get up to around [c]n = 2*x*y[/c] and the torus x,y grid might be able to get up to around [c]n = 4*x*y[/c] These are just wild guesses. Hopefully someone can come up with better bounds. I'm going to try running a python program to see if I can come up with some other/better solutions.

[QUOTE=WraithX;493546]I misunderstood your "straight lines only" rule and thought you meant only horizontal and vertical lines. Once i realized you also include diagonal lines, I see how your 4x3 could get from 1->21. I found a small improvement to get from 1->24 with:
[code]
5932
6124
7810
[/code]
If we treat the grid like a torus then that same group will go from 1->32.
[/QUOTE]

You can get to 25 by just swapping 5 & 9, and 26 by swapping 6 & 8
[CODE]
9532
8124
7610[/CODE]

[QUOTE=WraithX;493546]I really like this puzzle. I think the flat x,y grid will be able to get up to around [c]n = 2*x*y[/c] and the torus x,y grid might be able to get up to around [c]n = 4*x*y[/c] These are just wild guesses. Hopefully someone can come up with better bounds. I'm going to try running a python program to see if I can come up with some other/better solutions.[/QUOTE]Standard word searches are not based around the torus.
[QUOTE=axn;493549]You can get to 25 by just swapping 5 & 9, and 26 by swapping 6 & 8
[CODE]
9532
8124
7610[/CODE][/QUOTE]
Nice innovations.

Someone had posted on FB, "like and share if you can find XXX". My thought, I wonder how big of rectangle one would need to get all of the numbers.

So to get to 30, would a 5 x 3 work? Or would a 4 x 4 be required?
Once we get to 5 x 5 the number of potential connections goes way up. And passing through the 50's will see a gain in XY, YX pairing (ie. 45 and 54 are the same, just in a different direction, same for 91 and 19).

[CODE]
1....
41221
330..[/CODE]
5x3 = 34 (. to be replace by 4-9 in any order)

[CODE]
3043
.12.
.21.
3..3[/CODE]
4x4 = 43 (. to be replaced by 3,5-9 in any order)

I am assuming both of these can be improved -- these were found quickly by manual search.

I like what you did there in that last one. It pulls ahead of WraithX's prediction of [c]n = 2*x*y[/c] by having [c]43 > 2*4*4[/c]. So maybe 6 x 6 might be the break through that gets all the way to 100.

Here is a 5x3 rectangle with score 36:
[CODE]
9 0 3 6 8
1 2 3 1 2
7 4 1 5 2
[/CODE]


Genetic algorithms might perform pretty good on this kind of problem.

A 5x5 square derived from axn's 4x4 with score 76:
[CODE]
. 0 4 3 6
5 1 2 4 6
6 2 1 9 5
0 7 8 3 5
3 5 4 6 3
[/CODE]The upper-left entry can be filled with any value.

And a 6x6 with score 99:
[CODE]
9 9 2 8 5 1
6 7 3 4 0 6
2 6 6 3 4 7
2 8 5 9 1 7
1 2 8 0 5 5
1 0 7 5 4 1
[/CODE]

I found a 6x6 with score 100, derived from the 5x5 stated before:
[CODE]
. 7 0 6 . .
. 3 0 4 3 6
9 5 1 2 4 6
9 6 2 1 9 5
0 7 7 8 3 5
8 8 5 4 6 3

[/CODE]


The dots can be filled with any number, hence there is still a lot of freedom. On the other hand will it be difficult to get much better because then we need many "10x" strings.

Great work!
Did you do that all by hand? I noticed that the inner square of 1's and 2's carried over. At some point rather that keeping them together, it might be that we don't care about them being so close as we have 3 or 4 of them.

The initial thread title was a play on magic squares. But, there has to be a better title for these. Sentences that have all the letters are pangrams or holoalphabetic sentences. Holonumeric squares might be a good sterile name. Compact number squares. Convonumbero squares. Getting all Latin Omnibus numeris quadratum.

Thanks.
I wrote a little program that random-tests rectangles that contain each of "0123456789" at least once. That gave me the 5x3 solution with score 36 and the 6x6 with score 99.


The better 5x5 and 6x6 results were derived by hand. axn's 4x4 is quite ingenious I'ld say. My random test achieved no more than score 36 after >10million 4x4squares.