Minimum Pac-Man Distance
Note: the given solution is incorrect, sorry for the inconvenience! Hopefully the solution will be corrected soon.
If the ghosts weren’t in the way, what would be the minimum distance required for Pac-Man to eat all the Pac-dots (and Power Pellets) in the maze?
Assume that each consecutive Pac-dot is one unit apart and that Pac-Man travels one unit to reach the first Pac-dot.
The answer is 294.
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
1 solution
Here is one route with a distance of 2 9 4 :
(Thanks to @Jon Haussmann for providing a better path for the top section.)
Ideally, Pac-man would eat one pellet per one unit move, but given the layout of the board, this is not possible. One strategy is to minimize the amount of "wasted" unit moves in which Pac-man does not eat any pellets. Each intersection point with an odd number of paths coming out of it will have some wasted unit moves, and to minimize the waste we want to overlap the smallest path out of it. For example, in the diagram below, the red point has three paths out of it, each going to the three different green intersection points. Two paths are 3 units long, and one is 9 units long. We would want to avoid overlapping the 9 unit path because it is the biggest, and choose to overlap one of the other two 3 unit paths to minimize wasted unit moves.
There are still a lot of possibilities to consider, but this strategy helps. I would imagine a computer would be necessary to prove a minimum path, but it's still a fun exercise to think about.