Torre di hanoi metodo iterativo

[oleg.fresi]

Ho risolto il problema della torre di hanoi in maniera ricorsiva molto tempo fà, ma è tornata la curiosità di come risolverla iterativamente. Il fatto è che non ho la più pallida idea di come creare un algoritmo che lo sappia fare, poichè non so quanti passaggi deve fare. Potreste darmi una mano per favore?

[vict85]

Il numero minimo/corretto di mosse è \(2^n-1\). Lo si dimostra ricorsivamente.

[oleg.fresi]

Si, questa formula la conoscevo già, ma io volevo sapere come implementare un algoritmo in c++ che risolva iterativamente la torre di hanoi dato un numero n di dischi e specificao il piolo di partenza, appoggio e arrivo.

[vict85]

Se non ricordo male la mossa \(1\le s\le 2^n -1\) dipende solamente da \(n\) e da \(s\pmod 3\). Ma è più utile/educativo se lo trovi da solo/a facendo i calcoli.

[oleg.fresi]

"s" per cosa sta?

[vict85]

Il numero della mossa, ma facendo qualche conto mi ricordavo male. Quel modulo non dermina ogni cosa, solo i due pioli (ma non la direzione). La direzione la devi determinare in base a quale delle die mosse è ammissibile

[vict85]

Comunque ho implementato il gioco in C++, qui c'è l'implementazione (la dimensione della torre deve essere specificata in fase di compilazione):

#include "TorreHanoiGioco.h"

//template<size_t N>
//void solve(vict::TorreHanoiGioco<N>& torre);

void solve(vict::TorreHanoiGioco<3>& torre)
{
	constexpr size_t S = vict::TorreHanoiGioco<3>::sorgente;
	constexpr size_t A = vict::TorreHanoiGioco<3>::ausiliario;
	constexpr size_t D = vict::TorreHanoiGioco<3>::destinazione;

	// esempio
	torre.mossa(S, D);
	torre.mossa(S, A);
	torre.mossa(D, A);
	torre.mossa(S, D);
	torre.mossa(A, S);
	torre.mossa(A, D);
	torre.mossa(S, D);
}

int main()
{
	constexpr size_t N = 3;
	vict::TorreHanoiGioco<N> torre;

	solve(torre);

	std::cout << "problema " << (torre.check() ? "" : "non ") << "risolto in "
		<< torre.numero_mosse() << " mosse." << std::endl;
}

TorreHanoiGioco.h:

#pragma once

#include "stack-fixed.h"

#include <iostream>
#include <cstdint>

namespace vict
{
	template <size_t N>
	class TorreHanoiGioco
	{
	public:
		TorreHanoiGioco() : _mosse(0) {
			for (size_t i = N; i != 0; --i)
			{
				_pali[sorgente].push(i);
			}
		};

		bool mossa(size_t i, size_t j)
		{
			bool res = false;
			if (i < N && j < N)
			{
				size_t li = _pali[i].last_or(N + 1);
				size_t lj = _pali[j].last_or(N + 1);
				if (li < lj) { res = mossa_internal(i, j); }
				else if (li > lj) {
					res = mossa_internal(j, i);
				}
			}
			if (!res)
			{
				std::cout << "Mossa non valida tra " << i << " e " << j << std::endl;
			}
			return res;
		}

		size_t numero_mosse()
		{
			return _mosse;
		}

		bool check()
		{
			if (!_pali[destinazione].full()) return false;
			size_t* arr = _pali[destinazione].get_data();
			for (size_t i = 0; i != N; ++i)
			{
				if (*(arr + i) != N - i) return false;
			}
			return true;
		}

		static size_t constexpr sorgente = 0;
		static size_t constexpr ausiliario = 1;
		static size_t constexpr destinazione = 2;

	private:
		bool mossa_internal(size_t i, size_t j)
		{
			size_t elem;
			if (!_pali[i].pop(elem)) return false;
			if (!_pali[j].push(elem)) return false;
			std::cout << "Mosso da " << i << " in " << j << std::endl;
			_mosse++;
			return true;
		}

		FixedStack<size_t, N> _pali[3];
		size_t _mosse = 0;
	};
}

stack-fixed.h

#pragma once
#include <cstddef>

namespace vict {
	template < typename T, size_t N >
	class FixedStack
	{
	public:
		FixedStack() noexcept : _end(0) {};
		~FixedStack() = default;

		// not copyable
		FixedStack(const FixedStack&) = delete;
		FixedStack& operator=(const FixedStack&) = delete;

		size_t num_entry() noexcept
		{
			return _end;
		}

		bool push(T element) noexcept
		{
			if (full())
				return false;

			_data[_end] = std::move(element);
			_end++;
			return true;
		}

		bool pop(T& element) noexcept
		{
			if (empty())
				return false;
			element = _data[--_end];
			return true;
		}

		bool last(T& element)
		{
			if (empty())
				return false;
			element = _data[_end - 1];
			return true;
		}

		T last_or(T value = T()) noexcept
		{
			return empty() ? value : _data[_end - 1];
		}

		T* get_data()
		{
			return &_data[0];
		}

		bool empty() noexcept
		{
			return _end == 0;
		}

		bool full() noexcept
		{
			return _end == N;
		}

	private:
		T _data[N];
		size_t _end;
	};
} // namespace vict

L'implementazione della funzione solve non è inclusa nel codice per darti la possibilità di testare i tuoi algoritmi. Ho inserito una implementazione banale della funzione nel caso N=3 per mostrarti come usare la classe.

P.S.: Ho creato la classe FixedStack perché mi andava, ma puoi usare qualsiasi classe simile al suo posto. Esistono anche altri approcci. Il gioco stampa a video le mosse fatte.

[oleg.fresi]

Non ho ancora studiato i template, ma proverò a studiare il tuo codice, potrei chiederti su cosa si basa? Comunque grazie infinite per l'aiuto, davvero molto gentile!

[oleg.fresi]

Che altri aprocci esistono?

[vict85]

Non è essenziale avere una classe per esempio. L'uso dei template non è necessario ed è semplice scrivere una versione in cui N viene inserito dall'utente. Il gioco stesso può probabilmente essere implementato usando meno memoria e suppongo che sia possibile implementare la funzione solve senza la limitazione n < 32 o 64. L'interfaccia della classe può essere tranquillamente diversa e potresti voler spostare o rimuovere l'output sulla console. Insomma ci sono tante piccole cose che possono cambiare.

[oleg.fresi]

Perfetto, grazie mille per l'iuto, buona giornata!