Formulating a problem 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

Your problem can be formulated as a sequence of transitions between configurations. First think about how you want to represent a single configuration. You could use a list to do this, for example [->,<-,->,<-,->,<-] to represent the initial configuration. A single move could be described with a relation step/2 that is used as step(State0, State) and describes the relation between two configurations that are "reachable" from each other by flipping two adjacent arrows. It will in general be nondeterministic. Your main predicate then describes a sequence of state transitions that lead to the desired target state from an initial state. Since you want to describe a list (of configurations), DCGs are a good fit:

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

And then use iterative deepening to find a solution if one exists, as in:

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

The nice thing is that Prolog automatically backtracks once all sequences of a given length have been tried and the target state could not yet be reached. You only have to implement step/2 now and are done.

Answer 2

Here is my solution:

solution(Begin, End, PrevSteps, [Step | Steps]) :-
    Step = step(Begin, State1),
    Step,
    forall(member(step(S, _), PrevSteps),
           State1 \= S
          ), % prevent loops
    (   State1 == End
    ->  Steps = []
    ;   solution(State1, End, [Step | PrevSteps], Steps)
    ).

rev(->,<-).
rev(<-,->).

step([X,Y|T], [XX,YY|T]) :- rev(X,XX), rev(Y, YY).
step([A,X,Y|T], [A,XX,YY|T]) :- rev(X,XX), rev(Y, YY).
step([A,B,X,Y|T], [A,B,XX,YY|T]) :- rev(X,XX), rev(Y, YY).
step([A,B,C,X,Y|T], [A,B,C,XX,YY|T]) :- rev(X,XX), rev(Y, YY).
step([A,B,C,D,X,Y], [A,B,C,D,XX,YY]) :- rev(X,XX), rev(Y, YY).


run :-
    solution([->,<-,->,<-,->,<-], [<-,<-,<-,->,->,->],[],Steps),
    !,
    forall(member(Step,Steps),writeln(Step)).

It finds only first solution of all possible, though I suppose the solution found is not optimal, but rather first working one.

Answer 3

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.

Answer 4

Managed to transform mat's code to mercury:

:- module arrows.

:- interface.

:- import_module io.

:- pred main(io, io).
:- mode main(di, uo) is cc_multi.

:- implementation.

:- import_module list, io, int.

:- type arrow ---> (->); (<-).

:- mode solution(in, in, in, in, out, in) is cc_nondet.
solution(State0, Target, MaxDepth, CurrentDepth) -->
    {CurrentDepth =< MaxDepth},
    (    { State0 = Target } -> []
    ;    { step(State0, State1) },
         [State1],
         solution(State1, Target, MaxDepth, CurrentDepth + 1)
    ).

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

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

main -->
    (({
    member(N, 1..10),
        solution([->,<-,->,<-,->,<-], [<-,<-,<-,->,->,->], N, 0, Solution, [])
    }) 
    -> print(Solution)
    ; print("No solutions")
    ).

Compiling with mmc --infer-all arrows.m to infer signatures & determinism