Towers of Hanoi Iterative Solution Issue

Question

I am having trouble with an iterative solution to the Towers of Hanoi puzzle. As this was a university task, we have been given pseudo-code to follow.

Towers(number, src, dest, alt)
begin
    push { number, src, dest, alt }
    while NOT stack.empty
        pop { number, src, dest, alt }
        if number = 1
            print "Move 1 disc from " + src + " to " + dest
        else
            push { number – 1, alt, dest, src }
            push { 1, src, dest, alt }
            push { number – 1, src, alt, dest }
        end-if
    end-while
end

This is my attempt in C#:

static void TowersIterative(uint number, char src, char dest, char alt)
{
    Stack<Move> _Stack = new Stack<Move>();

    _Stack.Push(new Move(number, src, dest, alt));
    while (_Stack.Count != 0)
    {
        _Stack.Pop();
        if (number == 1)
            Console.WriteLine("Move one disc from {0} to {1}", src, dest);
        else
        {
            _Stack.Push(new Move(number - 1, alt, dest, src));
            _Stack.Push(new Move(1, src, dest, alt));
            _Stack.Push(new Move(number - 1, src, alt, dest));
        }
    }
}

Nothing much is going on with the move class at the moment.

class Move
{
    private char _Src, _Alt, _Dest;
    private uint _Number;

    public Move(uint number, char src, char dest, char alt)
    {
        _Number = number;
        _Src = src;
        _Alt = alt;
        _Dest = dest;
    }
}

This is an example of the desired output when number = 3, src = 'L', alt = 'M', and dest = 'R':

Move one disc from L to M
Move one disc from L to R
Move one disc from M to R

At the moment, the while loop in the TowersIterative method infinitely loops, and the number variable never equals 1.

score 1 · Answer 1 · edited May 23 '17 at 10:27

The problem is that you are ignoring the data popped off the stack and are instead using the arguments as if they had been popped off. I'd suggest breaking TowersIterative into two parts to avoid this danger:

class Move
{
    public char Src { get; private set; }
    public char Alt { get; private set; }
    public char Dest { get; private set; }
    public uint Number { get; private set; }

    public Move(uint number, char src, char dest, char alt)
    {
        Number = number;
        Src = src;
        Alt = alt;
        Dest = dest;
    }
}

public static class Hanoi
{
    static void TowersIterative(uint number, char src, char dest, char alt)
    {
        Stack<Move> _Stack = new Stack<Move>();

        _Stack.Push(new Move(number, src, dest, alt));

        TowersIterative(_Stack);
    }

    private static void TowersIterative(Stack<Move> _Stack)
    {
        while (_Stack.Count != 0)
        {
            var move = _Stack.Pop();
            if (move.Number == 1)
                Console.WriteLine("Move one disc from {0} to {1}", move.Src, move.Dest);
            else
            {
//              _Stack.Push(new Move(number - 1, alt, dest, src));
                _Stack.Push(new Move(move.Number - 1, move.Alt, move.Dest, move.Src));

//              _Stack.Push(new Move(1, src, dest, alt));
                _Stack.Push(new Move(1, move.Src, move.Dest, move.Alt));

//              _Stack.Push(new Move(number - 1, src, alt, dest));
                _Stack.Push(new Move(move.Number - 1, move.Src, move.Alt, move.Dest));
            }
        }
    }
}

I changed your fields in Move to public readonly properties, since this is generally considered to be good programming style

BartoszKP · Accepted Answer · 2014-08-24T15:45:47.133

This is because the number variable is used in two meanings - one is the method parameter name, but the pseudo-code's intent is to use it as the value of the number property of the element popped from the stack. This should work:

static void TowersIterative(uint number, char src, char dest, char alt)
{
    var stack = new Stack<Move>();

    stack.Push(new Move(number, src, dest, alt));
    while (stack.Count != 0)
    {
        var move = stack.Pop();
        if (move.Number == 1)
            Console.WriteLine("Move one disc from {0} to {1}", move.Src, move.Dest);
        else
        {
            stack.Push(new Move(move.Number - 1, move.Alt, move.Dest, move.Src));
            stack.Push(new Move(1, move.Src, move.Dest, move.Alt));
            stack.Push(new Move(move.Number - 1, move.Src, move.Alt, move.Dest));
        }
    }
}

And of course add appropriate properties to the Move class:

class Move
{
    public uint Number { get; private set; }

    public char Src { get; private set; }

    public char Dest { get; private set; }

    public char Alt { get; private set; }

    public Move(uint number, char src, char dest, char alt)
    {
        this.Number = number;
        this.Src = src;
        this.Alt = alt;
        this.Dest = dest;
    }
}

I've also renamed the variables, to conform to commonly used conventions. See a Working Demo.

Towers of Hanoi Iterative Solution Issue

2 Answers2