Write a sequence of moves for n=4 What kind of path is the resulting path? Expla

Question

Write a sequence of moves for n=4

What kind of path is the resulting path? Explain why the solution gives this kind of path.

Let us suppose that we are trying to solve a Towers of Hanoi puzzle that has n disks and 3 peas. To keep track of our moves, label the top disk 0, the next disk 1 and so forth, so that the largest disk is labeled n - 1. For example, suppose n=3. At the beginning of the puzzle, disk 0 will be on top of disk 1, which rests on top of disk 2, all of which are stacked on the left-most peg. As you solve the puzzle, record the number of the disk that you move. With n=3, first move disk 0, then disk 1, disk 0 (onto disk 1), disk 2, disk 0 (onto the empty peg), disk 1 and finally disk 0. In short, the disks moved are 0102010. Both exercises in the following topic notes, Hanoi's cube and Hanoi's Graph, involve the relationship between the puzzle's solution and paths in a graph but with different representations. write a sequence of moves for n=4? On the cube below, note that there are three directions in which we can travel: left/right front back, up/down. Also notice that if we start at any vertex, we can travel in each of the three listed directions. Start at the vertex v. Now, read your solution to the 3-disk puzzle and create a path using the following rules. Each time you encounter a 0. move left or right. Each time you encounter a 1, move forwards or backwards. Each time you encounter a 2, (you guessed it) move up or down. What kind of path is the resulting path? Explain in your own words why the solution to this problem gives this kind of path.

Explanation / Answer

<<1>>
Sequence of moves for N=4 :
---------------------------------------
For better understanding let A = tower 0, B = tower 1, C = tower 2. Following sequence follows :

(A , B) => (A , C) => (B , C) => (A , B) => (C , A) => (C , B) => (A , B) => (A , C) => (B , C) => (B , A) => (C , A) => (B ,C) => (A , B) => (A , C) => (B , C)
-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
<<2>>
The path will be a "Hamiltonian Path" !

Explanation : Considering each vertex of Cube as nodes and edges as edges we can imagine the cube as a "Undirected Graph".
Now, Hamiltonian Path in an undirected graph is a path that visits each vertex exactly once.
According to given set of rules of moving in your instructions, each vertex will be visited exactly once.
Hence the path will be hamiltonian path.

Note : Feel free to ask in case of you face any doubts or need further explanation :)

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.