title: A* search in Prolog
body: <p>I tried implementing a <a href="https://en.wikipedia.org/wiki/15_puzzle" rel="nofollow noreferrer">15puzzle</a> solver in prolog as a way to try and learn the language and take advantage of the native backtracking. I followed a few online <a href="https://www.cpp.edu/~jrfisher/www/prolog_tutorial/5_1.html" rel="nofollow noreferrer">resources</a> and wrote this simple version of the A* algorithm.</p>
  
  <p>All it does is generate all the children of a node and stick them at the end of a queue BFS style (eventually I intend to replace this with a priority queue for efficiency), and explores all the children, backtracking the solution with findall.</p>
  
  <p>Relevant code:</p>
  
  <pre><code>solve(State,Soln) :- f_function(State,0,F),
                   search([State#0#F#[]],[],S), reverse(S,Soln).
  
  search([State#_#_#Soln|_], All, Soln) :-
     goal(State).
  search([B|R], All, S) :-
     gen(B, R, Children),
     %insert_all(Children,R,Open),     %insertion sort option
     append(R, Children, Open),        %naive option
     append(All, Children, Allnew),
     search(Open, Allnew, S).
  
  gen(State#D#_#A, R,C) :-
     findall(Child#D1#F1#[Move|A],
           (  mover(State, Child, Move),
              D1 is D + 1,
              f_function(Child, D1, F1),
              \+member(Child, R)
           ), C).
  </code></pre>
  
  <p>This code finds the solution for simple initial configurations with only a few movements needed to reach the solution, but for more complex test cases, it doesn't halt.</p>
  
  <p>To avoid infinite cycles, I keep a list All of all the states ever generated (even if they are already gone from the queue), and check my new children against that list before adding them.</p>
  
  <p>If someone could tell me why this doesn't halt I would really appreciate it!</p>