$ cat domino.pl
:- use_module(library(lists), [select/3]).

stone(2,2).
stone(4,6).
stone(1,2).
stone(2,4).
stone(6,2).

domino(Chain) :-
	findall(stone(X,Y),stone(X,Y),[FirstStone|RestStones]),
	Chain = [FirstStone|RestChain],
	init_freesides(FirstStone,FreeSides),
	once(chain(FreeSides,RestStones,RestChain)).

init_freesides(stone(A,A),FreeSides) :- !, FreeSides = [A,A,A].
init_freesides(stone(A,B),FreeSides) :- FreeSides = [A,B].

chain(        _,    [],           []).
chain(FreeSides,Stones,[Stone|Chain]) :-
	select(Stone,Stones,RestStones),
	add_stone(Stone,FreeSides,RestStones,Chain).

add_stone(stone(A,A),FreeSides,RestStones,Chain) :- !,
	once(select(A,FreeSides,RestFreeSides)),
	chain([A,A|RestFreeSides],RestStones,Chain).
add_stone(stone(A,B),FreeSides,RestStones,Chain) :-
	(
	  once(select(A,FreeSides,RestFreeSides)),
	  chain([B|RestFreeSides],RestStones,Chain)
	;
	  once(select(B,FreeSides,RestFreeSides)),
	  chain([A|RestFreeSides],RestStones,Chain)
	).