losTorres de Hanoi El problema es un problema clásico para la recursividad. Se le dan 3 clavijas con discos en uno de ellos, y debe mover todos los discos de una clavija a otra, siguiendo las reglas dadas. También debes hacer esto con el número mínimo de movimientos.

Aquí hay un algoritmo recursivo que resuelve el problema:

void Hanoi3(int nDisks, char source, char intermed, char dest)
{
    if( nDisks > 0 )
    {
        Hanoi3(nDisks - 1, source, dest, intermed);
        cout << source << " --> " << dest << endl;
        Hanoi3(nDisks - 1, intermed, source, dest);
    }
}


int main()
{
    Hanoi3(3, 'A', 'B', 'C');

    return 0;
}

Ahora, imagine el mismo problema, solo con 4 clavijas, por lo que agregamos otra clavija intermedia. Cuando nos enfrentamos al problema de tener que elegir qué clavija intermediaria elegir en cualquier punto, elegiremos la más a la izquierda, en caso de que más de 1 sea libre.

Tengo el siguiente algoritmo recursivo para este problema:

void Hanoi4(int nDisks, char source, char intermed1, char intermed2, char dest)
{
    if ( nDisks == 1 )
        cout << source << " --> " << dest << endl;
    else if ( nDisks == 2 )
    {
        cout << source << " --> " << intermed1 << endl;
        cout << source << " --> " << dest << endl;
        cout << intermed1 << " --> " << dest << endl;
    }
    else
    {
        Hanoi4(nDisks - 2, source, intermed2, dest, intermed1);
        cout << source << " --> " << intermed2 << endl;
        cout << source << " --> " << dest << endl;
        cout << intermed2 << " --> " << dest << endl;
        Hanoi4(nDisks - 2, intermed1, source, intermed2, dest);
    }
}

int main()
{
    Hanoi4(3, 'A', 'B', 'C', 'D');

    return 0;
}

Ahora, mi pregunta es cómo generalizaría este enfoque recursivo para trabajarK clavijas? La función recursiva recibiría unchar[] que contendría las etiquetas de cada pila, por lo que la función se vería así:

void HanoiK(int nDisks, int kStacks, char labels[]) { ... }

Conozco el algoritmo Frame-Stewart, que probablemente es óptimo pero no está probado, y que te da lanúmero de movimientos. Sin embargo, estoy interesado en una solución estrictamente recursiva que siga el patrón de las soluciones recursivas para 3 y 4 clavijas, lo que significa que imprime los movimientos reales.

Al menos para mí, el pseudocódigo del algoritmo Frame-Stewart presentado en Wikipedia es bastante abstracto, y no he tenido éxito en traducirlo en un código que imprima los movimientos. Aceptaría una implementación de referencia de eso (para aleatoriok), o incluso un pseudocódigo más detallado.

Traté de encontrar algún tipo de algoritmo que permute la matriz de etiquetas en consecuencia, pero no tuve suerte de que funcione. Cualquier sugerencia es apreciada.

Actualizar:

Esto parece ser mucho más fácil de resolver en un lenguaje funcional. Aquí hay una implementación de F # basada en la solución Haskell de LarsH:

let rec HanoiK n pegs = 
    if n > 0 then 
        match pegs with
        | p1::p2::rest when rest.IsEmpty            
            ->  printfn "%A --> %A" p1 p2
        | p1::p2::p3::rest when rest.IsEmpty        
            ->  HanoiK (n-1) (p1::p3::p2::rest)
                printfn "%A --> %A" p1 p2
                HanoiK (n-1) (p3::p2::p1::rest)    
        | p1::p2::p3::rest when not rest.IsEmpty    
            ->  let k = int(n / 2)
                HanoiK k (p1::p3::p2::rest)
                HanoiK (n-k) (p1::p2::rest)
                HanoiK k (p3::p2::p1::rest)

let _ =
    HanoiK 6 [1; 2; 3; 4; 5; 6]

Y sin tratar 3 clavijas como un caso de borde:

let rec HanoiK n pegs = 
    if n > 0 then 
        match pegs with
        | p1::p2::rest when rest.IsEmpty            
            ->  printfn "%A --> %A" p1 p2
        | p1::p2::p3::rest     
            ->  let k = if rest.IsEmpty then n - 1 else int(n / 2) 
                HanoiK k (p1::p3::p2::rest)
                HanoiK (n-k) (p1::p2::rest)
                HanoiK k (p3::p2::p1::rest)

Tenga en cuenta que esto no maneja casos degenerados para los cuales no hay solución, comoHanoiK 2 [1; 2]