I've managed to generate the problem with 4 colours and 4 cubes randomly mixed and following the colour scheme suggested in the link.
So, the goal is to generate the possible solutions to the problem using clpfd. The main principle is basic, the same face for all 4 cubes must be different. Used all_different/2 on 4 lists, each of them containing the respective side of the "tower" composed by 4 faces. So far, so good.
Now I must assure that the final result is a composition of valid moves and the shape of the 4 cubes must remain unchanged. How can I do so?
I've also thought about implementing that graph algorithm to get possible solutions for the original problem but I don't really know how or even if that is possible using Constraint Logic Programming.
On the other hand, talked with a friend who's also doing this project and he is simply implementing the main principle I talked about. Is that enough? Spent some time playing around with that JavaScript app on the page and even though the cubes are the same, solutions seem to have cubes oriented on different directions.
Your basic idea is sound. You indeed only need all_different/1 constraints. The interesting thing about this puzzle is how to represent the cubes. I shall take a straight-forward approach and represent the cubes in almost exactly the same way as given on the page you link to. For example, I will represent the first cube, whose 2D-layout is:
b
r r r g
y
as the ground Prolog term:
tmb(b,[r,r,r,g],y)
where tmb stands for "top, middle, bottom" of the cube.
Initially, we are given the following 4 cubes:
cube(tmb(b,[r,r,r,g],y)).
cube(tmb(r,[g,y,g,b],b)).
cube(tmb(r,[b,g,r,y],y)).
cube(tmb(g,[b,r,y,g],y)).
The following predicates relate a cube to its sides of interest:
side_cube(top, tmb(Top,_,_), Top).
side_cube(front, tmb(_,[_,Front|_],_), Front).
side_cube(bottom, tmb(_,_,Bottom), Bottom).
side_cube(back, tmb(_,[_,_,_,Back],_), Back).
The main point is now: What does a rotation of a cube look like?
cube_rotation(Cube0, Cube) :-
cube_flip(Cube0, Cube1),
cube_rotation_(Cube1, Cube).
cube_rotation_(tmb(Top,[A,B,C,D],Bottom), tmb(Top,[E,F,G,H],Bottom)) :-
append(_, [E,F,G,H|_], [A,B,C,D,A,B,C]).
cube_flip(Cube, Cube).
cube_flip(tmb(Top,[A,B,C,D],Bottom), tmb(A,[Bottom,B,Top,D],C)).
cube_flip(tmb(Top,[A,B,C,D],Bottom), tmb(B,[A,Bottom,C,Top],D)).
EXERCISE: Fill in the 3 missing clauses of cube_flip/2 for a full solution.
Describing a solution is now easy, even without CLP(FD):
solution(Cs) :-
findall(C, cube(C), Cs0),
same_length(Cs0, Cs),
maplist(side_different(Cs), [top,front,bottom,back]),
maplist(cube_rotation, Cs0, Cs).
side_different(Cubes, Side) :-
maplist(side_cube(Side), Cubes, Colors),
all_dif(Colors).
all_dif([]).
all_dif([D|Ds]) :- maplist(dif(D), Ds), all_dif(Ds).
Even with the code given above (which, as I said, lacks 3 clauses which I omitted as an exercise for you), we already find two solutions:
?- solution(Cubes).
Cubes = [tmb(r,[r,y,r,b],g),tmb(y,[g,b,g,r],b),tmb(b,[y,g,r,y],r),tmb(g,[b,r,y,g],y)] ;
Cubes = [tmb(r,[r,b,r,y],g),tmb(y,[g,r,g,b],b),tmb(b,[r,y,y,g],r),tmb(g,[y,g,b,r],y)] ;
false.
To use CLP(FD), you can simply map all colors to integers, and use all_different/1 (or all_distinct/1, for stronger propagation) instead of all_dif/1.