标签: cryptarithmetic-puzzle

我已经在Prolog中制作了一个工作广义的动词算术求解器,但它太慢了.运行简单的表达SEND + MORE = MONE Y只需要8分钟.有人可以帮助我让它跑得更快吗？

/* verbalArithmetic(List,Word1,Word2,Word3) where List is the list of all 
possible letters in the words. The SEND+MORE = MONEY expression would then
be represented as
  verbalArithmetic([S,E,N,D,M,O,R,Y],[S,E,N,D],[M,O,R,E],[M,O,N,E,Y]). */

validDigit(X) :- member(X,[0,1,2,3,4,5,6,7,8,9]).
validStart(X) :- member(X,[1,2,3,4,5,6,7,8,9]).
assign([H|[]]) :- validDigit(H).         
assign([H|Tail]) :- validDigit(H), assign(Tail), fd_all_different([H|Tail]).

findTail(List,H,T) :- append(H,[T],List).

convert([T],T) :- validDigit(T).
convert(List,Num) :- findTail(List,H,T), convert(H,HDigit), Num is (HDigit*10+T).

verbalArithmetic(WordList,[H1|Tail1],[H2|Tail2],Word3) :- 
    validStart(H1), validStart(H2), assign(WordList), 
    convert([H1|Tail1],Num1),convert([H2|Tail2],Num2), convert(Word3,Num3), 
    Sum is Num1+Num2, Num3 = Sum.

我最近在Google Play应用商店中发现了一款​​名为Cryptogram的小游戏.有许多类似于这个的应用程序.我们的想法是将数字与颜色相匹配,以使所有方程听起来都是正确的.

我能够很快地解决问题1-8和问题10,但事实证明问题9对我来说更加困难.

问题9

经过一段时间的修补和猜测,我放弃了,决定编写一个解决方案.我使用Prolog/Datalog作为一些小任务作为本科生以及一些Project Euler问题.以前我见过使用Prolog的Constraint Logic Programming over Finite Domains(clpfd)库的15行数独求解器,我决定自己试一试.我正在使用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 …

也许大多数人都知道Send + More = Money.好吧,我现在正在学习java,其中一个练习是我要解决HES + THE = BEST.

现在,到目前为止,我可以/应该使用if-for-while-do循环,没有别的.虽然我确定有不同的方法来解决它,但这不是我正在经历的练习的重点.我必须能够以最有效的方式使用if-for-while-do循环.

我的问题？我似乎无法想出解决它的有效方法!我想出了这个,它解决了这个难题,但也许是最有效的方法:

public class Verbalarithmetics {

