CODEWITHSUNDEEP
prolog
Kate
Kate

Reputation: 83

How to make box a free, in the situation with the boxes on a table, SWI-Prolog?

I am a beginner at prolog and I am trying to solve the problem with the boxes as shown in the picture https://i.sstatic.net/BechG.png . My code is :

box(a).
box(b).
box(c).
table(t).
on(a,t).
on(b,t).
on(c,a).
free(b).
free(c).

move(X,Z),free(Y):-
   free(X),
   free(Z),
   on(X,Y).

move(X,t):-
   free(X),
   not(on(X,t)).

move(X,Y):-
   free(X),
   free(Y).

Only one box can be moved at at time, meaning that I can't grab two boxes from the table at the same time. I have a problem when it comes to box a being free when I put this command move(c,t),move(b,c),move(a,b). In SWI-Prolog it shows me false where it should have been a true. In all other choices it shows true and i think that the box a never becomes free.

Upvotes: 1

Views: 153

Answers (1)

Jan Wielemaker
Jan Wielemaker

Reputation: 1710

You take the wrong representation. Using facts is fine for representing an immutable world, but once you start searching you want to represent a mutable state of the world, which is best achieved in logical variables. That way you can exploit Prolog non-determinism and backtracking to find series of moves that gets you from the start state to the final state. So, let us represent the final state in the database as well and then rules to get the start and final states in variables. Our representation of a state is a series of (three) on(X,Y) terms.

final(a,b).
final(b,c).
final(c,t).

start(State) :-
    findall(on(X,Y), on(X,Y), State).
final(State) :-
    findall(on(X,Y), final(X,Y), FinalState),
    same_state(State, FinalState).

same_state(State1, State2) :-
    sort(State1, State),
    sort(State2, State).

Now we must define free in terms of the state. That is easy: the top one and the table are free:

free(X, State) :-
    box(X),
    \+ member(on(_,X), State).
free(t, _).

Now we can define a move as removing one on(X,Y) from the initial state and adding a new one:

move(State0, move(X,New), [on(X,New)|Rest]) :-
    select(on(X,_), State0, Rest),
    free(X, State0),
    free(New, State0),
    X \== New.

Next, we must make multiple moves. We must be careful not to get into a state we have seen before:

moves(State, [], _Visited, State).
moves(State0, [Move|T], Visited, State) :-
    move(State0, Move, State1),
    \+ ( member(V, Visited),
         same_state(State1, V)
       ),
    moves(State1, T, [State1|Visited], State).

And now we are almost done:

solve(Moves) :-
    start(State),
    moves(State, Moves, [State], Final),
    final(Final).

There is a lot to optimize. I'll leave that to you. The final two predicates do show the overall approach for searching: start at the beginning, make moves, avoiding to go back to and old state and test that you have found the target state. The whole stuff is shown in one file at https://swish.swi-prolog.org/p/BenchG.pl

Upvotes: 1

Related Questions