by **saulgoode** » Thu Oct 10, 2013 4:22 am

The stated problem can be simplified to the task of finding the shortest path from the white knight's starting square to the black knight's starting square. The actual place where the knights meet each other would lie midway along this path.

Unlike the Knight's Tour problem, there are an infinite number of routes that your knights could conceivably take (since there's no restriction against revisiting a square). The situation is not hopeless, however, because if given an upper bound to the number of moves that can be made, only a finite number of routes are possible. The absolute worst case for an upper bound would be 63 moves, the number of moves in a knight's tour solution.

The problem then becomes attempting each possible path until the upper bound is exceeded. If a solution is found before exceeding your upper bound, the number of moves of that solution becomes the new upper bound, and you continue your search. When you reach the point where no more routes can be found with fewer moves than your upper bound, you have your solution (if the number of moves equals the upper bound then you have an additional solution).

This approach leads to an untenable number of iterations when the upper bound is too large, but it would seem manageable if the solution can be found in a dozen or so moves. Since the number of iterations grows exponentially, it would be advisable to start with an upper bound of one and if no solution is found increase it by one, repeating until a solution is found. Hopefully a solution will arise before the upper bound reaches the point where it requires days to iterate through all the possible moves. (It would seem to me that even the worst case positioning of the starting and ending squares shouldn't demand more than a dozen moves, though I haven't done any analysis on this. EDIT: after some investigation, I've determined that a knight can reach any square on the board in six or fewer moves.)

Last edited by

saulgoode on Sun Oct 13, 2013 7:53 pm, edited 1 time in total.