5

我必须编写一个 Prolog 程序来解决一个密码难题。

我需要编写一个函数 solve([A, M, P, D, Y]) 将变量 [A, M, P, D, Y] 分配给从 0 到 9 的值，以便满足等式 AM+PM =天。每个变量被赋予不同的值，A、P、D 不能等于 0。

我开始编写这个函数，但是在运行我的程序时遇到了问题。我将 A、P 和 D 的限制设置为不为零。当我浏览算法时，我意识到 D 必须为 1，所以我在程序的开头定义了它。我为 M 定义了两个不同的变量（M1 和 M2）并将它们设置为彼此相等，因为拼图中的不同 M 应该分配给相同的值。我将位置分配给不同的变量，并根据谜题将它们相加。我解释了任何变量携带进位变量。我的程序编译但函数没有执行。

solve([A, M1, M2, P, D, Y]):- D is 1,
A/=0,
P/=0,
D/=0,
M1 = M2,
select(M1, [0,2,3,4,5,6,7,8,9], R1),
select(M2, R1, R2),
Y is (M1+M2) mod 10,
C1 is (M1+M2) // 10,
select(Y, R2, R3),
select(A, R3, R4),
select(P, R4, R5),
select(D, R5, R6),
A is (A+P+C1) mod 10,
D is (A+P+C1)// 10.

我究竟做错了什么？我的变量定义有问题吗？我需要定义两个不同的 M 变量，还是一个就足够了？

4

4 回答 4

3

这是我为您解决难题的解决方案。我们只是依靠 PROLOG 的回溯。我们首先选择所有变量，然后检查拼图条件。我认为您不需要定义两个女士。

solve([A,M,P,D,Y]):- 
select(A,[0,1,2,3,4,5,6,7,8,9],WA), % W means Without
not(A=0),
select(M,WA,WMA),
select(P,WMA,WMAP),
not(P=0),
select(D,WMAP,WMAPD),
not(D=0),
select(Y,WMAPD,WMAPDY),
DAY is 100*D+10*A+Y,
AM  is 10*A+M,
PM  is 10*P+M,
DAY is AM+PM.
于 2012-12-14T00:59:29.563 回答
1

你写：“我的程序编译但函数没有执行：”

solve([A, M1, M2, P, D, Y]):- D is 1,
    A/=0,

难怪。首先，/=Prolog 中没有运算符。我假设你的意思是\=. 但是A \= B意味着“A不能与B统一”。在你的情况下B是 0，但A它是一个尚未设置的逻辑变量。它可以与任何东西统一。在所有涉及的 logvar 都已实例化之后，您应该只用于\=检查不等式！

所以，A \= 0 失败了。（另一件事是，M1=M2是多余的，您可以M始终使用）。

解决此类难题的通用工具是从缩小域中进行独特选择：

selectM([A|As],S,Z):- select(A,S,S1),selectM(As,S1,Z).
selectM([],Z,Z).

有了它，你的谜题就

solve([A,M,P,D,Y]):-
  selectM([A,P,D],[1,2,3,4,5,6,7,8,9],R),     % R is the remaining domain
  selectM([M,Y],[0|R],_),                     % don't care what remains
  10*(A+P)+M+M =:= 100*D+10*A+Y.

您有一个正确的想法，即在可能的情况下在搜索之前找出分配。使用您的方法，它可以写成

solve([A,M,P,D,Y]):-    
  selectM([M,A],[0,1,2,3,4,5,6,7,8,9],R),
  A =\= 0,
  Y  is (M+M) mod 10,     % AM+PM=DAY
  C1 is (M+M) // 10,
  A  is (A+P+C1) mod 10,
  D  is (A+P+C1) // 10,
  selectM([P,D,Y],R,_),   % ensure all are different
  p =\= 0, D =\= 0.

同样，我们必须A在测试其值之前进行选择。

于 2012-12-16T11:04:55.603 回答
1

除了其他人发布的内容之外，我想提出一个稍微不同的看法。

以下解决方案使用 GNU Prolog 及其CLP(FD)约束。这种约束在所有广泛使用的 Prolog 系统中都可用。

解决方案（Vs）： -
        Vs = [A,M,P,D,Y],
        fd_domain(Vs, 0, 9),
                   A*10 + M
                 + P*10 + M
        #= D*100 + A*10 + Y,
        fd_all_different(Vs),
        一个#\= 0，
        P #\= 0,
        D #\= 0。

我现在强调在这种情况下使用 CLP(FD) 约束的几个关键优势。

首先，很明显，我们可以在具有这些约束的情况下以极其直接的方式对所有需求进行建模。该程序实际上是您的任务到内置关系的几乎逐字翻译：

  • 我需要编写一个函数solve([A, M, P, D, Y])

    我使用solution/1了命令而不是命令solve/1，因为谓词在所有方向上都有意义，包括所有变量已经绑定到具体整数的特定实例。在这种情况下，我们可以使用谓词来验证解决方案。在难题已经完全解决的情况下，称其为“解决”是没有意义的。此外，我们可以使用谓词来完成部分实例化的解决方案。在 Prolog 中，避免谓词名称的必要性是一种很好的做法。

  • 它将变量 [A, M, P, D, Y] 分配给从 0 到 9 的值

    这是通过fd_domain(Vs, 0, 9).

  • 从而满足等式AM+PM=DAY。

    因此方程为A*10 + M + P*10 + M #= D*100 + A*10 + Y。

  • 每个变量都被赋予不同的值

    这由内置约束表示fd_all_different/1。

  • 并且 A、P 和 D 不能等于 0。

    这是通过A #\= 0等说明的。

其次，我们可以使用最通用的查询来研究约束传播的影响：

| ？- 解决方案（[）。

VS = [_#3(2..8),_#24(5..8),9,1,_#87(0:2..6)]

或者，换一种说法：

| ?- 解决方案（[A,M,P,D,Y]）。

A = _#3(2..8)
D = 1
M = _#24(5..8)
P = 9
Y = _#87(0:2..6)

这证实了你所说的：在这个难题D中必然是 1。这也显示了超出您发现的其他一些有趣的事情：必然P是 9。此外，非常严格的界限适用于 ，并且 的域也 被显着修剪。MAY

这表明约束传播显着减少了搜索空间。

具体的解决方案是什么样的？这里有一些例子：

| ?- 解决方案（Vs），fd_labeling（Vs）。

VS = [2,5,9,1,0]？;

VS = [2,7,9,1,4]？;

VS = [2,8,9,1,6]？

是的

第三，您可以运行不同的标记选项来尝试各种搜索策略来探索解决方案空间，而无需更改或重新编译程序。

最后，显着减少的搜索空间通常会产生更快的程序。我把它作为一个练习来运行一些基准测试，以显示在这种情况下基于 CLP(FD) 的版本有多快。

有关这个重要的声明范式的更多信息，请参阅。

于 2016-10-01T06:15:40.473 回答
0

我认为您的问题是对 D 的多个“分配”。首先 D 绑定到 1，之后无法更改值（Prolog 使用统一，而不是分配）。然后两者

...
select(D, R5, R6),
...
D is (A+P+C1)// 10.

当 D 不等于 1 时将失败

于 2012-12-14T06:36:28.057 回答