[benzedrine.ch logo]
Contents
Home
Daniel Hartmeier
Packet Filter
pfstat
Mailing list
Annoying spammers
Prioritizing ACKs
Transparent squid
Proxy ICB/IRC
milter-regex
milter-spamd
milter-checkrcpt
login_yubikey
Dorabella
Tron
Planet Wars
Hexiom solver
3D-ODRPP
Polygon partition
Mikero's grid puzzle
Dark Star
Misc
Statistics


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:

mikero

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:

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.

Last updated on Tue Jun 9 20:28:27 2015 by daniel@benzedrine.ch.