вторник, 18 апреля 2017 г.

Hanoi tower algorithm to move from any to any state (1993)

In the year 1993 I have developed an algorithm to solve a generalized Hanoi tower problem: move from any state to any state.

The algorithm is very simple and uses a nice state representation: a ternary number. The right digit represents the number of rod where the largest disk resides, then the number of the next disk and so on to the number of rod of the smallest disk. 64 bit unsigned integer can hold state of up to 40 disks.

For the original Hanoi tower problem we have this encoding: source=0000...0, destination=2222...2.

It was also possible to use strings (with the largest disk at the left), but it was harder to allocate memory in this case, so I chose the integer representation.

It is easy to note that for moving a large disk it is required to move all smaller disks to an intermediate rod. So the algorithm first reduces the source and destination states if some large disks are on their target positions, then recursively moves the smaller disks to an intermediate rod, then moves the large disk, then recursively moves the smaller disks to their final destinations.

Here is the algorithm encoded in C (written in 1993, adapted now for ANSI C):

#include <stdio.h>
 
void Move(int f,int t)
{
        printf("%c%c  ",f+'0',t+'0');
}

void Hanoi3(unsigned from,unsigned to,int n)
{
        unsigned via,f,t,v;
        int i;

        if(n==0)
                return; /* nothing to do */
 
        /* reduce equal positions of largest disks */
        do
        {
                f=from%3;
                t=to%3;
                from/=3;
                to/=3;
                n--;
        }
        while(f==t && n>=0);
 
        if(n<0)
                return; /* nothing to do */

        /* now f is the source position of the largest disk,
           and t is its target position */

        v=3-f-t; /* intermediate rod */
        via=0; /* intermediate state */
        for(i=0; i<n; i++)
                via=via*3+v;

        Hanoi3(from,via,n);
        Move(f,t);
        Hanoi3(via,to,n);
}