Next predicate confusion

Question

I'm in the process of learning prolog, I'm currently writing a next predicate for a game which is really simple.

you have a list [1,0,1,0,0,1] A legal move is move a 1 to a zero position, the 1 can only move right to the first position containing 0, but it is allowed to jump over other values if necessary.

firstly I wrote a predicate to change the value 0 to 1:

flip_first_zero([0|Tail], [1|Tail]). 

simple enough, now I'm trying to find the legal moves, I will try to explain my thought process:

next([],[],[]).
next([Head|Tail], Rest, Out):-
    flip_first_zero([Head|Tail],List1),
    append(Rest,List1,Out).

next([Head|Tail], [Head|Rest], List):-
    next(Tail,Rest, List).

an example [1,0,0,1,1,1,0] the output should be [0,1,0,1,1,1,0] ; [1,0,0,0,1,1,1]; [1,0,0,1,0,1,1] ; [1,0,0,1,1,0,1].

[1,0,0,1,1,1,0] -> [0,1,0,1,1,1,0]

[1,0,0,1,1,1,0] -> [1,0,0,0,1,1,1]

[1,0,0,1,1,1,0] -> [1,0,0,1,0,1,1]

[1,0,0,1,1,1,0] -> [1,0,0,1,1,0,1]

So how I've understood this is, I loop through removing the head each time by conserving this in Rest so I can append it back on after.

Am I approaching this wrong?

Answer 1

The problem has two pieces: (1) the location of a 1, (2) the location of the first 0 after finding the 1 so that the 1 can be placed in its new position. The Prolog solution will reflect this. Your initial attempt tries to handle everything in a single predicate, which I believe makes the task a little more difficult.

The base case is easy. It represents the smallest valid move.

move([1,0], [0,1]).

Then the recursive cases. These enforce at least 3 positions in the list since the trivial case of 2 positions is already handled by the base case, and it establishes mutual exclusion in the rules to avoid redundant solutions.

% If we're at a 0 (space), keep going
move([0,X1,X2|T], [0|R]) :-
    move([X1,X2|T], R).

% If we see a 1, we can move it, or we can leave it alone and move on
move([1,X1,X2|T], [0|R]) :-
    place([X1,X2|T], R).
move([1,X1,X2|T], [1|R]) :-
    move([X1,X2|T], R).

% Place the 1 at the first located 0 (space)
place([0|T], [1|T]).
place([1|T], [1|R]) :-
    place(T, R).

So to determine valid next positions from a starting position:

| ?-  move([1,0,0,1,1,1,0],R).

R = [0,1,0,1,1,1,0] ? a

R = [1,0,0,0,1,1,1]

R = [1,0,0,1,0,1,1]

R = [1,0,0,1,1,0,1]

(1 ms) no
| ?-

You can also determine what starting positions would lead to a particular next position:

| ?- move(S, [1,0,0,1,0,1,1]).

S = [1,0,0,1,1,0,1] ? a

S = [1,0,0,1,1,1,0]

S = [1,0,1,0,0,1,1]

no

---

This can also be done using a DCG:

move([0, 1]) --> [1, 0].
move([0|R]) --> see(0), move(R).
move([0|R]) --> see(1), place(R).
move([1|R]) --> see(1), move(R).

see(N), [X1, X2] --> [N, X1, X2].

place([1|T]) --> [0], seq(T).
place([1|R]) --> [1], place(R).

seq([]) --> [].
seq([X|Xs]) --> [X], seq(Xs).

| ?- phrase(move(R), [1,0,0,1,1,1,0]).

R = [0,1,0,1,1,1,0] ? a

R = [1,0,0,0,1,1,1]

R = [1,0,0,1,0,1,1]

R = [1,0,0,1,1,0,1]

no
| ?- phrase(move([1,0,0,1,0,1,1]), S).

S = [1,0,0,1,1,0,1] ? a

S = [1,0,0,1,1,1,0]

S = [1,0,1,0,0,1,1]

no

Answer 2

Thank you for all the answers, this is how I did it:

flip_first_zero([0|L],[1|L]):-!.
flip_first_zero([X|L],[X|L1]):-
    flip_first_zero(L,L1).

next([1|L],[0|L1]):-
    flip_first_zero(L,L1).
next([X|L],[X|L1]):-
    next(L,L1).

Answer 3

One logical way to approach this: find what comes before a 1, then what comes after a 1 and before a 0, and a rest. Then, you need to swap the 1 and 0 so that you have Before 1, 0, after 1 before 0, 1, after 0.

Start small. First, to just split the list whenever you have a 1, so that you have Before and After, you can use append/3 like this, using the list from your example:

?- append(Before, [1|After], [1,0,0,1,1,1,0]).
Before = [],
After = [0, 0, 1, 1, 1, 0] ;
Before = [1, 0, 0],
After = [1, 1, 0] ;
Before = [1, 0, 0, 1],
After = [1, 0] ;
Before = [1, 0, 0, 1, 1],
After = [0] ;
false.

You already get the 4 solutions you expect. Now you need to look inside After to see where to put the 1 -- well, you need to put it right after the first 0. So let's split After on a 0, but just once:

?- append(Before, [1|After], [1,0,0,1,1,1,0]),
   once( append(Before0, [0|After0], After) ). 
Before = Before0, Before0 = [],
After = [0, 0, 1, 1, 1, 0],
After0 = [0, 1, 1, 1, 0] ;
Before = [1, 0, 0],
After = [1, 1, 0],
Before0 = [1, 1],
After0 = [] ;
Before = [1, 0, 0, 1],
After = [1, 0],
Before0 = [1],
After0 = [] ;
Before = [1, 0, 0, 1, 1],
After = [0],
Before0 = After0, After0 = [] ;
false.

Now you have 3 pieces: one before the 1 called Before, one between the 1 and the first 0 called Before0, and a last piece after the first 0 called After0. You just need to put them back together: Before, 0, Before0, 1, After0. You can use the 2-argument append/2 that takes a list of lists in the first argument:

?- append(Before, [1|After], [1,0,0,1,1,1,0]),
   once( append(Before0, [0|After0], After) ),
   append([Before, [0|Before0], [1|After0]], Result).
Result = [0, 1, 0, 1, 1, 1, 0] ;
Result = [1, 0, 0, 0, 1, 1, 1] ;
Result = [1, 0, 0, 1, 0, 1, 1] ;
Result = [1, 0, 0, 1, 1, 0, 1] ;
false.

(I left only the Result bindings to save space.)

I think you are done at this point.