Solve instant frenzy in PROLOG with CLP
I managed to create an issue with 4 colors and 4 cubes randomly mixed and following the color scheme suggested in the link.
So the goal is to generate possible solutions to the problem using clpfd
. The basic principle is basic, the same face should be different for all 4 cubes. Used all_different/2
in 4 lists, each of which contains a corresponding side of a 4-person tower. So far so good.
Now I must assure that the end result is the composition of the actual moves, and the shape of the 4 cubes must remain unchanged. How can i do this?
I also thought about implementing this graph algorithm in order to get possible solutions to the original problem, but I really don't know how or even if this is possible with Constraint Logic programming.
On the other hand, I talked to a friend who is also involved in this project, and he just implements the basic principle that I was talking about. It's enough? Having done some time with this JavaScript application on the page, and although the cubes are the same, the solutions seem to have cubes oriented in different directions.
source to share
Your main idea sounds. You really need limits all_different/1
. The interesting thing about this puzzle is how to represent cubes. I'll take a straightforward approach and represent cubes in much the same way as 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 main Prolog term:
tmb(b,[r,r,r,g],y)
where tmb
stands for "top, middle, bottom" of the cube.
First, 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 associate a cube with its interests:
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 thing now: what does the rotation of the 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 . Complete 3 missing sentences cube_flip/2
for a complete solution.
Description of the 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 above code (which, as I said, does not have the 3 articles I skipped as an exercise for you), we already found 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 match all colors to integers and use all_different/1
(or all_distinct/1
for stronger spread) instead all_dif/1
.
source to share
I tried my luck without using some kind of card list:
:- use_module(library(term/herbrand)).
:- use_module(library(basic/lists)).
solution([C1,C2,C3,C4]) :-
faces([C1,C2,C3,C4], 2, L2), all_dif(L2),
faces([C1,C2,C3,C4], 3, L3), all_dif(L3),
faces([C1,C2,C3,C4], 4, L4), all_dif(L4),
faces([C1,C2,C3,C4], 6, L6), all_dif(L6),
cube(1, C1),
rotate(2, C2),
rotate(3, C3),
rotate(4, C4).
% cube(+Integer, -List)
cube(1, [r,y,r,b,r,g]).
cube(2, [g,b,y,r,g,b]).
cube(3, [b,y,g,r,r,y]).
cube(4, [b,y,r,g,y,g]).
% rotate(+Integer, -List)
rotate(S, [X1,X2,X3,X4,X5,X6]) :- cube(S, [X1,X2,X3,X4,X5,X6]).
rotate(S, [X3,X2,X5,X4,X6,X1]) :- cube(S, [X1,X2,X3,X4,X5,X6]).
rotate(S, [X5,X2,X6,X4,X1,X3]) :- cube(S, [X1,X2,X3,X4,X5,X6]).
rotate(S, [X6,X2,X1,X4,X3,X5]) :- cube(S, [X1,X2,X3,X4,X5,X6]).
rotate(S, [X6,X1,X4,X5,X3,X2]) :- cube(S, [X1,X2,X3,X4,X5,X6]).
rotate(S, [X4,X1,X3,X5,X2,X6]) :- cube(S, [X1,X2,X3,X4,X5,X6]).
rotate(S, [X3,X1,X2,X5,X6,X4]) :- cube(S, [X1,X2,X3,X4,X5,X6]).
rotate(S, [X2,X1,X6,X5,X4,X3]) :- cube(S, [X1,X2,X3,X4,X5,X6]).
rotate(S, [X2,X6,X5,X3,X4,X1]) :- cube(S, [X1,X2,X3,X4,X5,X6]).
rotate(S, [X5,X6,X4,X3,X1,X2]) :- cube(S, [X1,X2,X3,X4,X5,X6]).
rotate(S, [X4,X6,X1,X3,X2,X5]) :- cube(S, [X1,X2,X3,X4,X5,X6]).
rotate(S, [X1,X6,X2,X3,X5,X4]) :- cube(S, [X1,X2,X3,X4,X5,X6]).
rotate(S, [X5,X4,X3,X2,X1,X6]) :- cube(S, [X1,X2,X3,X4,X5,X6]).
rotate(S, [X3,X4,X1,X2,X6,X5]) :- cube(S, [X1,X2,X3,X4,X5,X6]).
rotate(S, [X1,X4,X6,X2,X5,X3]) :- cube(S, [X1,X2,X3,X4,X5,X6]).
rotate(S, [X6,X4,X5,X2,X3,X1]) :- cube(S, [X1,X2,X3,X4,X5,X6]).
rotate(S, [X6,X5,X2,X1,X3,X4]) :- cube(S, [X1,X2,X3,X4,X5,X6]).
rotate(S, [X2,X5,X3,X1,X4,X6]) :- cube(S, [X1,X2,X3,X4,X5,X6]).
rotate(S, [X3,X5,X4,X1,X6,X2]) :- cube(S, [X1,X2,X3,X4,X5,X6]).
rotate(S, [X4,X5,X6,X1,X2,X3]) :- cube(S, [X1,X2,X3,X4,X5,X6]).
rotate(S, [X2,X3,X1,X6,X4,X5]) :- cube(S, [X1,X2,X3,X4,X5,X6]).
rotate(S, [X1,X3,X4,X6,X5,X2]) :- cube(S, [X1,X2,X3,X4,X5,X6]).
rotate(S, [X4,X3,X5,X6,X2,X1]) :- cube(S, [X1,X2,X3,X4,X5,X6]).
rotate(S, [X5,X3,X2,X6,X1,X4]) :- cube(S, [X1,X2,X3,X4,X5,X6]).
% faces(+List, +Integer, -List)
faces([], _, []).
faces([C|L], N, [F|R]) :-
nth1(N, C, F),
faces(L, N, R).
% all_dif(+List)
all_dif([]).
all_dif([X|Y]) :-
all_dif(Y, X),
all_dif(Y).
% all_dif(+List, +Var)
all_dif([], _).
all_dif([X|Y], Z) :-
dif(X, Z),
all_dif(Y, Z).
Like instant madness here , I get a unique solution:
Jekejeke Prolog 3, Runtime Library 1.3.8 (May 23, 2019) ?- solution(L). L = [[r,y,r,b,r,g],[g,b,y,r,g,b],[y,g,b,y,r,r],[b,r,g,g,y,y]] ; No
source to share