Recent Chat Activity (Main Lobby)
Join Chat

Loading Chat Log...

Prefer not to see ads? Become a Community Supporter.
Results 1 to 1 of 1

Thread: The Grid Challenge: Puzzle #1

  1. #1
    Join Date
    Nov 2013
    Posts
    2
    Downloads
    0
    Uploads
    0

    The Grid Challenge: Puzzle #1

    Prefer not to see ads?
    Become a Community Supporter.
    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.
    3. 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.
    4. 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.
    5. 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:

    Click image for larger version. 

Name:	grid_3x3.png 
Views:	28 
Size:	24.9 KB 
ID:	4080

    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

    Click image for larger version. 

Name:	grid_4x4.png 
Views:	19 
Size:	48.2 KB 
ID:	4081

    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!
    Last edited by OmniscientLogic; 11-09-2013 at 04:38 PM.

Bookmarks

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •