import java.util.*;

class Enigme {
    public String []mots;
    public Stack<Character> lesCaracteres;
    public int [] chiffres;
    public Enigme(String []equation) {
	mots = equation;
	lesCaracteres = new Stack<Character>();
	for (int i=0; i<mots.length; i++) {
	    for (int j=0; j<mots[i].length(); j++)
		if (!lesCaracteres.contains(mots[i].charAt(j))) {
		    lesCaracteres.push(mots[i].charAt(j));
		}
	}
	chiffres = new int[26];
	for (int i=0; i<26; i++) chiffres[i] = -1;
    }
    public boolean chiffreDejaAssocie(int n) {
	for (int i=0; i<26; i++)
	    if (chiffres[i]==n) return true;
	return false;
    }
    public String toString() {
	String s = "";
	for (int i=0; i<26; i++) {
	    if (chiffres[i]!=-1) s += (char)('A'+i)+"="+(char)('0'+chiffres[i])+";";
	}
	return s;
    }
    public void afficheSolution() {
	System.out.println("Pour le problème");
	for (int i=0; i<mots.length-2; i++) {
	    System.out.print(mots[i]+'+');
	}
	System.out.print(mots[mots.length-2]+'=');
	System.out.println(mots[mots.length-1]);
	System.out.println("La solution est "+this);
	for (int i=0; i<mots.length-2; i++) {
	    System.out.print(""+convertir(mots[i])+'+');
	}
	System.out.print(""+convertir(mots[mots.length-2])+'=');
	System.out.println(""+convertir(mots[mots.length-1]));
    }
    public boolean plusRienAAssocier() {
	return lesCaracteres.isEmpty();
    }
    public char popCaractereAAssocier() {
	return lesCaracteres.pop();
    }
    public void pushCaractereAAssocier(char c) {
	lesCaracteres.push(c);
	chiffres[c-'A'] = -1;
    }
    public void associer(int chiffre,char c) {
	chiffres[c-'A'] = chiffre;
    }
    public int convertir(String mot) {
	int v = 0;
	for (int i=0; i<mot.length(); i++) v = v*10 + chiffres[mot.charAt(i)-'A'];
	return v;
    }
    public boolean estResolue() {
	int [] valeurs = new int[mots.length];
	for (int i=0; i<valeurs.length-1; i++) {
	    valeurs[i] = convertir(mots[i]);
	    if (valeurs[i]==0) return false;
	}
	valeurs[valeurs.length-1] = convertir(mots[valeurs.length-1]);
	int somme = 0;
	for (int i=0; i<valeurs.length-1; i++) somme += valeurs[i];
	return valeurs[valeurs.length-1] == somme;
    }
}
public class Puzzle {
    static public int count;
    public static void main(String []args) {
	count = 0;
	String [] mots;
	mots = new String[3];
	mots[0] = "CROSS";
	mots[1] = "ROADS";
	mots[2] = "DANGER";
	Enigme e = new Enigme(mots);
	if (rechercheSolution(e)) {
	    e.afficheSolution();
	} else {
	    System.out.println("Y'a pas de solution");
	}
	System.out.println("J'ai testé "+count+" solutions");

	// un autre ?
	count = 0;
	mots = new String[4];
	mots[0] = "VINGT";
	mots[1] = "CINQ";
	mots[2] = "CINQ";
	mots[3] = "TRENTE";
	e = new Enigme(mots);
	if (rechercheSolution(e)) {
	    e.afficheSolution();
	} else {
	    System.out.println("Y'a pas de solution");
	}
	System.out.println("J'ai testé "+count+" solutions");

	// un autre ?
	count = 0;
	mots = new String[3];
	mots[0] = "SEND";
	mots[1] = "MORE";
	mots[2] = "MONEY";
	e = new Enigme(mots);
	if (rechercheSolution(e)) {
	    e.afficheSolution();
	} else {
	    System.out.println("Y'a pas de solution");
	}
	System.out.println("J'ai testé "+count+" solutions");

	// un autre ?
	count = 0;
	mots = new String[6];
	mots[0] = "ZERO";
	mots[1] = "QUATRE";
	mots[2] = "QUATRE";
	mots[3] = "ONZE";
	mots[4] = "ONZE";
	mots[5] = "TRENTE";
	e = new Enigme(mots);
	if (rechercheSolution(e)) {
	    e.afficheSolution();
	} else {
	    System.out.println("Y'a pas de solution");
	}
	System.out.println("J'ai testé "+count+" solutions");
    }
    public static boolean rechercheSolution(Enigme enigme) {
	count++;
	if (enigme.plusRienAAssocier()) {
	    return enigme.estResolue();
	}
	char c = enigme.popCaractereAAssocier();
	for (int chiffre=0; chiffre<10; chiffre++) {
	    if (enigme.chiffreDejaAssocie(chiffre)) continue;
	    enigme.associer(chiffre,c);
	    if (rechercheSolution(enigme)) return true; // on s'arrête à la première
	}
	enigme.pushCaractereAAssocier(c);
	return false;
    }
}