Generic prolog cryptarithmetic program

Question

I'm trying to write a program to solve general cryptarithmetic puzzles such as AM+PM=DAY, SEND+MORE=MONEY..

The program I've written is:

gsolve([H1,T1],[H2|T2],[H3|T3]):-
    gsolvehelper([H1,T1],[H2|T2],[H3|T3],[0,1,2,3,4,5,6,7,8,9],0).

gsolvehelper([H1,T1],[H2|T2],[H3|T3],D,C):-
    (   var(H1)->select(H1,D,D1);D1=D),
    (   var(H2)->select(H2,D1,D2);D2=D1),
    (   X1 is H1+H2+C),
    (   H3 is mod(X1,10)),
    (   C1 is X1//10),
    gsolvehelper(T1,T2,T3,D2,C1).

The input is of the form:

gsolve([A,M],[P,M],[D,A,Y]).

The head of the first two lists is added to the carry to find the head of the third list and the new carry and so on.

The error I get is:

ERROR: is/2: Type error: `[]' expected, found `[2,_G3922]' ("x" must hold one character)

I cannot figure out what this error is. Can someone please help me with this?

The code you're showing doesn't give that error message. It gives '.'/2: ... [_Gxxxx], not is/2: ...[2,_Gxxxx], which probably means you have a malformed list construct occurring (the actual list predicate is '.', so [H|T] is really '.'(H,T) in Prolog). — lurker
@false You are correct, I should have properly tested this before making the claim: my bad. Since lurker is not getting this error, do you know how this behaves over the various Prologs? — Wouter Beek

Wouter Beek Wouter Beek · Accepted Answer · 2014-10-23T08:04:55

The error you report is due to what is probably a typo: [H1,T1], appearing in several places. Due to this typo H2 gets -- unintentionally -- instantiated to a list, causing problems in the summation statement. The following reproduces the error in SWI7:

?- X is 1 + [1,_] + 3.
ERROR: is/2: Type error: `[]' expected, found `[1,_G11068]' (a list) ("x" must hold one character)

There are other ways in which you can improve your code:

Since you simply pass on the arguments of gsolve/3 you do not need to use the head/tail-notation [H|T] here.
You can simply name your second predicate gsolve/5, as it is already different from gsolve/3 due to its arity.
Several brackets in bsolve/5 are superfluous. Spacing around the if/then operators can be improved as well.
Using the combination of mod/2 and ///2 may introduce problems since the rounding of ///2 (i.e., towards zero, typically at least...) is not consistent with mod/2. Use div/2 (rounding towards negative infinity) instead.

Making alterations based upon the above I get:

gsolve(L1, L2, L3):-
  gsolve(L1, L2, L3, [0,1,2,3,4,5,6,7,8,9], 0).

gsolve([H1|T1], [H2|T2], [H3|T3], D, C):-
  (   var(H1)
  ->  select(H1, D, D1)
  ;   D1 = D
  ),
  (   var(H2)
  ->  select(H2, D1, D2)
  ;   D2=D1
  ),
  X1 is H1 + H2 + C,
  H3 is mod(X1, 10),
  C1 is div(X1, 10),
  gsolve(T1, T2, T3, D2, C1).

This does not solve the puzzle yet... However, since it solves the error you mentioned -- and some other things as well -- you should be able to take it on from here.

Generic prolog cryptarithmetic program

1 Answers