Trusted answers to developer questions
Trusted Answers to Developer Questions

Related Tags

python

How to solve the tower of Hanoi problem

Ibrahim Khan

In this shot, we’ll look at the tower of Hanoi problem and how to solve the problem in Python.

Introduction

Let’s start by discussing what the tower of Hanoi problem is. It is a mathematical problem that involves three vertical rods and n circular discs. In their original state, the discs are stacked in order on the first rod, with the largest at the bottom of the pile and the smallest at the top. The goal of the problem is to move the entire stack to the final rod with the order remaining constant. However, the solution has to abide by some constraints:

  1. We can move only one disc at a time.
  2. Only the disc at the top of the stack can be moved to the top of another stack.
  3. We can only place a smaller disc on a larger disc.

Let’s take a look at how three discs would be moved from the first to the last rod in the slides below.

1 of 8

Code

We can find the code of this given problem below:

def TowerOfHanoi(n, start_rod, end_rod, transition_rod):
	## base case for only one disc remaining
	if n==1:
		print "Move disk 1 from rod",start_rod,"to rod",end_rod
		return
	## Recursive call for to move the top disc in a stack of 2
	TowerOfHanoi(n-1, start_rod, transition_rod, end_rod)
	 
	print "Move disk",n,"from rod",start_rod,"to rod",end_rod
	## Recursive call for to move the top disc in a stack of 3
	TowerOfHanoi(n-1, transition_rod, end_rod, start_rod)
		

n = 3
TowerOfHanoi(n,'A','C','B')

RELATED TAGS

python

CONTRIBUTOR

Ibrahim Khan
Copyright ©2022 Educative, Inc. All rights reserved
RELATED COURSES

View all Courses

Keep Exploring