Mikero's brainwrenching grid puzzle
This page is dedicated to the puzzle Michael Goldshteyn aka Mikero has posted to
the newsgroup rec.puzzles in June 2000.
Mike's page with the original
description of the puzzle is gone, here's a brief summary from memory.
You have a grid of cities connected by bridges, like in the following image:
The cities are labeled with letters A to P. The bridges have numbers. The number
associated with a bridge represents the amount of money you have to pay to cross
that bridge.
Your task is to find the cheapest way to visit every city. You can start in a
city of your choice. You can visit the same city more than once. You may use
any bridge any number of times in any direction, but you have to pay the cost
of the bridge every time you use it. You don't have to return to your starting
city, the tour ends as soon as you enter the last city you haven't visited before.
In the example, if your route is ABCDHGFEIJKLPONM, the total cost
is 3+7+7+2+8+4+6+6+9+5+8+1+1+1+9 = 77. A cheaper route is MNOPLHDCGKJFBAEI
with cost 9+1+1+1+1+2+7+4+5+5+7+6+3+5+6 = 63. The cheapest possible route in the
example has cost 59.
Read the related newsgroup threads for the latest developments:
I wrote a description of my first approach at
solving the puzzle using a computer program.
You can download my program as source code (ANSI C++)
or executable (Win32). Suitable input files for the
grids posted by Mike: 4x4, 5x5,
6x6 and 7x7.
Even though Geoff Bailey
showed
that my initial assumption (that the perfect solution could not contain loops)
was wrong, my approach is still usable to find low scores fast.
An explanation, why loops are possible, can be found
here.
I'm now working on a different approach, which can deal with loops. I'm still
convinced that using trees of bridges as the basis (instead of paths from
town to town) might reveal valuable insights. None of the path algorithms I've
seen so far can prune the possibilities drastically enough to make a path search
feasible for large grids.
If you have ideas or comments, please join the newsgroup discussion. If you
have questions or suggestions concerning anything I wrote, you can send email
to Daniel Hartmeier.
