Simple cryptarithmetic puzzle solver in Java, C, and Python

SimpleSolver.java

public class SimpleSolver {
  static int eval(String q) {
    int val = 0;
    java.util.StringTokenizer st = new java.util.StringTokenizer(q, "*/+-", true);
    while (st.hasMoreTokens()) {
      String next = st.nextToken().trim();
      if (next.equals("+")) {
        val += Integer.parseInt(st.nextToken().trim());
      } else if (next.equals("-")) {
        val -= Integer.parseInt(st.nextToken().trim());
      } else if (next.equals("*")) {
        val *= Integer.parseInt(st.nextToken().trim());
      } else if (next.equals("/")) {
        val /= Integer.parseInt(st.nextToken().trim());
      } else {
        val = Integer.parseInt(next);
      }
    }
    return val;
  }
  static String solve(String q) {
    char c = 0;
    for (int i = 0; i < q.length(); ++i) {
      if (Character.isAlphabetic(q.charAt(i))) {
        c = q.charAt(i);
        break;
      }
    }
    if (c == 0) {
      String[] ops = q.split("==");
      int o1 = eval(ops[0]), o2 = eval(ops[1]);
      if (o1 == o2) return q;
      else return "";
    } else {
      char[] dset = new char[10];
      for (int i = 0; i < q.length(); ++i)
        if (Character.isDigit(q.charAt(i)))
          dset[q.charAt(i)-'0'] = 1;
      for (int i = 0; i < 10; ++i) {
        if (dset[i] == 0) {
          String r = solve(q.replaceAll(String.valueOf(c),
              String.valueOf(i)));
          if (!r.isEmpty()) return r;
        }
      }
    }
    return "";
  }
  public static void main(String[] args) {
    String query = "ABCDE * A == EEEEEE";
    System.out.println(solve(query));
  }
}

solver.c

#include <string.h>
#include <stdio.h>
#include <stdlib.h>

// get the value of the next integer out of the string s
// quick and dirty 
int next_int(char ** s) {
  char * q = *s;
  char * end = q+strlen(q);
  while(!isdigit(q[0]) && q < end)
    q++; // advance q to first digit
  char * p = q;
  while(isdigit(p[0]))
    p++; // advance q to character after last digit
  char tmp[p-q+1];
  strncpy(tmp, q, p-q);
  tmp[p-q] = '\0';
  *s = p; // advance s to where p is
  return atoi(tmp);
}

// evaluate the simple expression q
// doesn't handle fancy stuff like precedence
int eval(char * q) {
  int val=0, len=strlen(q);
  char * t = q;
  while(1) {
    if(isdigit(t[0])) {
      val = next_int(&t);
    } else if (t[0]=='+') {
      val += next_int(&t); 
    } else if (t[0]=='-') {
      val -= next_int(&t);
    } else if (t[0]=='*') {
      val *= next_int(&t);
    } else if (t[0]=='/') {
      val /= next_int(&t);
    } else if (t[0]=='\0') {
      break;
    } else {
      ++t;
    }
  }
  return val;
}

// solve the cryptarithmetic puzzle q
char * solve(char * q) {
  // find c, the first unbound letter of q
  char c = 0;
  int i = 0, j = 0, len = strlen(q);
  for (i=0; i<len; ++i) {
    if (isalpha(q[i])) {
      c = q[i];
      break;
    }
  }
  if (c == 0) { // if there are no unbound letters
    // extract op1 and op2 operands
    char * end = q+len;
    char * eq = strstr(q, "==");
    char op1[eq-q+1], op2[end-eq-1];
    strncpy(op1, q, eq-q);
    strncpy(op2, eq+2, end-eq-2);
    op1[eq-q] = '\0';
    op2[end-eq-2] = '\0';
    // evaluate op1 and op2
    int eval1 = eval(op1), eval2 = eval(op2);
    if(eval1 == eval2) { // solved!
      char * r = (char*)malloc(len*sizeof(char));
      strcpy(r, q);
      return r;
    } else {
      return 0;
    }
  } else { // if c is the next unbound letter
    // find unused digits
    char dset[10] = {0,0,0,0,0,0,0,0,0,0};
    for (i=0; i<len; ++i)
      if (isdigit(q[i]))
        dset[q[i]-'0'] = 1;
    for (i=0; i<10; ++i) {                                
      if (dset[i] == 0) { // if this digit i is unused
        // make a new string n with c replaced with i
        char * n = (char*)malloc(len*sizeof(char));
        for (j=0; j<len; ++j) 
          n[j] = (q[j] == c) ? i + '0' : q[j];
        char * r = solve(n);
        free(n);
        if (r) return r;
      }
    }   
  }
  return 0;
}

