Formulation in Prolog

Question

I currently have the following problem, that I want to solve with Prolog. It's an easy example, that would be easy to solve in Java/C/whatever. My problem is that I believe to be too tied to Java's thinking to actually formulate the problem in a way that makes useof Prolog's logic power.

The problem is..

I have a set of 6 arrows, either pointing left or right. Let's assume that they are in the following starting configuration:

->
<-
->
<-
->
<-

Now, I can switch two arrows as long as they are next to each other. My goal is to discover which sequence of actions will make the initial configuration of arrows turn into

<-
<-
<-
->
->
->

My initial attempt at formulating the problem is..

right(arrow_a).
left(arrow_b).
right(arrow_c).
left(arrow_d).
right(arrow_e).
left(arrow_f).

atPosition(1, arrow_a).
atPosition(2, arrow_b).
atPosition(3, arrow_c).
atPosition(4, arrow_d).
atPosition(5, arrow_e).
atPosition(6, arrow_f).

This will tell Prolog what the initial configuration of the arrows are. But now how do I insert aditional logic in it? How to implement, for example, switchArrows(Index) ? Is it even correct stating the initial conditions like this, in Prolog? Won't it interfere later when I try to set, for example, that arrow_a is at position 6, atPosition(6, arrow_a) ?

Answer 1

Since a complete solution is posted already, here is mine:

solution(State0, Target) -->
    (    { State0 == Target } -> []
    ;    { step(State0, State1) },
         [State1],
         solution(State1, Target)
    ).

flip(->, <-).
flip(<-, ->).

step([], []).
step([A|Rest0], [A|Rest]) :- step(Rest0, Rest).
step([A0,A1|Rest], [B0,B1|Rest]) :- flip(A0, B0), flip(A1, B1).

Example query:

?- length(Solution, _), phrase(solution([->,<-,->,<-,->,<-], [<-,<-,<-,->,->,->]), Solution).
Solution = [[->, <-, ->, <-, <-, ->],
            [->, <-, ->, ->, ->, ->],
            [->, ->, <-, ->, ->, ->],
            [<-, <-, <-, ->, ->, ->]].

Since iterative deepening is used, we know that no shorter solution (less than 4 steps) is possible.

I also have a general comment on what you said:

It's an easy example, that would be easy to solve in Java/C/whatever. My problem is that I believe to be too tied to Java's thinking to actually formulate the problem in a way that makes useof Prolog's logic power.

Personally, I think this example is already much more than could be expected from a beginning, say, Java programmer. Please try to solve this problem in Java/C/whatever and see how far you get. In my experience, when students say they are "too tied to Java's thinking" etc., they cannot solve the problem in Java either. Prolog is different, but not that different that, if you had a clear idea of how to solve it in Java, could not translate it quite directly to Prolog. My solution uses the built-in search mechanism of Prolog, but you do not have to: You could implement the search yourself just as you would in Java.