title: Prolog: Solve Peg Jumping Problem (Heuristics/A*)
body: <p>I am trying to solve the following question: </p>
  
  <p>A puzzle consists of three black pegs, three white pegs, and an empty space in the middle ("BBBOWWW").</p>
  
  <p>The puzzle has two moves with associated costs: 
  (a) A peg may move into an adjacent empty location (cost of 1). 
  (b) A peg can hop over one or two other pegs into the empty position. This has a cost equal to the number of pegs jumped over.</p>
  
  <p>The goal is to have all the white pegs to the left of all the black pegs. The position of the blank is not important. </p>
  
  <p>I am allowed to use any programming language I choose, and am hoping to solve this using Prolog to gain experience. I have been able to implement a simplified version of this problem that finds the shortest path, but am struggling with the A* and heuristic implementation.</p>
  
  <p>I have attached the following Prolog code and the query I am using. </p>
  
  <p>My question is how to go about implementing the A* algorithm into my code? I have not been able to find useful examples and would appreciate any guidance/hints.</p>
  
  <p>Thank you.</p>
  
  <p>QUERY:</p>
  
  <pre><code>length(Path, _),
  initial_state(Initial),
  phrase(moves(Initial), Path),
  maplist(writeln, Path).
  </code></pre>
  
  <p>PROGRAM:</p>
  
  <pre><code>% Initial state
  initial_state([b,b,b,o,w,w,w]).
  
  % 7 possible goal states
  goalState([w,w,w,o,b,b,b]).
  goalState([w,w,w,b,o,b,b]).
  goalState([w,w,w,b,b,b,o]).
  goalState([w,w,o,w,b,b,b]).
  goalState([w,o,w,w,b,b,b]).
  goalState([o,w,w,w,b,b,b]).
  
  % All possible moves
  move([E|Es]) --&gt; [E], move(Es).
  move([b,o|Solution]) --&gt; [o,b], list(Solution). 
  move([o,w|Solution]) --&gt; [w,o], list(Solution).
  move([o,X,w|Solution]) --&gt; [w,X,o], list(Solution).
  move([b,X,o|Solution]) --&gt; [o,X,b], list(Solution).
  move([o,X,X,w|Solution]) --&gt; [w,X,X,o], list(Solution).
  move([b,X,X,o|Solution]) --&gt; [o,X,X,b], list(Solution).
  move([w,X,X,o|Solution]) --&gt; [o,X,X,w], list(Solution).
  move([o,X,X,b|Solution]) --&gt; [b,X,X,o], list(Solution).
  
  list([]) --&gt; [].
  list([L|Solution]) --&gt; [L], list(Solution).
  
  moves(S)  --&gt; [S], {goalState(S)}.
  moves(S0) --&gt; [S0], {phrase(move(S0),S)}, moves(S).
  </code></pre>
  
  <p>I based my initial solution off of the following:
  <a href="https://stackoverflow.com/questions/36879616/prolog-program-that-solves-the-peg-jump-puzzle">Prolog program that solves the peg jump puzzle</a></p>