prolog - Smullyan数值机的解决方案

Question

在这里，我建议为Smullyan的数值机器defined here找到一个解决方案。

问题陈述

它们是将数字列表作为输入，然后根据输入模式遵循一些规则将其转换为另一数字列表的机器。
这是上面链接中给出的机器规则，表达得更正式一些。
假设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)

任何不符合任何规则的东西都将被拒绝。
这里有一些例子:

M(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约束)来表达此问题，但是无论如何表达它总是归结为详尽的搜索。

问题

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

Answer 1

这是@Celelibi改进版本(cele_n)的另一个改进。粗略地讲，它通过限制第一个参数的长度得到2的因数，并通过对这两个版本进行预测试而得到2的因数。

cele_n SICStus  2.630s
cele_n SWI     12.258s 39,546,768 inferences
cele_2 SICStus  0.490s
cele_2 SWI      2.665s  9,074,970 inferences

appendh([], [], Xs, Xs).
appendh([_, _ | Ws], [X | Xs], Ys, [X | Zs]) :-
   appendh(Ws, Xs, Ys, Zs).

m([H|A], X) :-
   A = [_|_],                 % New
   m(H, X, A).

m(1, X, A) :-
   append(X, [2], A).
m(3, X, A) :-
   appendh(X, B, B, X),
   m(A, B).
m(4, X, A) :-
   reverse(X, B),
   m(A, B).
m(5, X, A) :-
   X = [_| _],
   m(A, [_|X]).
m(H1, [H2 | B], A) :-
   \+ \+ ( H2 = 1 ; H2 = 2 ),  % New
   m(A, B),
   (  H1 = 6, H2 = 1
   ;  H1 = 7, H2 = 2
   ).

answer3(X) :-
   between(1, 13, N),
   length(X, N),
   reverse(X, A),
   m(X, A).

run :-
   time(findall(X, (answer3(X), write(X), nl), _)).