Solving Tower of Hanoi coding challenge

By Ahmed Ali

4 min read

Authors

In the previous article on the Tower of Hanoi coding challenge, we discussed the Tower of Hanoi as a mathematical problem that we need to solve using code. We were introduced to the Tower of Hanoi puzzle and the rules to solve it. If you haven't read the previous article yet, I suggest you do so.
Coding challenge Tower of Hanoi.

In this article, we are going to explore together how to solve this coding challenge.

Algorithm for Tower of Hanoi

One general way to solve the Tower of Hanoi is a recursive algorithm. First, we need to decide on two pegs as the source and destination, and the spare peg would be temporary.

Here are the steps to solve the Tower of Hanoi puzzle:

  • Move the top n-1 disks from the source peg to the helper peg.
  • Afterward, move the nth disk from the source peg to the destination peg.
  • Finally, move the rest n-1 disks from the helper peg to the destination peg.

How to solve the Tower of Hanoi Puzzle

Let’s illustrate the algorithm for three disks and consider peg A as the source, peg B as the helper, and peg C as the destination

Step 1) Initially, all the disks will be stacked on peg A.

At this stage:

Source = Peg A Destination = Peg C Helper = Peg B

Now, we need to move the top n-1 disks from the source to the helper.

Note: Though we can only move one disk at a time, it breaks our problem from a 3-disk problem to a 2-disk problem, which is a recursive call.

Step 2) As we call a recursive call from peg A and the destination is peg B, we will use peg C as a helper.

Notice that we are at stage one again for the same tower of Hanoi problem for two disks.

Now we need to move n-1 or one disk from source to helper, moving the smallest disk from peg A to peg C.

At this stage:

Source = peg A Destination = peg B Helper = peg C

Step 3) Then, according to our algorithm, the nth or 2nd disk needs should be transferred into the destination or peg B.

At this stage:

Source = peg A Destination = peg B Helper = peg C

Step 4) Now, we will move the n-1 disks or disk one from helper or peg C to the destination or peg B according to the third stage of our algorithm.

At this stage:

Source = peg A Destination = peg B Helper = peg C

Step 5) After completing the recursive call, we will return to our previous setting when the first stage of the algorithm.

Step 6) Now, in the second stage, we will move our source to our destination, which is moving disk 3 to peg C from peg A.

At this stage:

Source = peg A Destination = peg C Helper = peg B

Step 7) Now we can see that

d is to move the remaining disks from helper (peg B) to destination (peg C). We will use the initial source or peg A as a helper in this case.

Step 8) As we can’t move two disks simultaneously, we will call a recursive call for disk 1. According to the last step and our algorithm, a destination in this step is peg A.

At this stage:

Source = peg B Destination = peg A Helper = peg C

Step 9) Our recursive call is completed now. Then we move disk 2 from its source to its destination.

At this stage:

Source = peg B Destination = peg C Helper = peg A

Step 10) Then we move our remaining n-1 or disk 1 from helper to destination.

We will apply this approach as below to solve the puzzle:

  • Create a function towerOfHanoi where pass the N (current number of disk), startPeg, endPeg, tempPeg.
  • Make a function call for N – 1 th disk.
  • Then print the current the disk along with startPeg and endPeg
  • Again make a function call for N – 1 th disk.

Below is the implementation of the above approach using C#.

char startPeg = 'A'; // start tower in output
char tempPeg = 'B'; // temporary tower in output
char endPeg = 'C'; // end tower in output
int totalDisks = 3; // number of disks

MoveDisk(totalDisks, startPeg, endPeg, tempPeg);

static void MoveDisk(int n, char startPeg, char endPeg, char tempPeg)
{
    if (n > 0)
    {
        MoveDisk(n - 1, startPeg, tempPeg, endPeg);
        Console.WriteLine("Move disk " + n + " from peg " + startPeg + " to peg " + endPeg);
        MoveDisk(n - 1, tempPeg, endPeg, startPeg);
    }
}

Output

Move disk 1 from peg A to peg C
Move disk 2 from peg A to peg B
Move disk 1 from peg C to peg B
Move disk 3 from peg A to peg C
Move disk 1 from peg B to peg A
Move disk 2 from peg B to peg C
Move disk 1 from peg A to peg C

