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