Hamiltonian’s Game (icosian)

Run LPL Code  ,  PDF Document

Problem

The Icosian game, also called the Hamiltonian game, is a mathematical game invented in 1857 by William Rowan Hamilton. The game’s object is finding a path along the edges of a dodecahedron such that every vertex is visited exactly once, and the ending point is the same as the starting point.

The vertices of the 3-dimensional dodecahedron can be projected to the 2-dimensional space, producing a graph (see Figure 4). The problem is reduced to finding a path visiting each vertex exactly once and returning to the starting vertex. A path such as this became known as a Hamilton circuit, though the task of finding a circuit that passes just once through every vertex of a shape seems to have arisen first in connection with Leonhard Euler’s study of the knight’s tour, two years before Hamilton introduced his game.

It seems that the commercialization of the game (see Figure 1), suggested by Hamilton’s friend John Graves, was a complete flop, probably because it is too easy, although finding a Hamilton circuit is an instance of one of the most famous and most investigated difficult problem, the Traveling Salesman Problem or just TSP.

---

---

We use this game to give a short introduction to a famous problem, the TSP. For doing this, we need to define a minimum of a vocabulary from graph theory. We use the concepts graph, complete graph, path, circuit, and tour. A graph, noted as G = (V,E) is defined by of a finite set V , the vertices or nodes, and a set of edges E ⊆ V × V . Graphically speaking, it can be represented by a “network” consisting of points (the vertices) and lines (edges) between these points. It is not relevant where the points are placed and whether the line are straight or curved. What alone counts is the “connectedness”. An example is given in Figure 2 The figure displays a graph G = (V,E) with

with the alternative notation (v₀,v₂) for edge e₀, for example. The graph is complete, if there is a direct link (edge) between each pair of vertices. A path in a graph is a sequence of < v₀,e₁,v₁,…,e_k,v_k > where each v_i ∈ V and e_i ∈ E, and for 1 ≤ i ≤ k the ends of e_i are v_i–1 and v_i, and all v_i–1 are distinct. The path is a circuit if v₀ = v_k. A tour is a circuit visiting all vertices of the graph. We also associate a length to each edge, and say the length of a tour is the sum of all its edge lengths.

In Figure 2 (on the right) the displayed path – marked by bold lines – is:

< v₀,e₀,v₂,e₃,v₁,e₈,v₅,e₆,v₃,e₅,v₄ >.

In Figure 3 < v₀,e₁,v₃,e₅,v₄,e₂,v₀ > is a circuit and on the right a tour is displayed.

---

---

---

---

Using these concepts, the Traveling Salesman Problem is the problem of finding a tour with the shortest tour-length in a complete graph. Note that a complete graph has many tours, in fact every permutation of vertices builds a tour.

---

---

Modeling Steps

First, we must translate the Icosian game into a traveling salesman problem. Figure 4 displays a graph of the Icosian game and the problem consists of finding a tour in this graph (if it exists). First, let the length of each edge in this graph be 0 (zero). Second, note that the graph of the Icosian game is not complete. To transform the problem to a TSP, we extend the graph to a complete graph by adding the missing edges and attach a length of 1 to each added edge. We now have a complete graph and finding a tour in the Icosian graph is the same as finding a shortest tour in the extended (complete) graph. If the complete graph has a shortest TSP tour of length 0 (zero), then there exists a tour for the Icosian game otherwise no tour exists.

Let’s build a mathematical model for the Icosian game. Let i,j ∈{1,…, 20} be the set of vertices.

1. Define a 0-1 matrix d_i,j with i ⁄= j as follows: d_i,j = 1 if (i,j) is an edge in the Icosian graph, else d_i,j = 0. (Note that d_i,j = d_j,i.)

2. We introduce a binary variable x_i,j (i ⁄= j) with the meaning: x_i,j = 1, if edge (i,j), in the direction i to j is in the tour, else (i,j) is not in the tour.

3. A necessary condition for a tour is that each vertex is “visited” exactly once. That is, for every vertex there is only exactly one incoming edge and one outgoing edge building the tour. We have:

   

