bzwk(W):-
	write('start situation: [b,z,w,k] on the left'),nl,nl,
	bzwk([b,z,w,k],[],W,[[]]).
	
bzwk([],_,[],_).
	
bzwk(L1,R1,[H|W],S):-
		test(H),
		go(L1,R1,H,L2,R2),
		write('transition of '), write(H),nl,
		write('new situation: '),nl, write(L2), write(' on the left'),nl, write(R2), write(' on the right'),nl,
		prove(L2),
		prove(R2),
		not_previous_situation(R2,S),
		bzwk(L2,R2,W,[R2|S]).
	
go(L1,R1,H,L2,R2):-
		difference_subset(H,L1,L2),
		append1(H,R1,R2).

go(L1,R1,H,L2,R2):-
		difference_subset(H,R1,R2),
		append1(H,L1,L2).

not_previous_situation(_,[]).		
		
not_previous_situation(R2,[H|S]):-
	difference_subset(R2,H,[]),
	!,
	fail.

not_previous_situation(R,[H|S]):-
		not_previous_situation(R,S).

	
prove(S):-
	member1(z,S),
	member1(k,S),
	not_member(b,S),
	write('ziege frisst kohlkopf'),nl,
	!,
	fail.
	
prove(S):-
	member1(z,S),
	member1(w,S),
	not_member(b,S),
	write('wolf frisst ziege'),nl,
	!,
	fail.

prove(S).	

test([b]).

test(L):-
	difference_subset(L,[b,w],[]).

test(L):-
	difference_subset(L,[b,z],[]).

test(L):-
	difference_subset(L,[b,k],[]).

test(_):-
	write('transition not allowed'),nl,
	!,
	fail.
	
difference_subset([],L,L).	
	
difference_subset([H|T],L1,L2):-
	member1(H,L1),
	remove_first(H,L1,L1N),
	difference_subset(T,L1N,L2).	

remove_first(H,L1,L2):-
	remove_first(H,L1,[],L2).

remove_first(H,[],ACC,ACC).	

remove_first(H,[H|L],ACC,L2):-
	!,
	append1(L,ACC,L2).                                                                 

remove_first(H,[E|L],ACC,L2):-
	remove_first(H,L,[E|ACC],L2).
		
not_member(E,[]).
	
not_member(E,[E|M]):-
	!,
	fail.

not_member(E,[_|M]):-
	not_member(E,M).
	
	
member1(E,[E|M]):-
	!.

member1(E,[_|M]):-
	member1(E,M).

	
append1([],B,B).

append1([H|A],B,[H|C]):-
	append1(A,B,C).