PDA

View Full Version : The Grid Challenge: Puzzle #1



OmniscientLogic
11-09-2013, 11:44 AM
I have revisited an idea I had for a game that I think others will find enjoyable. Here are the rules for this game:

1. You are presented with a grid of cities. Connecting the cities are bridges that have a certain toll or cost to using them ranging from 1 to 9.
2. The object of the game is to visit every city for the lowest total cost. This total cost is the sum of the costs of all of the bridges visited on your trip.
3. Your route can start at any city and finish at any city, as long as all cities get visited at least once. In other words, it has to in one way or another connect all cities.
4. Every time you move from city to city, you traverse a bridge. Each bridge has a toll associated with it and this toll is added to the total cost when the bridge is used to travel from one city to another.
5. This is very important: Cities can be visited more than once and bridges can be traversed more than once. However, each time a bridge is traversed, its toll must be paid and the goal of the game is to visit all cities with as low a total cost (i.e., sum of all tolls) as possible.
6. Since it is in your best interest to keep the total cost as low as possible, traversing bridges more than once (and visiting cities more than once) is generally a bad idea. However, there are times when traversing the same bridge more than once can lead to a smaller total cost.

The above may sound a little bit confusing, so here is an example problem:

4078

In the above 3x3 grid, uppercase letters (A-I) represent the cities. Between each city and its adjoining cities you see bridges with the costs associated with traversing them.

After several attempts, an astute reader may conclude that the following is the optimal path:

Path: CFIHEBADG

The format of the path above is that each letter represents a particular city visited in succession. A visitor would start at city C, visiting F, then I, then H, etc..., until finally ending up at city G, having visited all cities at least (and in this case exactly) once.

The total cost of the path above is 40. This is probably the best cost for a solution that includes each city only once. In other words, one that doesn't involve any repeat visits to cities.

With practice, someone would discover the even better solution:

Path: GEHECFIFBAD

This one, despite visiting cities E and F twice comes to a total cost of 37. This is three less than our former (shorter) solution. Therefore, this solution is the winner so far on this particular problem.

Having solved this problem, it is time for something more challenging and I want this challenge to be yours.

This is a more complex 4x4 city construction. We will call this:

Puzzle #1


4082

Click on the image to see it full size.

Here is an ASCII representation of the puzzle that may be easier to copy/paste and print:

A-2-B-8-C-6-D
|\ /|\ /|\ /|
7 9 4 5 6 7 9
|/ \|/ \|/ \|
E-8-F-2-G-5-H
|\ /|\ /|\ /|
1 8 9 8 9 5 8
|/ \|/ \|/ \|
I-5-J-3-K-3-L
|\ /|\ /|\ /|
3 7 8 4 4 1 6
|/ \|/ \|/ \|
M-2-N-8-O-9-P

At this level, finding the lowest cost can be a little challenging, but many techniques exist to make this endeavor more optimal.

Try to find the lowest cost route that solves Puzzle #1 and post it as a reply to this post.

Good luck!

nijineko
11-11-2013, 01:28 PM
i imagine no mid-bridge turns are permitted? only straight line travel?