使用 Prolog CLPFD 的密码谜题
Cryptogram Puzzle with Prolog CLPFD
我最近在 Google Play 应用商店发现了一款名为 Cryptogram 的小游戏。有许多与此类似的应用程序。这个想法是将数字与颜色相匹配，这样所有的方程式听起来都是正确的。
我能够很快地通过第 1-8 题和第 10 题，但事实证明第 9 题对我来说更难。
问题 9
经过一段时间的修改和猜测，我放弃了，决定编写一个解决方案。作为一名本科生，我已经使用 Prolog/Datalog 完成了一些小任务以及一些 Project Euler problems. Previously I had seen the 15 line Sudoku solver that uses Prolog's Constraint Logic Programming over Finite Domains (clpfd) library, and I decided to give it a go myself. I'm using SWI-Prolog.
:- use_module(library(clpfd)).
problem(Colors) :-
Colors = [Pink, Cyan, Yellow, Green, Purple, Red, Brown, White, Lime],
Colors ins 0..9,
all_distinct(Colors),
% The leading digit of a number can't be 0
Pink #\= 0,
Red #\= 0,
White #\= 0,
Green #\= 0,
Lime #\= 0,
Cyan #\= 0,
% I originally tried to write a predicate generalizing numbers and a list of digits
% but got in way over my head with CLPFD.
Number1_1 #= (Pink * 1000) + (Cyan * 100) + (Pink * 10) + Yellow,
Number1_2 #= (Green * 10) + Purple,
Number1_3 #= (Cyan * 100) + (Red * 10) + Purple,
Number2_1 #= (Red * 1000) + (Brown * 100) + (White * 10) + Red,
Number2_2 #= (Lime * 10) + Yellow,
Number2_3 #= (Red * 1000) + (Lime * 100) + (Purple * 10) + Pink,
Number3_1 #= (White * 1000) + (Purple * 100) + (Cyan * 10) + White,
Number3_2 #= (Green * 1000) + (Cyan * 100) + (Yellow * 10) + Purple,
Number3_3 #= (Cyan * 1000) + (Red * 100) + (Yellow * 10) + Red,
% I'm not 100% sure whether to use floored or truncated division here.
% I thought the difference would be a float vs integer output,
% but that doesn't make sense with finite domains.
Number1_1 // Number1_2 #= Number1_3,
Number1_1 rem Number1_2 #= 0,
Number2_3 #= Number2_1 + Number2_2,
Number3_3 #= Number3_1 - Number3_2,
Number3_1 #= Number1_1 - Number2_1,
Number3_2 #= Number1_2 * Number2_2,
Number3_3 #= Number1_3 + Number2_3.
当我在 SWI-Prolog 中 运行 这个查询时的输出让我觉得我误解了 CLPFD 中的一个大概念：
?- problem([Pink, Cyan, Yellow, Green, Purple, Red, Brown, White, Lime]).
Pink in 3..9,
_7756#=Pink+10*Purple+1000*Red+100*Lime,
_7810#=1010*Pink+100*Cyan+Yellow,
all_distinct([Pink, Cyan, Yellow, Green, Purple, Red, Brown, White|...]),
Cyan in 1..7,
_7946#=1000*Cyan+10*Yellow+101*Red,
_7994#=100*Cyan+10*Yellow+1000*Green+Purple,
_8048#=10*Cyan+100*Purple+1001*White,
_8096#=100*Cyan+Purple+10*Red,
Yellow in 0..9,
_8162#=Yellow+10*Lime,
Green in 1..7,
_8216#=10*Green+Purple,
Purple in 0..9,
Red in 1..7,
_8294#=1001*Red+100*Brown+10*White,
Brown in 0..9,
White in 2..8,
Lime in 1..9,
_7756 in 1103..7568,
_8096+_7756#=_7946,
_8294+_8162#=_7756,
_8096 in 110..779,
_7810//_8216#=_8096,
_7810 in 3334..9799,
_8048+_8294#=_7810,
_7810 rem _8216#=0,
_8048 in 2313..8778,
_7946+_7994#=_8048,
_7946 in 1213..7678,
_7994 in 1100..7565,
_8216*_8162#=_7994,
_8216 in 12..79,
_8162 in 14..99,
_8294 in 1021..7486.
我希望颜色列表中的每种颜色都绑定到 运行ge 0..9 中的单个不同整数，但事实并非如此。你能帮我找到解决这个问题的办法吗？
编辑
所以我选择了一种任意颜色并开始在 运行ge 中给它分配数字，约束说应该是有效的。我 运行 这个青色绑定到 1 的查询。
?- problem([Pink, 1, Yellow, Green, Purple, Red, Brown, White, Lime]).
false.
这没有意义。前面的 "output" 表示 "Cyan in 1..7"，我认为这意味着 运行ge 中的任何值都是有效的。但是，如果我为青色选择另一个任意值：
?- problem([Pink, 2, Yellow, Green, Purple, Red, Brown, White, Lime]).
Pink = 7,
Yellow = 6,
Green = 3,
Purple = 4,
Red = 1,
Brown = 8,
White = 5,
Lime = 9.
我得到了我想要的答案。虽然破解了Cryptogram，但是我还是不明白为什么Prolog的CLPFD库没有完全独立的找到它
编辑 2
我使用了您的建议来清理代码。我还重新引入了将数字与数字相关联的谓词。此代码块完美运行。
:- use_module(library(clpfd)).
digit_number(0, [], 1).
digit_number(Number, [Digit|Tail], DigitPlace) :-
digit_number(NextNumber, Tail, NextDigitPlace),
DigitPlace #= NextDigitPlace * 10,
PlaceNumber #= Digit * (NextDigitPlace),
Number #= PlaceNumber + NextNumber.
digit_number(Number, ColorList) :-
digit_number(Number, ColorList, _).
problem(Colors) :-
Colors = [Pink, Cyan, Yellow, Green, Purple, Red, Brown, White, Lime],
Colors ins 0..9,
all_distinct(Colors),
digit_number(Number1_1, [Pink, Cyan, Pink, Yellow]),
digit_number(Number1_2, [Green, Purple]),
digit_number(Number1_3, [Cyan, Red, Purple]),
digit_number(Number2_1, [Red, Brown, White, Red]),
digit_number(Number2_2, [Lime, Yellow]),
digit_number(Number2_3, [Red, Lime, Purple, Pink]),
digit_number(Number3_1, [White, Purple, Cyan, White]),
digit_number(Number3_2, [Green, Cyan, Yellow, Purple]),
digit_number(Number3_3, [Cyan, Red, Yellow, Red]),
Number1_1 // Number1_2 #= Number1_3,
Number1_1 rem Number1_2 #= 0,
Number2_1 + Number2_2 #= Number2_3,
Number3_1 - Number3_2 #= Number3_3,
Number1_1 - Number2_1 #= Number3_1,
Number1_2 * Number2_2 #= Number3_2,
Number1_3 + Number2_3 #= Number3_3,
label(Colors).
您的代码有效，只需 添加标签(C) :
?- problem(C), label(C).
C = [7, 2, 6, 3, 4, 1, 8, 5, 9] .
另一个答案向您展示了一种获得所需结果的方法，但我想回答您的一些问题。
I still don't understand why Prolog's CLPFD library didn't find it completely independently.
Prolog 或多或少是一种声明性编程语言，但是（虽然我们喜欢假装，出于宣传的原因）你不能只写下任何逻辑上等同于你的问题的东西并期望它被正确执行并且有效率的。特别是，不同目标的执行顺序非常重要，即使它在逻辑上应该没有区别。对于算术尤其如此。考虑：
?- between(1, 99999999, N), N > 99999998.
N = 99999999. % correct but slooooow
?- N > 99999998, between(1, 99999999, N).
ERROR: >/2: Arguments are not sufficiently instantiated
对 CLP(FD) 做同样的事情会更好：
?- N in 1..99999999, N #> 99999998.
N = 99999999. % correct and fast!
?- N #> 99999998, N in 1..99999999.
N = 99999999. % also correct, also fast!
CLP(FD) 允许您编写更正确、更具声明性并且通常比其他解决方案更高效的程序，除非您手动优化它们。
为了实现这一点，与普通 Prolog 不同，CLP(FD) 将约束集合与实际搜索解决方案分开。随着您的程序运行并创建约束，CLP(FD) 将进行一些简化，例如在您的示例中它自己确定 Cyan in 1..7 ，或者在我上面的示例中它可以立即找到唯一的解决方案。但总的来说，这些简化并不能完全解决问题。
其中一个原因很简单，就是性能：搜索速度可能很慢。如果已知更多约束，它会更快，因为对已经约束变量的新约束只能使搜索 space 变小，但永远不会变大！将其推迟到实际需要具体答案时才有意义。
因此，要真正获得具体的结果，您需要调用系统枚举解决方案的 labeling 谓词。在SWI-Prolog中，简单的是indomain/1和label/1；一般的是 labeling/2。后一个甚至可以让您影响搜索 space 探索策略，如果您对问题领域有一定了解，这会很有用。
The previous "output" says "Cyan in 1..7", which I thought meant that any value in that range is valid.
不完全：这意味着如果 Cyan 有一个有效的解决方案，那么它在 1 到 7 的范围内。它没有给出保证该范围内的所有值都是解决方案。例如：
?- X in 1..5, Y in 1..5, X #< Y.
X in 1..4,
X#=<Y+ -1,
Y in 2..5.
3 在 1..4 范围内，而 3 在 2..5 范围内，因此纯粹基于此我们可能期望 X = 3 和 Y = 3 的解决方案.但由于额外的限制，这是不可能的。只有标记才能真正为您提供有保证的答案，并且只有在您标记查询中的所有变量时才可以。
另请参阅此处的非常好的答案：
编辑：
% I'm not 100% sure whether to use floored or truncated division here.
% I thought the difference would be a float vs integer output,
% but that doesn't make sense with finite domains.
Number1_1 // Number1_2 #= Number1_3,
事实上小数除法在这里没有意义，但 Prolog 会告诉你：
?- X in 1..5, Y in 1..5, Z #= X // Y.
X in 1..5,
X//Y#=Z,
Y in 1..5,
Z in 0..5.
?- X in 1..5, Y in 1..5, Z #= X / Y.
ERROR: Domain error: `clpfd_expression' expected, found `_G6388/_G6412'
我最近在 Google Play 应用商店发现了一款名为 Cryptogram 的小游戏。有许多与此类似的应用程序。这个想法是将数字与颜色相匹配，这样所有的方程式听起来都是正确的。
我能够很快地通过第 1-8 题和第 10 题，但事实证明第 9 题对我来说更难。
经过一段时间的修改和猜测，我放弃了，决定编写一个解决方案。作为一名本科生，我已经使用 Prolog/Datalog 完成了一些小任务以及一些 Project Euler problems. Previously I had seen the 15 line Sudoku solver that uses Prolog's Constraint Logic Programming over Finite Domains (clpfd) library, and I decided to give it a go myself. I'm using SWI-Prolog.
:- use_module(library(clpfd)).
problem(Colors) :-
Colors = [Pink, Cyan, Yellow, Green, Purple, Red, Brown, White, Lime],
Colors ins 0..9,
all_distinct(Colors),
% The leading digit of a number can't be 0
Pink #\= 0,
Red #\= 0,
White #\= 0,
Green #\= 0,
Lime #\= 0,
Cyan #\= 0,
% I originally tried to write a predicate generalizing numbers and a list of digits
% but got in way over my head with CLPFD.
Number1_1 #= (Pink * 1000) + (Cyan * 100) + (Pink * 10) + Yellow,
Number1_2 #= (Green * 10) + Purple,
Number1_3 #= (Cyan * 100) + (Red * 10) + Purple,
Number2_1 #= (Red * 1000) + (Brown * 100) + (White * 10) + Red,
Number2_2 #= (Lime * 10) + Yellow,
Number2_3 #= (Red * 1000) + (Lime * 100) + (Purple * 10) + Pink,
Number3_1 #= (White * 1000) + (Purple * 100) + (Cyan * 10) + White,
Number3_2 #= (Green * 1000) + (Cyan * 100) + (Yellow * 10) + Purple,
Number3_3 #= (Cyan * 1000) + (Red * 100) + (Yellow * 10) + Red,
% I'm not 100% sure whether to use floored or truncated division here.
% I thought the difference would be a float vs integer output,
% but that doesn't make sense with finite domains.
Number1_1 // Number1_2 #= Number1_3,
Number1_1 rem Number1_2 #= 0,
Number2_3 #= Number2_1 + Number2_2,
Number3_3 #= Number3_1 - Number3_2,
Number3_1 #= Number1_1 - Number2_1,
Number3_2 #= Number1_2 * Number2_2,
Number3_3 #= Number1_3 + Number2_3.
当我在 SWI-Prolog 中 运行 这个查询时的输出让我觉得我误解了 CLPFD 中的一个大概念：
?- problem([Pink, Cyan, Yellow, Green, Purple, Red, Brown, White, Lime]).
Pink in 3..9,
_7756#=Pink+10*Purple+1000*Red+100*Lime,
_7810#=1010*Pink+100*Cyan+Yellow,
all_distinct([Pink, Cyan, Yellow, Green, Purple, Red, Brown, White|...]),
Cyan in 1..7,
_7946#=1000*Cyan+10*Yellow+101*Red,
_7994#=100*Cyan+10*Yellow+1000*Green+Purple,
_8048#=10*Cyan+100*Purple+1001*White,
_8096#=100*Cyan+Purple+10*Red,
Yellow in 0..9,
_8162#=Yellow+10*Lime,
Green in 1..7,
_8216#=10*Green+Purple,
Purple in 0..9,
Red in 1..7,
_8294#=1001*Red+100*Brown+10*White,
Brown in 0..9,
White in 2..8,
Lime in 1..9,
_7756 in 1103..7568,
_8096+_7756#=_7946,
_8294+_8162#=_7756,
_8096 in 110..779,
_7810//_8216#=_8096,
_7810 in 3334..9799,
_8048+_8294#=_7810,
_7810 rem _8216#=0,
_8048 in 2313..8778,
_7946+_7994#=_8048,
_7946 in 1213..7678,
_7994 in 1100..7565,
_8216*_8162#=_7994,
_8216 in 12..79,
_8162 in 14..99,
_8294 in 1021..7486.
我希望颜色列表中的每种颜色都绑定到 运行ge 0..9 中的单个不同整数，但事实并非如此。你能帮我找到解决这个问题的办法吗？
编辑
所以我选择了一种任意颜色并开始在 运行ge 中给它分配数字，约束说应该是有效的。我 运行 这个青色绑定到 1 的查询。
?- problem([Pink, 1, Yellow, Green, Purple, Red, Brown, White, Lime]).
false.
这没有意义。前面的 "output" 表示 "Cyan in 1..7"，我认为这意味着 运行ge 中的任何值都是有效的。但是，如果我为青色选择另一个任意值：
?- problem([Pink, 2, Yellow, Green, Purple, Red, Brown, White, Lime]).
Pink = 7,
Yellow = 6,
Green = 3,
Purple = 4,
Red = 1,
Brown = 8,
White = 5,
Lime = 9.
我得到了我想要的答案。虽然破解了Cryptogram，但是我还是不明白为什么Prolog的CLPFD库没有完全独立的找到它
编辑 2
我使用了您的建议来清理代码。我还重新引入了将数字与数字相关联的谓词。此代码块完美运行。
:- use_module(library(clpfd)).
digit_number(0, [], 1).
digit_number(Number, [Digit|Tail], DigitPlace) :-
digit_number(NextNumber, Tail, NextDigitPlace),
DigitPlace #= NextDigitPlace * 10,
PlaceNumber #= Digit * (NextDigitPlace),
Number #= PlaceNumber + NextNumber.
digit_number(Number, ColorList) :-
digit_number(Number, ColorList, _).
problem(Colors) :-
Colors = [Pink, Cyan, Yellow, Green, Purple, Red, Brown, White, Lime],
Colors ins 0..9,
all_distinct(Colors),
digit_number(Number1_1, [Pink, Cyan, Pink, Yellow]),
digit_number(Number1_2, [Green, Purple]),
digit_number(Number1_3, [Cyan, Red, Purple]),
digit_number(Number2_1, [Red, Brown, White, Red]),
digit_number(Number2_2, [Lime, Yellow]),
digit_number(Number2_3, [Red, Lime, Purple, Pink]),
digit_number(Number3_1, [White, Purple, Cyan, White]),
digit_number(Number3_2, [Green, Cyan, Yellow, Purple]),
digit_number(Number3_3, [Cyan, Red, Yellow, Red]),
Number1_1 // Number1_2 #= Number1_3,
Number1_1 rem Number1_2 #= 0,
Number2_1 + Number2_2 #= Number2_3,
Number3_1 - Number3_2 #= Number3_3,
Number1_1 - Number2_1 #= Number3_1,
Number1_2 * Number2_2 #= Number3_2,
Number1_3 + Number2_3 #= Number3_3,
label(Colors).
您的代码有效，只需 添加标签(C) :
?- problem(C), label(C).
C = [7, 2, 6, 3, 4, 1, 8, 5, 9] .
另一个答案向您展示了一种获得所需结果的方法，但我想回答您的一些问题。
I still don't understand why Prolog's CLPFD library didn't find it completely independently.
Prolog 或多或少是一种声明性编程语言，但是（虽然我们喜欢假装，出于宣传的原因）你不能只写下任何逻辑上等同于你的问题的东西并期望它被正确执行并且有效率的。特别是，不同目标的执行顺序非常重要，即使它在逻辑上应该没有区别。对于算术尤其如此。考虑：
?- between(1, 99999999, N), N > 99999998.
N = 99999999. % correct but slooooow
?- N > 99999998, between(1, 99999999, N).
ERROR: >/2: Arguments are not sufficiently instantiated
对 CLP(FD) 做同样的事情会更好：
?- N in 1..99999999, N #> 99999998.
N = 99999999. % correct and fast!
?- N #> 99999998, N in 1..99999999.
N = 99999999. % also correct, also fast!
CLP(FD) 允许您编写更正确、更具声明性并且通常比其他解决方案更高效的程序，除非您手动优化它们。
为了实现这一点，与普通 Prolog 不同，CLP(FD) 将约束集合与实际搜索解决方案分开。随着您的程序运行并创建约束，CLP(FD) 将进行一些简化，例如在您的示例中它自己确定 Cyan in 1..7 ，或者在我上面的示例中它可以立即找到唯一的解决方案。但总的来说，这些简化并不能完全解决问题。
其中一个原因很简单，就是性能：搜索速度可能很慢。如果已知更多约束，它会更快，因为对已经约束变量的新约束只能使搜索 space 变小，但永远不会变大！将其推迟到实际需要具体答案时才有意义。
因此，要真正获得具体的结果，您需要调用系统枚举解决方案的 labeling 谓词。在SWI-Prolog中，简单的是indomain/1和label/1；一般的是 labeling/2。后一个甚至可以让您影响搜索 space 探索策略，如果您对问题领域有一定了解，这会很有用。
The previous "output" says "Cyan in 1..7", which I thought meant that any value in that range is valid.
不完全：这意味着如果 Cyan 有一个有效的解决方案，那么它在 1 到 7 的范围内。它没有给出保证该范围内的所有值都是解决方案。例如：
?- X in 1..5, Y in 1..5, X #< Y.
X in 1..4,
X#=<Y+ -1,
Y in 2..5.
3 在 1..4 范围内，而 3 在 2..5 范围内，因此纯粹基于此我们可能期望 X = 3 和 Y = 3 的解决方案.但由于额外的限制，这是不可能的。只有标记才能真正为您提供有保证的答案，并且只有在您标记查询中的所有变量时才可以。
另请参阅此处的非常好的答案：
编辑：
% I'm not 100% sure whether to use floored or truncated division here. % I thought the difference would be a float vs integer output, % but that doesn't make sense with finite domains. Number1_1 // Number1_2 #= Number1_3,
事实上小数除法在这里没有意义，但 Prolog 会告诉你：
?- X in 1..5, Y in 1..5, Z #= X // Y.
X in 1..5,
X//Y#=Z,
Y in 1..5,
Z in 0..5.
?- X in 1..5, Y in 1..5, Z #= X / Y.
ERROR: Domain error: `clpfd_expression' expected, found `_G6388/_G6412'