prolog - 使用 CLP 解决 PR​​OLOG 中的 Instant Insanity

Question

This is the game

我已经成功地生成了随机混合的 4 种颜色和 4 个立方体的问题，并遵循链接中建议的配色方案。

因此，目标是使用 clpfd 生成问题的可能解决方案。主要原则是基本的，所有 4 个立方体的相同面必须不同。在 4 个列表上使用了 all_different/2，每个列表都包含由 4 个面组成的“塔”的相应侧面。到目前为止，还不错。

现在我必须确保最终结果是有效移动的组合，并且 4 个立方体的形状必须保持不变。我该怎么做？

我也考虑过实现该图算法以获得原始问题的可能解决方案，但我真的不知道如何使用约束逻辑编程实现这一点，甚至不知道这是否可行。

另一方面，我和一个也在做这个项目的 friend 谈过，他只是在实现我谈到的主要原则。够了吗？花了一些时间在页面上玩那个 JavaScript 应用程序，即使立方体相同，解决方案似乎也有面向不同方向的立方体。

Answer 1

您的基本想法是正确的。您确实只需要 all_different/1 约束。这个谜题的有趣之处在于如何表示立方体。我将采取直接的方法，并以与您链接到的页面上给出的几乎完全相同的方式表示立方体。例如，我将表示第一个立方体，其 2D 布局为:

    b
 r  r  r  g
    y

作为基础 Prolog 术语:

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)).

练习:填写 cube_flip/2 中缺少的 3 个子句以获得完整的解决方案。

现在即使没有 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.