4. Another necessary condition is the following. If the edge (i,j) in the direction i to j is in the tour, then (i,j) in direction j to i is not in the tour. Hence:

   We need to minimize the tour-length, hence:

   

model Icosian "Hamiltonian's Game"; 
    set i,j    "set of vertices"; 
        e{i,j} "set of edges"; 
    parameter d{i,j} "distances"; 
    binary variable x{i,j|i<>j}; 
    constraint 
      A{i}: sum{j} x = 1; 
      B{j}: sum{i} x = 1; 
      F{i,j|j>i}: x[i,j] + x[j,i] <= 1; 
      G: x[14,7] "This is enough to make a single tour"; 
    minimize obj: sum{i,j} d*x "minimize a round trip"; 
    if obj then Write('No tour length of zero exists' n'); 
    else Write('An Icosian tour exists, see graph.' n'); 
   end; 
    draw; 
    model data "The Icosian Game Instance"; 
      i:=[1..20]; 
      e{i,j}:= [(1,2) (2,3) (3,4) (4,5) (5,1) (1,6) (2,7) 
        (3,8) (4,9) (5,10) (6,14) (14,7) (7,15) (15,8) 
        (8,11) (11,9) (9,12) (12,10) (10,13) (13,6) 
        (14,19) (15,20) (11,16) (12,17) (13,18) (16,17) 
        (17,18) (18,19) (19,20) (20,16)]; 
      d{i,j}:= if(e[i,j] or e[j,i],0,1); 
    end 
    model draw; 
      parameter r:=6; PI:=4*Arctan(1); 
        X{i}:=if(i<6,1,i<11,0.75,i<16,0.5,0.3)*r* 
               Cos(3*PI/if(i<11,2,6)+(i-1)*2*PI/5)+r+.3; 
        Y{i}:=if(i<6,1,i<11,0.75,i<16,0.5,0.3)*r* 
               Sin(3*PI/if(i<11,2,6)+(i-1)*2*PI/5)+r+.3; 
      Draw.Scale(50,50); 
      for{i,j|e} do Draw.Line(X[i],Y[i],X[j],Y[j]);  end; 
      for{i,j|x} do Draw.Line(X[i],Y[i],X[j],Y[j],3,5);  end; 
      --for{i,j|x} do Draw.CLine(X[i],Y[i],X[j],Y[j],1,3,5);  end; 
      for{i} do Draw.Circle(i&'',X,Y,.35,1,0) ; end; 
    end; 
  end

Solution

A solution of this famous game is shown in Figure 5. Note that the solution is not unique, there exist several tours with length 20.

---

---

Further Comments

Note that the constraints given so far are necessary conditions for a TSP tour in a complete graph, but they are not sufficient as will be seen in another model (see next section lacing). For the Icosian game the given conditions are enough (if we are lucky).

Questions

1. Is the last constraint F really necessary? Does it not follow from the fact that at each vertex there must be exactly one incoming and one outgoing edge in the tour? Solve the problem without the last constraint to see what happens.

2. A solution to the previous question is given by Figure 7. Could we get rid of the annoying subtours if we just forbid the two tours 1 – 5 – 1 and 4 – 9 – 4 ?

3. Figure 6 displays a graph. Let all the edges-lengths be The Euclidean distances between the points, where a distance between vertex 46 and 47, for example, is defined to be 1. Find the shortest tour if it exists. Note that only edges of length ≤ 3.1 exist in the graph.

   ---

   

   Figure 6: A Graph containing 92 Vertices

   ---

Answers

1. Solving the problem without the last constraint results in a solution given by Figure 7. The Figure reveals an alarming fact: subtours can arise (containing any number ≥ 2 of edges). This means that our model for the TSP is not complete. We must also ban all subtours. We shall see in another context how to “remedy” the problem.

   ---

   

   Figure 7: Subtours in the Icosian Game

   ---

2. Unfortunately not, other subtours pop up confirming that we really need to ban all subtours.

3. We complete the missing edges and attach a large edge-length, say 99′999 in our case. We can try to use the model above to solve the TSP. Luckily, we get a single tour, so we solved the problem. The complete model for this problem can be downloaded from cross92 (next section).

References