Tower of Hanoi
O problema Torre de Hanoi consiste basicamente de mover todos os círculos inseridos em um dos pilares para um outro pilar. Sua resolução utilizando recursividade estabelece um código pequeno e que atende as necessidades de forma ágil. Para uma adequação do problema a ser submetido aos casos de busca, foi necessário uma outra representação para os estados. Foi também convencionada a movimentação de todos os círculos para o último pilar (demonstrada no código fonte).
Como restrição a observar tem-se: não pode haver inserção de um círculo maior sobre outro menor.
Código Fonte para submissão às buscas:
%----------- Buscas ---------------------------------------------
Neste ponto se localiza as buscas de Largura e Profundidade cuja descrição
pode ser vista acessando sua página respectiva através da página principal.
Dessa forma é facilitada a visualização do trecho específico referente ao problema.
% ---------- Representação de Estados para o Problema ----------
% Estado Inicial
estado_inicial([[1,2,3],[],[]]).
% Estado Final
[[],[],[1,2,3]] e_a_meta.
% Operações possíveis/permitidas para mudanças de estado.
operacao(move_A_para_C) transforma [[X|A],B,C] em [A,B,[X|C]] :- menor(X,C).
operacao(move_A_para_B) transforma [[X|A],B,C] em [A,[X|B],C] :- menor(X,B).
operacao(move_B_para_A) transforma [A,[X|B],C] em [[X|A],B,C] :- menor(X,A).
operacao(move_B_para_C) transforma [A,[X|B],C] em [A,B,[X|C]] :- menor(X,C).
operacao(move_C_para_A) transforma [A,B,[X|C]] em [[X|A],B,C] :- menor(X,A).
operacao(move_C_para_B) transforma [A,B,[X|C]] em [A,[X|B],C] :- menor(X,B).
% Verifica se um dado elemento é menor que a cabeça da lista, ou seja,
% o disco só poderá ser colocado acima de outro caso ele seja menor que
% o ultimo disco.
menor(X,[]).
menor(X,[Y|Cauda]) :- X < Y.
Código Fonte utilizando processo recursivo:
%Problema da Torre de Hanoi
torre :-
write('Numero de discos: '),
read(X),
hanoi(X).
hanoi(N) :- move(N,esquerda,centro,direita).
move(0,_,_,_).
move(N,E,C,D) :-
N1 is N-1,
move(N1,E,D,C),
nl,write('mova de '),write(E),write(' para '),write(D),nl,
move(N1,C,E,D).
Resolução por busca em largura
(utilizando 3 círculos)
# Abolishing hanoi.pl [d:\users\jaque\ia\]
# 0.00 seconds to consult hanoi.pl [d:\users\jaque\ia\]
| ?- resolva_bl.
Estado inicial: [[1,2,3],[],[]].
move_A_para_C: [[2,3],[],[1]].
move_A_para_B: [[3],[2],[1]].
move_C_para_B: [[3],[1,2],[]].
move_A_para_C: [[],[1,2],[3]].
move_B_para_A: [[1],[2],[3]].
move_B_para_C: [[1],[],[2,3]].
move_A_para_C: [[],[],[1,2,3]].
yes
Resolução por busca em profundidade (utilizando 3 círculos)
| ?- resolva_bp.
Estado inicial: [[1,2,3],[],[]].
move_A_para_C: [[2,3],[],[1]].
move_A_para_B: [[3],[2],[1]].
move_C_para_A: [[1,3],[2],[]].
move_A_para_B: [[3],[1,2],[]].
move_A_para_C: [[],[1,2],[3]].
move_B_para_A: [[1],[2],[3]].
move_A_para_C: [[],[2],[1,3]].
move_B_para_A: [[2],[],[1,3]].
move_C_para_A: [[1,2],[],[3]].
move_A_para_B: [[2],[1],[3]].
move_A_para_C: [[],[1],[2,3]].
move_B_para_A: [[1],[],[2,3]].
move_A_para_C: [[],[],[1,2,3]].
yes
Resolução por busca em largura (utilizando 4 círculos)
Ocorreu estouro de pilha.
| ?-
# Abolishing hanoi.pl [u:\valeria\ia\ia_p2programas\]
# 0.00 seconds to consult hanoi.pl [u:\valeria\ia\ia_p2programas\]
| ?- resolva_bl.
Error 4, Heap Space Full, Trying asn/2
Aborted
| ?-
Resolução por busca em profundidade (utilizando 4 círculos)
| ?- resolva_bp.
Estado inicial: [[1,2,3,4],[],[]].
move_A_para_C: [[2,3,4],[],[1]].
move_A_para_B: [[3,4],[2],[1]].
move_C_para_A: [[1,3,4],[2],[]].
move_A_para_B: [[3,4],[1,2],[]].
move_A_para_C: [[4],[1,2],[3]].
move_B_para_A: [[1,4],[2],[3]].
move_A_para_C: [[4],[2],[1,3]].
move_B_para_A: [[2,4],[],[1,3]].
move_C_para_A: [[1,2,4],[],[3]].
move_A_para_B: [[2,4],[1],[3]].
move_A_para_C: [[4],[1],[2,3]].
move_B_para_A: [[1,4],[],[2,3]].
move_A_para_C: [[4],[],[1,2,3]].
move_A_para_B: [[],[4],[1,2,3]].
move_C_para_A: [[1],[4],[2,3]].
move_A_para_B: [[],[1,4],[2,3]].
move_C_para_A: [[2],[1,4],[3]].
move_B_para_A: [[1,2],[4],[3]].
move_A_para_C: [[2],[4],[1,3]].
move_A_para_B: [[],[2,4],[1,3]].
move_C_para_A: [[1],[2,4],[3]].
move_A_para_B: [[],[1,2,4],[3]].
move_C_para_A: [[3],[1,2,4],[]].
move_B_para_A: [[1,3],[2,4],[]].
move_A_para_C: [[3],[2,4],[1]].
move_B_para_A: [[2,3],[4],[1]].
move_C_para_A: [[1,2,3],[4],[]].
move_B_para_C: [[1,2,3],[],[4]].
move_A_para_C: [[2,3],[],[1,4]].
move_A_para_B: [[3],[2],[1,4]].
move_C_para_A: [[1,3],[2],[4]].
move_A_para_B: [[3],[1,2],[4]].
move_A_para_C: [[],[1,2],[3,4]].
move_B_para_A: [[1],[2],[3,4]].
move_A_para_C: [[],[2],[1,3,4]].
move_B_para_A: [[2],[],[1,3,4]].
move_C_para_A: [[1,2],[],[3,4]].
move_A_para_B: [[2],[1],[3,4]].
move_A_para_C: [[],[1],[2,3,4]].
move_B_para_A: [[1],[],[2,3,4]].
move_A_para_C: [[],[],[1,2,3,4]].
yes