Ready? :P

"Knot theory". Don't have time to pursue it, but there's just got to be some way to represent the board in such a way that:

1) Trivial movements which get you nearer your goal are "normal", cost = 1.

2) Turning back upon your own path is a "knot", cost of two, sometimes three. Basically following the theory that any given problem is one of three cases: 0 knots, odd number of knots, even number of knots. Solve the knots (which for sufficiently long distances (> ~4), the actual position of the "knot" move is variable), and the rest is trivial.

-------------------------\n|   |   |   |   |   |   |\n-------------------------\n|   | 0 | 3 |   | 3 |   |\n-------------------------\n|   |   |   | 1 |   |   |\n-------------------------\n|   | 2 |   | 4 |   | 2 |\n-------------------------\n|   |   |   |   |   |   |\n-------------------------

Initial Cost = (distance between pt 0 and pt 4, no fair counting diagonal moves) / 3 = (4/3) = 1

Added Cost =
+1 for "undershooting" on move 0->1
+1 for "overshooting" (increasing the distance to target) on move 1->2
+1 for overshooting on move 2->3

The Added Cost occurs because we are seeking a penultimate position whose distance differential to the target is 3; i.e. where f(x, y) = ((x'-x) + (y'-y)) mod 3 = 0. Because the "distance" from 0 to 4 is 4 squares, 4 mod 3 = 1. Does every point where f(x, y) = 1 result in 3 "extra" moves? Does every point where f(x, y) = 2 result in 2 "extra" moves? I don't have the motivation to be rigorous here, just stating my research direction.

Note that for square boards, multiple equal-cost options are available at almost all decision points; this also implies that at least one of those options will be available even when we are near a board edge, assuming our board is at least 4x4. Gotta prove that one.

So, a brute-force comparison process could determine initial cost mathematically, saving a good chunk of time, and then solve the "endgame" either mathematically as well, or with a lookup table, if I'm wrong about f(x, y) patterns.

Does your algorithm need to show the path? or just calculate cost?

I was developing this for Knight's Path only, not Tour/Circuit. And I wrote part of that in a misleading way...my hope would be that it would *not* be brute-force, but straightforward division.