int main() {
  char * query = "ABCDE * A == EEEEEE";
  char * result = solve(query);
  if(result) puts(result);
  else puts("No solution found.");
  return 0;
}

solver.py

from re import sub

def solve(q):
  try:
    n = (i for i in q if i.isalpha()).next()
  except StopIteration:
    return q if eval(sub(r'(^|[^0-9])0+([1-9]+)', r'\1\2', q)) else False
  else: 
    for i in (str(i) for i in range(10) if str(i) not in q):
      r = solve(q.replace(n,str(i)))
      if r:
        return r
    return False

if __name__ == "__main__":
  query = "ABCDE * A == EEEEEE"
  r = solve(query)
  print r if r else "No solution found."

# Other puzzles to try:
# query = "REASON == IT * IS + THERE"
# query = "MAD * MAN == ASYLUM"
# query = "THREE + THREE + ONE == SEVEN"
# query = "SEND + MORE == MONEY"
# query = "I + BB == ILL"
# query = "WHOSE + TEETH + ARE + AS == SWORDS"
# query = "BILL + WILLIAM + MONICA == CLINTON"
# query = "GREEN + ORANGE == COLORS"
# query = "PACIFIC + PACIFIC + PACIFIC == ATLANTIC"
# query = "CASSATT + RENOIR == PICASSO"
# query = "MANET + MATISSE + MIRO + MONET + RENOIR == ARTISTS"
# query = "COMPLEX + LAPLACE == CALCULUS"

Can you please provide some explanation(algorithm) of the C code

it seems your c algorithm have some bug. plays + well == better must have provided 97426 + 8077 == 105503. instead your algo is providing 17348 + 9277 == 026625 as the output.

import java.util.Scanner;

public class SimpleSolver {
static int eval(String q) {
int val = 0;
java.util.StringTokenizer st = new java.util.StringTokenizer(q, "+", true);
while (st.hasMoreTokens()) {
String next = st.nextToken().trim();
if (next.equals("+")) {
val += Integer.parseInt(st.nextToken().trim());
} else if (next.equals("")) {
val *= Integer.parseInt(st.nextToken().trim());
} else {
val = Integer.parseInt(next);
}
}
return val;
}
static String solve(String q) {
char c = 0;
for (int i = 0; i < q.length(); ++i) {
if (Character.isAlphabetic(q.charAt(i))) {
c = q.charAt(i);
break;
}
}
if (c == 0) {
String[] ops = q.split("=");
int o1 = eval(ops[0]), o2 = eval(ops[1]);
if (o1 == o2)return q;
else return "";
} else {
char[] dset = new char[10];
for (int i = 0; i < q.length(); ++i)
if (Character.isDigit(q.charAt(i)))
dset[q.charAt(i)-'0'] = 1;
for (int i = 0; i < 10; ++i) {
if (dset[i] == 0) {
String r = solve(q.replaceAll(String.valueOf(c),
String.valueOf(i)));
if (!r.isEmpty()) {
String[] p=r.split(" ");
int sw=0;
for(int j=0;j<p.length;j++){
if(p[j].charAt(0)=='0'){
sw=1;
break;
}
}
if(sw==0)return r;
}
}
}
}
return "";
}
public static void main(String[] args) {
Scanner t=new Scanner(System.in);
while(t.hasNext()){
String query =t.nextLine();
System.out.println(solve(query));
}
}
}

no 0 at left