I was contemplating another generalization, this one to mxn grids. 2xn is interesting, because the optimal paths on square grids always seem to start by sweeping out a 2xn rectangle first. On Sun, Apr 14, 2013 at 8:16 PM, Dan Asimov <dasimov@earthlink.net> wrote:
As is my custom, I'm curious what happens if the NxN square is replaced by an NxN square torus. This has more symmetries than the square, so probably won't be any harder.
Also of interest might be the same question asked of hexagon tori, where the nth one is made of what Wikipedia calls a "centered hexagonal number" (or just a "hex number") of hexagons, where that's made of
H(n) = 1 + T(n-1)
hexagons, where T(k) = k(k+1)/2 is the kth triangular number, n= 0,1,2,....
(Of course for the hexagonal torus (or, OK, grid), the analogue of a king's move would just be a move to any cell sharing an edge.)
--Dan
On 2013-04-14, at 4:42 PM, Allan Wechsler wrote:
Haha, "helpy" Gmail hyperlinked the three numbers 156 1368 2280, because it looked just enough like a phone number.
My intuition has crystallized just a little bit. If you have a path that is not "contiguous", that means there is a pair of cells c[n], c[n+1] that are not kingwise adjacent. Sometime after c[n+1] there occurs the first cell c[n+k] that *is* adjacent to c[n]. If you alter the cell sequence by moving c[n+k] up to follow c[n] immediately, shoving everything else down one space to make room -- then how can that hurt? It seems ("seems" -- this is not a proof!) that the last element can't decrease. I just now got a little bit less confident, but maybe somebody else can either push this through or find a counterexample.
On Sun, Apr 14, 2013 at 7:29 PM, Fred W. Helenius <fredh@ix.netcom.com wrote:
On 4/14/2013 5:43 PM, Allan Wechsler wrote:
Conjecture: the highest achievable outcome can be achieved by a king's-move-connected path through the grid. This seems very obvious to me intuitively, but I'm too scatterbrained to prove it at the moment. If it's true, it should speed up searches considerably.
It's plausible--if only because the 3x3 and 4x4 solutions work that way--but I don't see a proof. But it would be a great thing to know because assuming the correctness of Allan's conjecture reduces the computation for 5x5 to under 10 minutes. The conjectural champion value is then 297136, from this grid:
1 1 53181 106357 143018
2 4 16515 36661 297136
6 12 9046 7452 3648
18 54 156 1368 2280
18 90 300 456 456
Even with this improvement, 6x6 still looks difficult; possibly on the order of CPU-weeks.
As ever, independent confirmation would be welcome.
-- Fred W. Helenius fredh@ix.netcom.com
______________________________**_________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/**cgi-bin/mailman/listinfo/math-**fun<; http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun>
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun