% From Chapter 12 of Gabbrielli & Martini
% Using these due to gnuprolog's built in append and sublist
% myappend(A,B,C) is based on C being the concatenation of A and B.
% myappend([1,2],[3,4],[1,2,3,4]) as query will return yes.
% myappend([1,2,3],[4,5,6],X) as query will return X = [1,2,3,4,5,6].
% myappend(X,Y,[1,2,3,4]) as query has five solutions. 

myappend([], Ys, Ys).
myappend([X|Xs], Ys, [X|Zs]) :- myappend(Xs, Ys, Zs).

% Tests whether the first argument's list appears within (as a sublist)
% of the second argument's list.
% mysublist([1],[2,1,3]) as query is true (in one way).
% mysublist([1],[1,1,1]) as query is true (in three ways).
% mysublist([X,Y,Z],[1,2,3,4,5,6]) has four solutions.
mysublist(Xs, Ys) :- myappend(As, XsBs, Ys), myappend(Xs, Bs, XsBs).

% Has six solutions using sol(X) as query
list_of_27(Ls):-
  Ls = [_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_].

sol(Ls) :-
  list_of_27(Ls),
  mysublist([9,_,_,_,_,_,_,_,_,_,9,_,_,_,_,_,_,_,_,_,9], Ls),
  mysublist([8,_,_,_,_,_,_,_,_,8,_,_,_,_,_,_,_,_,8], Ls),
  mysublist([7,_,_,_,_,_,_,_,7,_,_,_,_,_,_,_,7], Ls),
  mysublist([6,_,_,_,_,_,_,6,_,_,_,_,_,_,6], Ls),
  mysublist([5,_,_,_,_,_,5,_,_,_,_,_,5], Ls),
  mysublist([4,_,_,_,_,4,_,_,_,_,4], Ls),
  mysublist([3,_,_,_,3,_,_,_,3], Ls),
  mysublist([2,_,_,2,_,_,2], Ls),
  mysublist([1,_,1,_,1], Ls).

solcut(Ls) :-
  list_of_27(Ls),
  mysublist([9,_,_,_,_,_,_,_,_,_,9,_,_,_,_,_,_,_,_,_,9], Ls),
  mysublist([8,_,_,_,_,_,_,_,_,8,_,_,_,_,_,_,_,_,8], Ls),
  mysublist([7,_,_,_,_,_,_,_,7,_,_,_,_,_,_,_,7], Ls),
  mysublist([6,_,_,_,_,_,_,6,_,_,_,_,_,_,6], Ls),
  mysublist([5,_,_,_,_,_,5,_,_,_,_,_,5], Ls),
  mysublist([4,_,_,_,_,4,_,_,_,_,4], Ls),
  mysublist([3,_,_,_,3,_,_,_,3], Ls),
  mysublist([2,_,_,2,_,_,2], Ls),
  mysublist([1,_,1,_,1], Ls),!. % this cut (p. 400) prevents multiple solutions