title: Towers of Hanoi using Lists Prolog
body: <p>I know that there is already sample programs floating around that cover this, but I need to do the towers of hanoi with 6 discs a specific way for an assignment and I'm having trouble. Code I currently have is below: </p>
  
  <pre><code>s([],[],[]).
  
  initial(s([1,2,3,4,5,6], [], [])).
  
  goal(s([],[],[1,2,3,4,5,6])).
  </code></pre>
  
  <p>I also have 26 lines of code to verify valid states, however I tested that code on it's own and it works, the issue I'm having is creating the code to move the discs from stack to stack. An example of what I'm trying to do along with an example query is below:</p>
  
  <pre><code>changeState((s([A | B],[],[])), s([C], [D], [])) :- C is B, D is A.
  ?- changeState((s([1,2,3,4,5,6],[],[])), s([2,3,4,5,6], [1], [])).
  </code></pre>
  
  <p>So this would be the very beginning, where all 6 plates are on the first stack, and I want to move the top plate to the second stack. Essentially, I want to be able to remove the first element from a list, and add it to another list, whether it is empty or not.</p>
  
  <p><strong>Edits:</strong></p>
  
  <p>Got what I needed above working, now I just need help fixing the traverse predicate. Entire code is below:</p>
  
  <pre><code>%Post A, Post B, Post C
  s([],[],[]).
  
  initial(s([1,2,3,4,5,6], [], [])).
  
  goal(s([],[],[1,2,3,4,5,6])).
  
  valid([], _).
  valid([H|_], X) :-
      X &lt; H.
  
  changeState((s([A|T1], T2, T3)), s(T1, [A|T2], T3)) :-
      valid(T2, A).
  changeState((s([A|T1], T2, T3)), s(T1, T2, [A|T3])) :-
      valid(T3, A).
  changeState(s(T1, [A|T2], [B|T3]), s(T1, T2, [A,B|T3])) :-
      valid(A,B).
  changeState(s([A|T1], T2, [B|T3]), s([B,A|T1], T2, T3)) :-
      valid(B, A).
  changeState(s(T1, [A|T2], [B|T3]), s(T1, [B,A|T2], T3)) :-
      valid(B, A).
  changeState(s([A|T1], [B|T2], T3), s(T1, [A,B|T2], T3)) :-
      valid(A,B).
  changeState(s([A|T1], [B|T2], T3), s([B,A|T1], T2, T3)) :-
      valid(B,A).
  changeState(s([A|T1], T2, [B|T3]), s(T1, T2, [A,B|T3])) :-
      valid(A,B).
  changeState(s(T1, [A|T2], T3), s(T1, T2, [A|T3])) :-
      valid(T3, A).
  changeState(s(T1, [A|T2], T3), s([A|T1], T2, T3)) :-
      valid(T1, A).
  changeState(s(T1, T2, [A|T3]), s(T1, [A|T2], T3)) :-
      valid(T2, A).
  changeState(s(T1, T2, [A|T3]), s([A|T1], T2, T3)) :-
      valid(T1, A).
  
  traverse(StartNode,Sol,_) :- goal(StartNode), Sol = [StartNode].
  traverse(StartNode,Sol,Visit) :- changeState(StartNode, NextNode),
         not(member(NextNode, Visit)),
         traverse(NextNode, PartialSol, [NextNode|Visit]),
         Sol = [StartNode | PartialSol].
  </code></pre>
  
  <p>When I run this query:</p>
  
  <pre><code>?- traverse((s([1,2,3,4,5,6], [], [])), Sol, s([1,2,3,4,5,6], [], [])).
  </code></pre>
  
  <p>I get this output: <img src="https://i.gyazo.com/b388cd2b80fe4bcb4c74289c2b4d4aef.png" alt="output"></p>
  
  <p>I've left it running after I get those responses for about 10 minutes and it still doesn't produce new ones so it's just continuing to run over and over again. As mentioned above, the point of the program is to solve the Towers of Hanoi problem with 6 discs using Lists. For those not familiar with Towers of Hanoi, you essentially need to move all discs from the first stack, to the last 3rd stack. You can only move 1 disc at a time, and you cannot place a larger disc on-top of a smaller disc. So you start with (s([1,2,3,4,5,6], [], [])) with each list representing Stack A, Stack B, Stack C respectively, and the goal is to end with (s([], [], [1,2,3,4,5,6])). I manually ran through an entire solution (63 moves) through the changeState predicates and all transitions were accepted, so the issue is with the transverse predicate. The transverse predicate is meant to show all steps that lead up to the solution, and all possible solutions. It's also meant to stop cycles, so that it's not just swapping the same 2 discs over and over again. Can't quite figure out what's wrong with my predicates thats causing me to get this output, I'm still fairly new to prolog, so I would appreciate any help!</p>