I have written the following code for Towers of Hanoi problem using non recursive approach. I guess it is not correct as the number of moves are not 2*n - 1, for eg, for 3 disks to be moved, it has to generate 7 moves. Thanks in advance.

`````` ######################
#   Towers of Hanoi  #
######################

numbers = []

def TowersofHanoi():
# Proram to simulate Towers of hanoi
# Objective is to move the disks from A to C
# with B as a temporary varialbel

print "Program to simulate Towers of Hanoi"
print "Users will input numbers of disks, which is 'A'"
print "The disks have to be moved from A to C"
print "With B as temporary placeholder"

print "Enter the number of disks to be moved:",

Num = int (raw_input("> "))
Src = Num
Aux = 0
Dst = 0
print "you have entered %d disks to be moved"
print "Source is -->", Src
print "Auxillary is -->", Aux
print "Destination is -->", Dst

print "Disk positions after the placement:"

#B = A-1
#print B
while Num >= 1:
print Num
Aux = Num-1
Src = Src-Aux
Dst = Src

print "Source is -->", Src
print "Auxillary is -->", Aux
print "Destination is -->", Dst
Src = Aux
Num = Num-1

numbers.append(Dst)
print numbers

print "The task of accomplishing the movements of disk is over"
print "This completes TOWERS OF HANOI!"
print "Final disk positions are:"
print "Source is -->", Src
print "Auxillary is -->", Aux
print "Destination is -->", len(numbers)

TowersofHanoi()
``````

## All 4 Replies

Yes, you're right - it's not correct. For one thing, as you said, the number of moves is wrong.

Further when I enter 3 as the number of disks, it tells me that after the first step there will be 1 disk on the source pile, 2 disks on the auxilary pile and 1 disk on the target pile, making a total of 4 disks. So where did the 4th disk come from? And in the second to last step there's only two disks. Obviously in a correct program there'd be the same number of disks at every step.

Also the program never prints which moves it actually performs, leaving you to guess that from the number of disks on each pile (which might be okay if those numbers weren't total nonsense).

So yes, your solution is wrong. I don't think there is a correct solution that doesn't use recursion or an explicit stack (or some encoding thereof).

Ok, so i need to used recursive solution for this. I had figured it out, because for non recursive solution, it is tough to determine the first legal move.

You can use a GUI to visualize your algorithm. Here is a program I found HERE using the turtle module to solve the hanoi problem, written by Gregor Lingl. This program contains an algorithm, but you you can use it to run your own algorithm too. For this, use the following code together with the Hanoi module

``````#!/usr/bin/env python
# -*-coding: utf8-*-
# hanoiclient.py
# warning: this is draft quality code

from Hanoi import Hanoi

class InvalidMove(Exception):
pass

class MyHanoi(Hanoi):
def __init__(self, nrOfDiscs, speed, algorithm):
self.algorithm = algorithm
Hanoi.__init__(self, nrOfDiscs, speed)

def move(self,  x, y):
if not all(z in (0, 1, 2) for z in (x, y)):
raise InvalidMove("Tower number not in (0, 1, 2)")
if not len(self.towers[x]):
raise InvalidMove("Tower %d is empty" % x)
if len(self.towers[y]) and self.towers[y][-1] < self.towers[x][-1]:
raise InvalidMove("Disc size disallows %d --> %d."
%(x, y))
self.hEngine.move(self.towers[x], self.towers[y])

def step(self):
# disable step button
pass

def start(self):
self.towers = list(getattr(self.hEngine, "tower"+x) for x in "ABC")
self.algorithm(self.hEngine.nrOfDiscs, self.move)

def my_algorithm(nrOfDiscs, move):
move(0, 1)
move(0, 2)
move(1, 2)
move(0, 2)

if __name__ == '__main__':
hanoi = MyHanoi(5, 3, my_algorithm) # replace by Hanoi(5, 3) to run Gregor Lingl's code.
``````

Put your code in the function my_algorithm().

Thanks, I will use it. This TOWERS OF HANOI is indeed an UNIQUE problem.

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, learning, and sharing knowledge.