Fuji 2dsan 2fChallengeTwo

Find an upper limit for the length of optimal solutions.

The lowest upper limit found so far is 20474. This was found on 15 Jun 2005 by DonKirkby. This is a lot longer than the longest solution found so far, so there's plenty of room to improve on challenge one or two.

One upper limit can be found by realizing that the same position of priests cannot be repeated in an optimal solution. If a position were repeated, then all the moves between the two occurrences could be removed to make a shorter solution, but an optimal solution is the shortest solution possible.

If a position cannot be repeated, then the longest optimal solution cannot be longer than one that contains every possible position. The number of possible positions can be calculated as follows:

Therefore, the longest optimal solution cannot be longer than 20474 moves. (Each move goes from one state to the next, so the number of moves is one less than the number of states.)

Related pages: Fuji-san [[Navigation(siblings)?]]