Upcoming events

  • Coven of Wisdom - Herentals - Winter `24 edition

    Worstelen jij en je team met automated testing en performance? Kom naar onze meetup waar ervaren sprekers hun inzichten en ervaringen delen over het bouwen van robuuste en efficiënte applicaties. Schrijf je in voor een avond vol kennis, heerlijk eten en een mix van creativiteit en technologie! 🚀 18:00 – 🚪 Deuren open 18:15 – 🍕 Food & drinks 19:00 – 📢 Talk 1 20:00 – 🍹 Kleine pauze 20:15 – 📢 Talk 2 21:00 – 🙋‍♀️ Drinks 22:00 – 🍻 Tot de volgende keer? Tijdens deze meetup gaan we dieper in op automated testing en performance. Onze sprekers delen heel wat praktische inzichten en ervaringen. Ze vertellen je hoe je effectieve geautomatiseerde tests kunt schrijven en onderhouden, en hoe je de prestaties van je applicatie kunt optimaliseren. Houd onze updates in de gaten voor meer informatie over de sprekers en hun specifieke onderwerpen. Over iO Wij zijn iO: een groeiend team van experts die end-to-end-diensten aanbieden voor communicatie en digitale transformatie. We denken groot en werken lokaal. Aan strategie, creatie, content, marketing en technologie. In nauwe samenwerking met onze klanten om hun merken te versterken, hun digitale systemen te verbeteren en hun toekomstbestendige groei veilig te stellen. We helpen klanten niet alleen hun zakelijke doelen te bereiken. Samen verkennen en benutten we de eindeloze mogelijkheden die markten in constante verandering bieden. De springplank voor die visie is talent. Onze campus is onze broedplaats voor innovatie, die een omgeving creëert die talent de ruimte en stimulans geeft die het nodig heeft om te ontkiemen, te ontwikkelen en te floreren. Want werken aan de infinite opportunities van morgen, dat doen we vandaag.

    | Coven of Wisdom Herentals

    Go to page for Coven of Wisdom - Herentals - Winter `24 edition
  • Mastering Event-Driven Design

    PLEASE RSVP SO THAT WE KNOW HOW MUCH FOOD WE WILL NEED Are you and your team struggling with event-driven microservices? Join us for a meetup with Mehmet Akif Tütüncü, a senior software engineer, who has given multiple great talks so far and Allard Buijze founder of CTO and founder of AxonIQ, who built the fundaments of the Axon Framework. RSVP for an evening of learning, delicious food, and the fusion of creativity and tech! 🚀 18:00 – 🚪 Doors open to the public 18:15 – 🍕 Let’s eat 19:00 – 📢 Getting Your Axe On Event Sourcing with Axon Framework 20:00 – 🍹 Small break 20:15 – 📢 Event-Driven Microservices - Beyond the Fairy Tale 21:00 – 🙋‍♀️ drinks 22:00 – 🍻 See you next time? Details: Getting Your Axe On - Event Sourcing with Axon Framework In this presentation, we will explore the basics of event-driven architecture using Axon Framework. We'll start by explaining key concepts such as Event Sourcing and Command Query Responsibility Segregation (CQRS), and how they can improve the scalability and maintainability of modern applications. You will learn what Axon Framework is, how it simplifies implementing these patterns, and see hands-on examples of setting up a project with Axon Framework and Spring Boot. Whether you are new to these concepts or looking to understand them more, this session will provide practical insights and tools to help you build resilient and efficient applications. Event-Driven Microservices - Beyond the Fairy Tale Our applications need to be faster, better, bigger, smarter, and more enjoyable to meet our demanding end-users needs. In recent years, the way we build, run, and operate our software has changed significantly. We use scalable platforms to deploy and manage our applications. Instead of big monolithic deployment applications, we now deploy small, functionally consistent components as microservices. Problem. Solved. Right? Unfortunately, for most of us, microservices, and especially their event-driven variants, do not deliver on the beautiful, fairy-tale-like promises that surround them.In this session, Allard will share a different take on microservices. We will see that not much has changed in how we build software, which is why so many “microservices projects” fail nowadays. What lessons can we learn from concepts like DDD, CQRS, and Event Sourcing to help manage the complexity of our systems? He will also show how message-driven communication allows us to focus on finding the boundaries of functionally cohesive components, which we can evolve into microservices should the need arise.

    | Coven of Wisdom - Utrecht

    Go to page for Mastering Event-Driven Design
  • The Leadership Meetup

    PLEASE RSVP SO THAT WE KNOW HOW MUCH FOOD WE WILL NEED What distinguishes a software developer from a software team lead? As a team leader, you are responsible for people, their performance, and motivation. Your output is the output of your team. Whether you are a front-end or back-end developer, or any other discipline that wants to grow into the role of a tech lead, RSVP for an evening of learning, delicious food, and the fusion of leadership and tech! 🚀 18:00 – 🚪 Doors open to the public 18:15 – 🍕 Let’s eat 19:00 – 📢 First round of Talks 19:45 – 🍹 Small break 20:00 – 📢 Second round of Talks 20:45 – 🙋‍♀️ drinks 21:00 – 🍻 See you next time? First Round of Talks: Pixel Perfect and Perfectly Insane: About That Time My Brain Just Switched Off Remy Parzinski, Design System Lead at Logius Learn from Remy how you can care for yourself because we all need to. Second Round of Talks: Becoming a LeadDev at your client; How to Fail at Large (or How to Do Slightly Better) Arno Koehler Engineering Manager @ iO What are the things that will help you become a lead engineer? Building Team Culture (Tales of trust and positivity) Michel Blankenstein Engineering Manager @ iO & Head of Technology @ Zorggenoot How do you create a culture at your company or team? RSVP now to secure your spot, and let's explore the fascinating world of design systems together!

    | Coven of Wisdom - Amsterdam

    Go to page for The Leadership Meetup

Share