用CLP解决PROLOG中的即时疯狂问题 [英] Solve Instant Insanity in PROLOG with CLP
问题描述
我已经设法产生了4种颜色和4个立方体随机混合的问题，并遵循链接中建议的配色方案。
所以，目标是使用 clpfd 生成可能的解决方案。主要原则是基本的，所有4个立方体的同一个面必须不同。在4个列表中使用 all_different / 2 ，每个列表包含由4个面组成的塔的相应侧。到目前为止，这么好。
现在我必须确保最终结果是有效移动的组合，并且4个立方体的形状必须保持不变。我怎么能这样做？
我也想过如何实现这个图算法来获得原始问题的可能解决方案，但我并不真正知道如何甚至是如何这是可能的使用约束逻辑编程。
另一方面，与一个也在做这个项目的朋友谈话，他只是实现我所谈论的主要原则。够了吗？花费了一些时间在页面上玩耍JavaScript应用程序，即使立方体相同，解决方案似乎也有以不同方向定向的立方体。
你的基本想法是健全的。你确实只需要 all_different / 1 约束。关于这个难题有趣的是如何表示立方体。我将采取一种直接的方法，并以与链接页面上给出的几乎完全相同的方式表示立方体。例如，我将代表第一个立方体，它的2D布局是：
b
rrrg
y
作为理由Prolog术语：
< code $ t
$ b $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $' tmb 表示立方体的top，middle，bottom。
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））： -
追加（_，[E，F，G，H | _]，[A，B，C，D，A，B，C]）。
cube_flip（立方体，立方体）。
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））。
练习：填写立方体_flip / 2 为一个完整的解决方案。
描述一个解决方案现在很容易，即使没有CLP（FD） b
$ b
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个子句，我省略了我们已经找到了两种解决方案：
？ - 解决方案（立方体）。
Cubes = [tmb（r，[r，y，r，b]，g），tmb（y，[g，b，g，r]，b），tmb（b，[y， 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 。
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.
这篇关于用CLP解决PROLOG中的即时疯狂问题的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
