Решите Мгновенное Безумие в PROLOG с CLP
Мне удалось создать проблему с 4 цветами и 4 кубиками, смешанными случайным образом и следуя цветовой схеме, предложенной в ссылке.
Таким образом, цель состоит в том, чтобы сгенерировать возможные решения проблемы, используя clpfd, Основной принцип является базовым, одно и то же лицо для всех 4 кубов должно быть разным. Используемый all_different/2 в 4 списках, каждый из которых содержит соответствующую сторону "башни", состоящей из 4 граней. Все идет нормально.
Теперь я должен заверить, что конечный результат - это состав из правильных ходов, и форма 4 кубов должна остаться неизменной. Как я могу это сделать?
Я также думал о реализации этого алгоритма графа, чтобы получить возможные решения исходной проблемы, но я не знаю, как и даже если это возможно с помощью логического программирования с ограничениями.
С другой стороны, поговорил с другом, который также занимается этим проектом, и он просто реализует основной принцип, о котором я говорил. Этого достаточно? Потратил некоторое время на то, чтобы поиграть с этим приложением JavaScript на странице, и хотя кубы одинаковы, кажется, что решения имеют кубы, ориентированные в разных направлениях.
1 ответ
Ваша основная идея - это звук. Вам действительно нужно только all_different/1 ограничения. Интересная вещь в этой головоломке - как изображать кубики. Я выберу прямой подход и представляю кубы почти точно так же, как указано на странице, на которую вы ссылаетесь. Например, я буду представлять первый куб, 2D-макет которого:
b
r r r g
y
В качестве основного термина Пролог:
tmb(b,[r,r,r,g],y)
где tmb обозначает "верх, середина, низ" куба.
Изначально нам дают следующие 4 кубика:
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)).
Следующие предикаты связывают куб с интересующими его сторонами:
side_cube(top, tmb(Top,_,_), Top).
side_cube(front, tmb(_,[_,Front|_],_), Front).
side_cube(bottom, tmb(_,_,Bottom), Bottom).
side_cube(back, tmb(_,[_,_,_,Back],_), Back).
Теперь главное: как выглядит вращение куба?
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)).
УПРАЖНЕНИЕ: заполните 3 пропущенных пункта cube_flip/2 для полного решения.
Описание решения теперь легко, даже без 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).
Даже с приведенным выше кодом (в котором, как я уже сказал, отсутствуют 3 предложения, которые я пропустил в качестве упражнения для вас), мы уже нашли два решения:
?- 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.
Чтобы использовать CLP(FD), вы можете просто отобразить все цвета на целые числа и использовать all_different/1 (или же all_distinct/1, для более сильного распространения) вместо all_dif/1,
Я попытал счастья, не используя список карт:
:- 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).
Как здесь мгновенное безумие, я получаю уникальное решение:
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