 <p>Consider the following modifications to your code:</p> <pre><code>mix([], [], []) :- !. mix(P1, P2, Pile) :- takeshirt(P1, 1, Taken1, Rem1), takeshirt(P2, 1, Taken2, Rem2), append(Taken1, Taken2, Pile0), mix(Rem1, Rem2, Pile1), append(Pile0, Pile1, Pile). </code></pre> <p>It seems you need to accumulate the 'shirts' (as list atoms). Here, we are recursively appending them onto the third argument of <code>mix/3</code> (<code>Pile</code>), until the base case (the first clause) is hit when both input lists are empty lists (note that the cut <code>!</code> is necessary here as the binding pattern for the second clause matches the first, so we want to exclude it). The behaviour of the second clause, which takes a shirt from each input list for every step, requires that they must have been of equal length to start with.</p> <p>To test this, I used the following definition of <code>takeshirt/4</code>:</p> <pre><code>takeshirt(Ps, _, [P], Rem) :- select(P, Ps, Rem). </code></pre> <p>Note that the second argument here is unused, as <code>select/3</code> is being used to take a single element (a shirt) from the list, and return the remainder. The absence of a cut (<code>!</code>) after the <code>select</code> allows this predicate to backtrack in selecting all other elements (shirts) from the list. If we now execute your example query with this definition, we can get:</p> <pre><code>1 ?- mix([a,b],[c,d],NewPile). NewPile = [a, c, b, d] ; NewPile = [a, d, b, c] ; NewPile = [b, c, a, d] ; NewPile = [b, d, a, c] ; false. </code></pre> <p>...we can see that <code>mix/3</code> enumerates all possible 'piles' on backtracking by taking a shirt from the first pile (first input list), then a shirt from the second pile (second input list), and so on, until both input lists are empty. If your definition of <code>takeshirt/4</code> doesn't leave choice-points, (is non-backtracking), then you could only get one solution, if any.</p>