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 A-B-C-D-H-G-F-E-I-J-K-L-P-O-N-M, the total cost is 3+7+7+2+8+4+6+6+9+5+8+1+1+1+9 = 77. A cheaper route is M-N-O-P-L-H-D-C-G-K-J-F-B-A-E-I 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:

• Mikero's brainwrenching grid puzzle
• Mikero's revenge (brainwrenching grid puzzle)
• Mikero's brainwrenching grid puzzle #3 (June 25, 2000)
• Mikero's brainwrenching grid puzzle #4 (June 29, 2000)

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.