Stack Overflow
Stack Overflow

Questions tagged [towers-of-hanoi]

A simple puzzle involving moving discs between rods. Commonly used as a programming kata/exercise and frequently set as homework when introducing the concept of recursion.

The Tower of Hanoi or Towers of Hanoi , also called the Tower of Brahma or Towers of Brahma, is a mathematical game or puzzle. It consists of three rods, and a number of disks of different sizes which can slide onto any rod. The puzzle starts with the disks in a neat stack in ascending order of size on one rod, the smallest at the top, thus making a conical shape.

The objective of the puzzle is to move the entire stack to another rod, obeying the following rules:

  • Only one disk may be moved at a time.
  • Each move consists of taking the upper disk from one of the rods and sliding it onto another
  • rod, on top of the other disks that may already be present on that rod.
  • No disk may be placed on top of a smaller disk.
310 questions
68
votes
29 answers

Tower of Hanoi: Recursive Algorithm

Although I have no problem whatsoever understanding recursion, I can't seem to wrap my head around the recursive solution to the Tower of Hanoi problem. Here is the code from Wikipedia: procedure Hanoi(n: integer; source, dest, by: char); Begin …
titaniumdecoy
  • 18,900
  • 17
  • 96
  • 133
51
votes
3 answers

How does this work? Weird Towers of Hanoi Solution

I was lost on the internet when I discovered this unusual, iterative solution to the towers of Hanoi: for (int x = 1; x < (1 << nDisks); x++) { FromPole = (x & x-1) % 3; ToPole = ((x | x-1) + 1) % 3; moveDisk(FromPole,…
Andres
  • 5,012
  • 3
  • 24
  • 36
17
votes
4 answers

Code Golf: Towers of Hanoi

Rules The Towers of Hanoi is a puzzle, and if you are not very familiar with it, here is how it works: The play field consists of 3 rods, and x number of disks, each next one bigger than the previous one. The disks can be put on the rod, with these…
Aurel Bílý
  • 7,068
  • 1
  • 21
  • 34
11
votes
3 answers

Solving the Towers of Hanoi at compile-time

I am trying to solve the Towers of Hanoi at compile-time, but I have discovered a problem: template struct move_disc { // member access will print src and dst }; template struct hanoi { …
fredoverflow
  • 256,549
  • 94
  • 388
  • 662
10
votes
2 answers

How does recursive algorithm work for Towers of Hanoi?

This is code from a book I have explaining recursion. The problem is that I don't understand the steps taken by the program: var hanoi = function(disc,src,aux,dst) { if (disc > 0) { hanoi(disc - 1,src,dst,aux); …
dopatraman
  • 13,416
  • 29
  • 90
  • 154
8
votes
1 answer

Scaling an iterative, bitwise algorithm to solve the Towers of Hanoi using X discs and Y towers

I like the algorithm mentioned in this question: "How does this work? Weird Towers of Hanoi Solution" How does this work? Weird Towers of Hanoi Solution Is there any way to scale that non-recursive solution of Towers of Hanoi to use X disks and Y…
Robb
  • 81
  • 2
8
votes
5 answers

Towers of Hanoi solution better than O(2^n)?

Is there a solution for Towers of Hanoi whose running time is less than O(2n) where n is the number of disks to move? My solution takes O(2n) time. Also, the below solution is with recursion. Can we use Dynamic Programming with the concept of…
dharam
  • 7,882
  • 15
  • 65
  • 93
7
votes
4 answers

Solving Tower of Hanoi declaratively (Prolog)

My professor gave this as an example of Prolog. It is a program that solves the Tower of Hanoi puzzle, where you have to move a stack of disks to another peg by moving one disk after the other, without putting a bigger disk on top of a smaller disk.…
Bart Louwers
  • 873
  • 9
  • 28
7
votes
2 answers

How does this iterative Tower of Hanoi work? C

Possible Duplicate: How does this work? Weird Towers of Hanoi Solution While surfing Google, i found this interesting solution to Tower Of Hanoi which doesn't even use stack as data structure. Can anybody explain me in brief, what is it actually…
TCM
  • 16,780
  • 43
  • 156
  • 254
7
votes
1 answer

Ruby vs Java: Why world is going to end faster with Java?

I have tested recursive method execution speed with classic example of Honoi Tower. First in Java than JRuby and Ruby with different no. of plates: package com.example; public class Hanoi { public static void main(String[] args) { int…
Sergii Brytiuk
  • 345
  • 1
  • 12
6
votes
2 answers

Towers on Hanoi in Java using only int[ ][ ] (can it be done?)

This is not homework, I don't have money for school so I am teaching myself whilst working shifts at a tollbooth on the highway (long nights with few customers). I am trying to implement a simple version of the Hanoi Towers solver in Java. I am…
Robottinosino
  • 10,384
  • 17
  • 59
  • 97
5
votes
5 answers

Solution of "Tower of Hanoi" When all disks are not in A

As you know there are some ways to solve Tower of Hanoi, but they require all disks to be in one tower at the begining. Now I wanna know is there any way to solve it, where the disks are already spread out randomly among the towers at the start.
Moein Hosseini
  • 4,309
  • 15
  • 68
  • 106
5
votes
2 answers

Continuation passing style makes things tail recursive?

It hurts to ask it here. It really does. Every time I search in vain for the answers to my troubles, I see it. Taunting me. Stack Overflow. Anyway, some hellish influence caused me to attempt to solve the Towers of Hanoi. My first solution was…
Lily Chung
  • 2,919
  • 1
  • 25
  • 42
5
votes
1 answer

How to add a Increment Counter in F#

I'm trying to do the Tower of Hanoi but I don't know how to add a count incrementer. Here's my code: open System let disks = Int32.Parse(Console.ReadLine()) let rec hanoi num start finish = match num with | 0 -> [ ] | _ -> let temp = (6 -…
Marc Karam
  • 445
  • 6
  • 22
5
votes
2 answers

Crockford's hanoi function (from "The Good Parts")

At the moment I'm reading Douglas Crockford's book, and the towers of hanoi function is a bit over my head. Even with logging stuff to the console I wasn't able to really understand what's going on. Here's the function with my additions: var hanoi =…
north
  • 605
  • 7
  • 22
1
2 3
…
20 21