Smullyan 数值机的解决方案

在这里我建议找到 Smullyan 数值机的解决方案：此处定义 http://heras-gilsanz.com/manuel/smullyan-machines.html.

问题陈述

它们是接受数字列表作为输入，并根据输入模式遵循一些规则将其转换为另一个数字列表的机器。 以下是上面链接中给出的机器规则，表达得更正式一些。 假设 M 是机器，M(X) 是 X 的变换。 我们定义了一些这样的规则：

M(2X) = X
M(3X) = M(X)2M(X)
M(4X) = reverse(M(X)) // reverse the order of the list.
M(5X) = M(X)M(X)

任何不符合任何规则的内容都会被拒绝。 这里有一些例子：

• 中号(245) = 45
• M(3245) = M(245)2M(245) = 45245
• M(43245) = 反向(M(3245)) = 反向(45245) = 54254
• M(543245) = M(43245)M(43245) = 5425454254

问题是，找到 X 使得：

• M(X) = 2
• M(X) = X
• M(X) = X2X
• M(X) = 反向(X)
• M(X) = 反向(X2X)反向(X2X)

这是第二个例子，它的详尽搜索稍微复杂一些（特别是如果我想要前 10 个或 100 个解决方案）。

M(1X2) = X
M(3X) = M(X)M(X)
M(4X) = reverse(M(X))
M(5X) = truncate(M(X)) // remove the first element of the list truncate(1234) = 234. Only valid if M(X) has at least 2 elements.
M(6X) = 1M(X)
M(7X) = 2M(X)

问题：

• M(X) = XX
• M(X) = X
• M(X) = 反向(X)

（非）解决方案

在 Prolog 中编写求解器非常简单。只是这只是详尽的探索（又名蛮力），并且可能需要一些时间来制定某些规则。

我尝试过，但无法用 CLP(FD) 的逻辑约束来表达这个问题，所以我尝试了 CHR（约束处理规则）来用列表上的约束来表达这个问题（尤其是append约束），但无论我如何表达，它总是归结为详尽的搜索。

Question

知道我可以采取什么方法在合理的时间内解决此类问题吗？ 理想情况下，我希望能够生成比某个界限更短的所有解决方案。

让我们看看你的“稍微复杂一点”的问题。详尽的搜索效果非常好！

以下是与 Серге́й 解决方案的比较，通过考虑共同目标可以显着改进该解决方案：

m([1|A], X) :-
    A = [_|_],
    append(X, [2], A).
m([E | X], Z) :-
    m(X, Y),
    (  E = 3,
       append(Y, Y, Z)
    ;  E = 4,
       reverse(Y, Z)
    ;  E = 5,
       Y = [_ | Z]
    ;  E = 6,
       Z = [1 | Y]
    ;  E = 7,
       Z = [2 | Y]
    ).

供查询time(findall(_, (question3(X), write(X), nl), _)).我使用 B 8.1、SICStus 4.3b8 得到：

Серге́й B tabled   104.542s
Серге́й B          678.394s
false  B           16.013s
false  B tabled    53.007s
Серге́й SICStus    439.210s
false  SICStus      7.990s
Серге́й SWI       1383.678s, 5,363,110,835 inferences
false  SWI         44.743s,   185,136,302 inferences

附加的问题并不难回答。仅 SICStus 具有上述功能m/2 and call_nth/2 https://stackoverflow.com/questions/11364634/count-the-number-of-call-of-a-clause-prolog/11400256#11400256:

| ?- time(call_nth( (
        length(Xs0,N),append(Xs0,Xs0,Ys),m(Xs0,Ys),
          writeq(Ys),nl ), 10)).
[4,3,7,4,3,1,4,3,7,4,3,1,2,4,3,7,4,3,1,4,3,7,4,3,1,2]
[3,4,7,4,3,1,3,4,7,4,3,1,2,3,4,7,4,3,1,3,4,7,4,3,1,2]
[4,3,7,3,4,1,4,3,7,3,4,1,2,4,3,7,3,4,1,4,3,7,3,4,1,2]
[3,4,7,3,4,1,3,4,7,3,4,1,2,3,4,7,3,4,1,3,4,7,3,4,1,2]
[3,5,4,5,3,1,2,2,1,3,5,4,5,3,1,2,3,5,4,5,3,1,2,2,1,3,5,4,5,3,1,2]
[3,5,5,3,4,1,2,1,4,3,5,5,3,4,1,2,3,5,5,3,4,1,2,1,4,3,5,5,3,4,1,2]
[5,4,7,4,3,3,1,2,5,4,7,4,3,3,1,2,5,4,7,4,3,3,1,2,5,4,7,4,3,3,1,2]
[4,7,4,5,3,3,1,2,4,7,4,5,3,3,1,2,4,7,4,5,3,3,1,2,4,7,4,5,3,3,1,2]
[5,4,7,3,4,3,1,2,5,4,7,3,4,3,1,2,5,4,7,3,4,3,1,2,5,4,7,3,4,3,1,2]
[3,5,4,7,4,3,1,_2735,3,5,4,7,4,3,1,2,3,5,4,7,4,3,1,_2735,3,5,4,7,4,3,1,2]
196660ms

| ?- time(call_nth( (
        length(Xs0,N),m(Xs0,Xs0),
          writeq(Xs0),nl ), 10)).
[4,7,4,3,1,4,7,4,3,1,2]
[4,7,3,4,1,4,7,3,4,1,2]
[5,4,7,4,3,1,_2371,5,4,7,4,3,1,2]
[4,7,4,5,3,1,_2371,4,7,4,5,3,1,2]
[5,4,7,3,4,1,_2371,5,4,7,3,4,1,2]
[3,5,4,7,4,1,2,3,5,4,7,4,1,2]
[4,3,7,4,5,1,2,4,3,7,4,5,1,2]
[3,4,7,4,5,1,2,3,4,7,4,5,1,2]
[4,7,5,3,6,4,1,4,7,5,3,6,4,2]
[5,4,7,4,3,6,1,5,4,7,4,3,6,2]
6550ms

| ?- time(call_nth( (
        length(Xs0,N),reverse(Xs0,Ys),m(Xs0,Ys),
          writeq(Ys),nl ), 10)).
[2,1,3,4,7,1,3,4,7]
[2,1,4,3,7,1,4,3,7]
[2,1,3,5,4,7,_2633,1,3,5,4,7]
[2,1,5,4,7,3,2,1,5,4,7,3]
[2,4,6,3,5,7,1,4,6,3,5,7]
[2,6,3,5,4,7,1,6,3,5,4,7]
[2,_2633,1,5,3,4,7,_2633,1,5,3,4,7]
[2,_2633,1,5,4,3,7,_2633,1,5,4,3,7]
[2,1,3,4,4,4,7,1,3,4,4,4,7]
[2,1,3,4,5,6,7,1,3,4,5,6,7]
1500ms