/***********************************************************
by Neng-Fa Zhou
***********************************************************/
go =>
    plan(state(s,s,s,s),Path,_),
    write('   '),writeln(state(s,s,s,s)),
    foreach(State in Path, (write('==>'),writeln(State))).


:-table plan(+,-,min).
plan(state(n,n,n,n),Plan,Len):-!,Plan=[],Len=1.
plan(S,Plan,Len):-
    move(S,S1),
    safe(S1),
    plan(S1,Plan1,Len1),
    Plan=[S1|Plan1],
    Len is Len1+1.

move(state(F,F,G,C),NS):-
    NS=state(F1,F1,G,C),
    opposite(F,F1).
move(state(F,W,F,C),NS):-
    NS=state(F1,W,F1,C),
    opposite(F,F1).
move(state(F,W,G,F),NS):-
    NS=state(F1,W,G,F1),
    opposite(F,F1).
move(state(F,W,G,C),NS):-
    NS=state(F1,W,G,C),
    opposite(F,F1).

opposite(n,s).
opposite(s,n).

safe(state(F,_W,F,_C)):-!.
safe(state(F,F,G,F)):-
    opposite(F,G).


