Tower of Hanoi - n peg solution algorithm

Question

I was implementing the tower of hanoi problem to understand more about recursion. I was able to implement it using the 3 peg case, however, when I wanted to use more pegs (to generate less moves) I understand the Frame-Stewart solution where I have to break the number of disks I have and stack onto one peg and never touch that peg while I am transferring disks from the source peg to the destination pegs with all the intermediate pegs. However, I don't understand how write something like move(disks, 1, i, {2...K}) as a function. How can I write the names of all the pegs in the function prototype when I don't even know them from the beginning? I have given below what I worked up for the 3 disk solution, but I need help with the more general case.

// private member function: primitive/basic move of the top disk
    // from the source peg to the destination peg -- and legality-check
    void move_top_disk(int source, int dest)
    {
        cout << "Move disk " << towers[source].front() << " from Peg ";
        cout << source+1 << " to Peg " << dest+1;
        towers[dest].push_front(towers[source].front());
        towers[source].pop_front();
        if (true == is_everything_legal())
            cout << " (Legal)" << endl;
        else 
            cout << " (Illegal)" << endl;
    }

    // private member function: recursive solution to the 3 Peg Tower of Hanoi
    void move(int number_of_disks, int source, int dest, int intermediate)
    {
        if (1 == number_of_disks)
        {
            moves++;
            move_top_disk (source, dest);
        }
        else 
        {
            moves++;
            move (number_of_disks-1, source, intermediate, dest);
            move_top_disk (source, dest);
            move (number_of_disks-1, intermediate, dest, source);
        }
    }

I don't understand what kind of changes I would need to make to my "move" function to solve for a 6 pegs case. Thanks

I don't know how to implement the move function. I can't figure out how to include more than 2 towers used for intermediates for switching. — Josh

Victor Ronin Victor Ronin · Accepted Answer · 2012-09-21T03:02:42

You will need to modify the last block of code, where it does move, move-top-disk, move.

And here is the article regarding solution of Hanoi towers for N pegs: Towers of Hanoi with K pegs

Tower of Hanoi - n peg solution algorithm

1 Answers