The Application of Hanoi Towers Game in Logistics Management

1.1. Pile Problems Applications in Logistics Management

Some examples are mentioned in (Hempel and Schmiedel, 2006): imagine a port where there are several containers and is necessary to load or to unload loading from the containerships, or suppose large concrete parts for a modern bridge or construction of buildings, or the shunt of trains in a marshaling yard, or patient plays. A container pre-marshaling problem is reported in (Shan-Huen & Tsan-Hwan, 2012) which purpose is finding a set of container movements to reach a final container arrangement by satisfying certain restrictions. Lu & Dillon (1995) discuss a parallelism implementation of Towers of Hanoi on which is permitted concurrent moves of disks in a single step. These authors analyzed three versions of parallelism considering two factors: the order of moves of disks and the resource utilization of pegs. They present a common technique for getting the non-recursive implementation by considering minimum steps. All of these problems can be modeled by applying basic principles of the Towers of Hanoi.

1.2. Mathematical Modeling

Puzzles are connected with graphs, it means can be modeled by using graphs, vertices of the graph represent configuration and graph edges define possible moves of the puzzle (Cull, Merril and Van, 2013). According (Hempel & Schmiedel, 2006) to describe pile problems more precisely is highly recommended using graph theory. For these authors:

For a given directed graph G = (V, A) and its vertices v ϵ V can be used the following notations: N_G+(v) is the set of all successors of v, N_G-(V) is the set of all predecessors of v. d_G+(v) represents numbers of outgoing arcs of v and d_G-(v) numbers of incoming arcs of v respectively. For G₁ = (V₁, A₁) and G₂ = (V₂, A₂) the union of G₁ and G2 is defined as G₁ U G₂:= (V₁ U V₂, A₁ U A₂). A cycle in a directed graph G = (V, A) is a closed path in G. The directed graph G = (V, A) is called a pile, if and only if G is finite and does not contain a loop or a cycle. The vertices of G represent the elements of the pile; the arcs of G represent the order in which the elements are piled up. A step is the move of an element of data structure to another place. This place can be in different pile or in an auxiliary place if it exists (Hempel & Schmiedel, 2006).

Figure 1 and Figure 2, show an example of typical pile problems, meanwhile graphs representing the starting Gs and final Gf are shown below (Hempfel and Schmiedel, 2006):

Figure 1.

Starting situation

Figure 2.

Required final situation

Note how arcs in Figure 3 and Figure 4 correspond to inverted graphs.

Figure 3.

Starting pile Gs

Figure 4.

Final pile Gf

Towers of Hanoi

Also called the Towers of Brahma or Towers of Lucas; is a mathematical game, puzzle or toy that is made of three pegs (poles) and a number of disks of different sizes (in its basic form consisting of three disks), which can be moved into any peg (Hofstadter, 1996). The game starts with the disks placed in ascending order of size in one peg, the smallest at the top, forming a cone or pyramid (see Figure 5).

Figure 5.

Towers of Hanoi Basic game (three pegs - three disks) source (Hofstadter, 1996)

The purpose of the game is moving the entire pile of disks from the origin peg to the destiny peg, by considering next simple rules (Scheinerman, 2000):

• Step 1: Sole one disk can be moved each turn.

• Step 2: A move consists of taking the upper disk from one of the stacks and placing it on top of another stack.

• Step 3: Is not allowed a disk be placed on top of a smaller disk.

According Mishra and Vishnoi (2015) with three single disks, the game can be solved in seven steps. The minimum moves required to solve a Tower of Hanoi puzzle is 2ⁿ - 1, where n represents number of disks, as can be seen, this is an exponential number that increases when n increases.