Towers of Hanoi non recursive: Is my code correct?

[peterparker]

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()

[sepp2k]

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).

[peterparker]

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.

[Gribouillis]

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):
    # write your algorithm here
    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().

[peterparker]

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