% breadth-first search to solve the hanoi towers problem
% example of query for initial state with three stacks, where two are initially empty
% ?- bfs([[c,b,a],[],[]],Solution).
% The final state (goal state) is any stack in the form [a,b,c]

:- use_module(library(lists)).

bfs(Initial,Final) :- solve([[Initial]],Final).

solve([[N|Path]|_],[N|Path]) :- goal(N).
solve([Path|Paths],Solution) :-
  extend(Path,NewPaths),
  append(Paths,NewPaths,Paths1),
  solve(Paths1,Solution).

extend([Node|Path],NewPaths) :-
  bagof([NewNode,Node|Path],
   (s(Node,NewNode), \+ member(NewNode,[Node|Path])),
    NewPaths), !.
extend(Path,_). % node has no successor.

% mv Top1 to Stk2 em St2
s(Stacks,[Stk1,[Top1|Stk2]|Otherstacks]) :- 
% [Top1|Stk1] is a stack in St1
   myselect([Top1|Stk1],Stacks,Stacks1), 
% Stk2 is a stack in St1
   myselect(Stk2,Stacks1,Otherstacks).   
    
goal(Estado) :- member([a,b,c],Estado).

myselect(X,[X|T],T).
myselect(X,[Y|T],[Y|T1]) :-
    myselect(X,T,T1).