Extended Hanoi Tower

Question

Problem Definition
I'm trying write a c++ program to solve the Extended Hanoi Tower problem.
Extended Hanoi Tower is similar to the standard hanoi problem. The difference is that, odd rings are in A (1, 3, 5, ...) and even rings are in B (2, 4, 6, ...). The question asks, how can we transfer all of the rings to C in a recursive way?

I've written what I've done so far. Any help letting me implement my approach or Any ideas to implement the program would be appreciated ! Thanks !

Rules
1. Only one disk can be moved at a time.
2. No disk may be placed on top of a smaller disk.
3. The output should contain the necessary moves, not the minimum necessary moves
4. The total number of disks may be even or odd.
5. Implementation should be recursive.

Approach 1
we assume that the problem has been solved for n-1 rings that are currently in A and B. That means they are all moved to C and C have 2n-2 ordered rings. After that we have to handle the remaining rings in A & B. That means we have to take smaller ring and place it on the bigger ring (from B to A). After that we have to merge the rings in C (2n-2) and the rings in A (2). Finally we have to use standard Hanoi solution to reach our goal and move all of the rings to C.

Implementation 1

int main()
{
    long int n;
    cin >> n;
    // move odd & even rings to the first shaft, recursively
    customHanoi(n);
    // move all rings from first shaft to the destination shaft, recursively
    standardHanoi(n);
    return 0;
}

// the shaft holds the odd rings: A
// the shaft holds the even rings: B
// the final destination shaft: C
void customHanoi(int n, char A, char B, char C)
{
    if (n == 1)
        return;
    else if (n == 2)
    {
        cout << B << " " << A << endl;
        return;
    }
    else if (n == 3)
    {
        cout << A << " " << C << endl;
        cout << B << " " << A << endl;
        cout << C << " " << A << endl;
    }
    else
    {
        // here we have some missing code !
    }
}

// a recursive function to find the solution for standard hanoi
void standardHanoi(int n, char from, char helper, char to)
{
    // the base condition
    if (n == 1)
    {
        cout << from << " " << to << endl;
        return;
    }
    // the recursive calls
    standardHanoi(n - 1, from, to, helper);
    cout << from << " " << to << endl;
    standardHanoi(n - 1, helper, from, to);
}

Releated Resources
Link

Answer 1

We can put 1 from A over 2 on B.

We can put 1,2 from B over 3 on A by Standard Hanoi. All the other disks are larger and can be ignored.

We can put 1,2,3 from A over 4 on B by Standard Hanoi. All the other disks are larger and can be ignored. ........

When we've arranged all disks on one pole, they are either on A (if total number of disks was odd) or B (even).

Move them all to C by Standard Hanoi.

Although, this may be considered an iterative approach, while you asked for a recursive one.

So, recursive: assume there's n disks in total. Move n-1 disks to C by recursive application. Move n-1 disks from C to A (n is odd) or B (n is even) by Standard Hanoi. Move the resulting n disks to C by Standard Hanoi.

This is very similar to what you proposed, except n stands for the total number of disks (rings). It is also not purely recursive.

Answer 2

Many thanks to @Will-Ness !!
This is one of the possible solutions.
Hope this helps ! :)

#include <iostream>
using namespace std;

// function declarations
void customHanoi(long int, char = 'A', char = 'B', char = 'C');
void standardHanoi(long int, char = 'A', char = 'B', char = 'C');

int main()
{
    // initialize the variable
    long int n;
    // getting the number of rings
    cin >> n;
    // move odd & even rings to the first shaft, recursively
    // after that move all rings from first shaft to the destination shaft
    customHanoi(n);
    // our program finished successfully
    return 0;
}

// A: the shaft that holds odd rings
// B: the shaft that holds even rigns
// C: the final destination shaft
void customHanoi(long int n, char A, char B, char C)
{
    // initialize the variable
    static long int level = 1;

    // we can't handle zero/negative disk
    if (n < 1)
        return;

    // the base condition of recursion
    if (level == n)
    {
        // now, we moved all rings to the first shaft
        // so, we have to move them to the destination shaft
        standardHanoi(n);
        // finish the execution of recursion
        return;
    }

    // reordering the disks
    // based on even or odd number of disks & current level
    if (n % 2 == 1)
    {
        if (level % 2 == 1)
            standardHanoi(level, A, C, B);
        else
            standardHanoi(level, B, C, A);
    }
    else
    {
        if (level % 2 == 1)
            standardHanoi(level, B, C, A);
        else
            standardHanoi(level, A, C, B);
    }

    // go to the next level, it helps us control the flow
    level++;
    // the recursive calls
    customHanoi(n);
}

// a recursive function to find the solution for standard hanoi
void standardHanoi(long int n, char from, char helper, char to)
{
    // the base condition
    if (n == 1)
    {
        cout << from << " " << to << endl;
        return;
    }
    // the recursive calls
    standardHanoi(n - 1, from, to, helper);
    cout << from << " " << to << endl;
    standardHanoi(n - 1, helper, from, to);
}