    public static void main (String args[]) {
        // Countint Variables
        int index_h = 0;
        int index_e = 0;
        int index_s = 0;
        int index_t = 0;
        int index_b = 0;

        // Start with h = 1 and increase until the else-if statement is true
        for(int h = 1; h <= 9; h++) { // h = 1, because first Symbol can't be zero
            index_h++;
                // …

我正在计划一个C++程序,它需要3个代表一个密码算术难题的字符串.例如,给定TWO,TWO和FOUR,程序将找到每个字母的数字替换,使得数学表达式

   TWO 
+  TWO 
------
  FOUR

是正确的,假设输入是正确的.解决这个问题的一种方法当然是强制它,用嵌套循环为每个字母分配每个可能的替换,重复尝试总和等,直到最终找到答案.

我的想法是,尽管这是非常低效的,但是在执行一系列推算以限制每个变量的域之后,潜在的循环检查可能是可行的(甚至是必要的)方式.我觉得很难想象,但是首先假设像这样的通用/填充结构是合理的(每个X代表一个不一定不同的数字,每个C都是一个进位数,在这种情况下,会是0还是1)？:

   CCC.....CCC
   XXX.....XXXX
+  XXX.....XXXX
----------------
  CXXX.....XXXX 

考虑到这一点,还有一些更多的计划思路:

- 虽然在这个问题中不会给出前导零,但我可能应该在适当的地方添加足够多的内容,以便将操作数输出/匹配.

- 我想我应该从每个字母的一组可能值0-9开始,可能在"域"表中存储为向量,并在扣除时从中消除值.例如,如果我看到一些像这样排列的字母

 A
 C
--
 A

,我可以说C是零,这消除了其域中的所有其他值.我可以想到相当多的推论,但是将它们推广到各种小情况并将它放入代码中乍一看似乎有些棘手.

- 假设我有一系列很好的推论贯穿整个事情并从域表中引出很多值,我想我仍然只是循环遍历所有事情并希望状态空间足够小以便在合理的情况下生成解决方案多少时间.但感觉必须要有更多的东西! - 可能是一些聪明的方程式设置或沿着那些线.

提示很感激!

嗨,我遇到了这个拼图,这是一个名为Cryptarithms的着名的单词和基于数字的谜题的子集.假设你有一个表达式

发送+更多=金钱

现在有趣的部分是,每个字母表代表0-9的唯一数字.我想编写一个广义求解器,但最后我写了一个粗暴的强制解决方案.任何接受者如何解决它？

我认为可以使用谓词逻辑或集合论来解决.我特别感兴趣的是找到基于C#或Python的解决方案.任何人.？

我被要求使用 Prolog 解决一个密码谜题：

GIVE
* ME 
------
MONEY

以上是谜题，我无法弄清楚问题出在哪里，结果总是返回 false。另外，我不允许使用 SWI-Prolog 中的任何库。

solve(Z) :-
    assign(Z,[0,1,2,3,4,5,6,7,8,9]),
    check(Z).

find( VAL , G,I,V,E  ) :- VAL  is G * 1000 + I * 100 + V * 10 + E.
find2(VALR, M,E      ) :- VALR is M * 10 + E.
find3(VALA, M,O,N,E,Y) :- VALA is M * 10000 + O * 1000 + N * 100 + E * 10 + Y.

check(Z) :- 
    G #>= 1, 
    M #>= 1,
    find( VAL, …

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

我需要编写一个函数solve([A,M,P,D,Y]),它将变量[A,M,P,D,Y]分配给0到9之间的值,使其满足方程AM + PM = DAY.每个变量都分配给一个不同的值,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变量,还是一个足够？

假设您获得了密码算术拼图:

发送+更多=金钱

目标是用数字(0-9)代替字母,这样就可以解决这个问题.

我理解如何以数学方式解决问题,但我不知道如何使用关系数据库来解决这个问题.

如何设计架构来解决这个问题？

如何尝试解决此问题的SQL查询？

编辑: 有一些限制:

1. 在整个过程中,相同的数字应该用于给定的字母.例如,如果您猜测字母E为"5",则E应在其出现的所有位置获得值"5".
2. 不同的字母应该有不同的数字,例如,你不能为E和M指定"4".
3. 没有数字(单词)可能有任何前导零

我正在尝试学习 Prolog。我看了这个脚本：

:- use_module(library(clpfd)).
puzzle([S,E,N,D] + [M,O,R,E] = [M,O,N,E,Y]) :-
   Vars = [S,E,N,D,M,O,R,Y],
   Vars ins 0..9,
   all_different(Vars),
   S*1000 + E*100 + N*10 + D + M*1000 + O*100 + R*10 + E #= M*10000 + O*1000 + N*100 + E*10 + Y,
   M #\= 0,
   S #\= 0.

来源：https : //github.com/Anniepoo/prolog-examples/blob/master/sendmoremoney.pl

我像这样运行它并得到一些输出：

$ swipl -q -s sendmoremoney.pl
?- puzzle(X).
X = ([9, _G2009, _G2012, _G2015]+[1, 0, _G2024, _G2009]=[1, 0, _G2012, _G2009, _G2042]),
_G2009 in 4..7,
all_different([9, _G2009, _G2012, _G2015, …

我是Prolog的新手，非常困惑！我不断收到“ [WMAPDY]的单个变量”警告。我在某处读到，有时警告没有用。我还读到该程序会由于警告而不会编译所有子句？

我正在尝试执行的程序是一种“算术”难题，应该“解决” AM + PM = DAY。

如果有人可以帮助解决此错误，而且单例变量警告始终很重要，我将不胜感激！

史考特

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.