Scribd
Upload
238 views2 pages

2 - Tower of Hanoi

The document describes the Tower of Hanoi puzzle, which involves moving disks of different sizes between three pegs according to rules. It explains that the puzzle has a recursive solution involving moving all but the largest disk, then the largest disk, then the remaining disks. The number of moves required increases exponentially with the number of disks.

Uploaded by

Aneesh Shinde
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
238 views2 pages

2 - Tower of Hanoi

The document describes the Tower of Hanoi puzzle, which involves moving disks of different sizes between three pegs according to rules. It explains that the puzzle has a recursive solution involving moving all but the largest disk, then the largest disk, then the remaining disks. The number of moves required increases exponentially with the number of disks.

Uploaded by

Aneesh Shinde
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 2

Practical 2 AI

Practical 2: Tower of Hanoi


Aim: Write a program to solve tower of Hanoi problem..

Theory:

The Tower of Hanoi is a classic mathematical puzzle or problem that involves moving a sequence of
disks from one peg to another peg, subject to certain constraints. The problem is often used to
illustrate principles of recursion, algorithm design, and problem-solving strategies. The Tower of
Hanoi puzzle is named after the city of Hanoi in Vietnam.

The problem is usually stated as follows:

Problem Statement:
You have three pegs (usually labeled A, B, and C) and a number of disks of different sizes which can
slide onto any peg. The puzzle starts with the disks neatly stacked in increasing size on one peg, with
the largest at the bottom and the smallest on top. The goal is to move the entire stack to another
peg, subject to the following rules:

1. Only one disk can be moved at a time.


2. Each move consists of taking the top disk from one of the stacks and placing it on top of another
stack or on an empty peg.
3. No disk may be placed on top of a smaller disk.

The challenge is to find a sequence of moves that transfers the entire stack of disks from the source
peg to the target peg, using the third peg as an auxiliary peg.

The Tower of Hanoi problem is interesting because it requires a recursive approach to solve
optimally. The recursive solution is based on the observation that to move N disks from the source
peg to the target peg:

1. Move N-1 disks from the source peg to the auxiliary peg.
2. Move the largest disk from the source peg to the target peg.
3. Move the N-1 disks from the auxiliary peg to the target peg.

This recursive pattern continues until the base case of moving a single disk is reached.

The number of moves required to solve the Tower of Hanoi problem with N disks is \(2^N - 1\),
making it a good example for demonstrating the power of recursion and exponential growth in
algorithmic complexity.

Prof. Ismail H. Popatia Page 1


Practical 2 AI

The problem has practical applications in algorithm analysis, teaching recursion, and understanding
problem-solving techniques.

Prolog Code: (Statements and Rules)

Output:

For Video demonstration


of the given practical
Scan the QR-code or click
on the link below

https://youtu.be/2ilWvjCBaZ0

Prof. Ismail H. Popatia Page 2

You might also like