# Symbolrätsel Backtracking



## blade (30. Nov 2010)

Hallo, habe hier eine Java Aufgabe die ich garnicht so wirklich verstehe.
Ich soll ein Programm schreiben das mittels backtracking durch versuchen in Schleifen diese beiden Aufganen löst.
Kann mir das einer  mit der ersten Aufgabe ILL erklären?


    I                 
+ B B               
-----               
I L L              



S E N D
 + M O R E
---------
M O N E Y

Im ersten müssen zur Lösung die Buchstaben folgendermaßen ersetzt werden: I = 1, B = 9 und L = 0:

        1
    + 9 9
    -----
    1 0 0


----------



## Andi_CH (30. Nov 2010)

Du musst nun für jeden Buchstaben der Gleichung eine Ziffer finden, so dass die Rechnung aufgeht

I
+
BB
---
ILL

ist die wohl einzige Möglichkeit I = 1, B = 9, L = 0

Backtracking bezieht sich nun darauf dass du für jeden Buchstaben eine Ziffer annimmst, die Gleichung prüfst und wenn sie nicht stimmt die Annahme änderst.

I=0; B=1; L=2 -> stimmt nicht
I=0; B=1; L=3 -> stimmt nicht
...
I=0; B=1; L=9 -> stimmt nicht
I=0; B=2; L=1 -> stimmt nicht
I=0; B=2; L=3 -> stimmt nicht
... und so weiter


Ich muss dir ehrlich sagen, dass ich das brut force mit Loops umsetzten würde und nicht mal genau weiss, wie ich das mit Backtracking mache, aber ich bin sicher dass genau Backtracking ein Teil der Vorlesung war und du das jetzt einfach auf das Problem hier anwenden sollst.

Vielleicht kannst du mir ja Backtracking erklären dann helfe ich beim umsetzen


----------



## maki (30. Nov 2010)

*verschoben*


----------



## blade (30. Nov 2010)

Andi_CH hat gesagt.:


> Du musst nun für jeden Buchstaben der Gleichung eine Ziffer finden, so dass die Rechnung aufgeht
> 
> I
> +
> ...



woher weist du dass das die einzigste möglichkeit ist?


----------



## Jens81 (30. Nov 2010)

Backtracking ist im Grunde "nur" rekursives durchtesten der Möglichkeiten. Im Falle einer "Nicht-Lösung" einen Schritt zurückgehen.


----------



## Andi_CH (1. Dez 2010)

blade hat gesagt.:


> woher weist du dass das die einzigste möglichkeit ist?



"ist wohl" schliesst nicht aus, dass es andere gibt, aber beweise mir dass es eine weitere gibt ;-)

Ich nehme die Herausforderung an:

Zweistellig + Einstellig:

Kleinster Wert: 11+2 = 13
Grösster Wert: 99+8 = 107

I=0 oder 1!

Die Lösung muss dreistellig sein -> alle Buchstaben unterschiedliche Ziffern - also I=0 ist ausgeschlossen, weil sonst B=L währe. So bleibt für I nur noch die 1

Die einzige Zahl mit dem Muster ILL mit 1 am Anfang ist 100
für B bleibt also nur noch die 9, denn mit jeder tieferen Ziffer lässt sich keine dreistellige Lösung erreichen

I=1, B=9, L=0 QED!

Ich hatte gestern keine Zeit mehr ....

Rekursiv lässt sich das schon programmieren (ob das alles schon stimmt - hm - es ist noch SEHR früh ;-) )

1. Liste aller vorkommenden Buchstaben erstellen
2. Liste aller Ziffern (0..9) erstellen
3. N=1
4. dem n-ten Buchstaben eine Ziffer zuordnen, Ziffer aus der Ziffernliste entfernen
5. letzter Buchstabe?
5.1 Ja: Gleichung überprüfen -> OK oder nOk zurück geben
5.2 Nein: Falls nicht letzter Buchstabe ++N -> 4 Aufrufen
5.3 returnwert?
5.3.1 Ok -> Lösung
5.3.2 nOk -> Ziffer zurücknehmen und neue Zuordnen -> 4 Aufrufen -> Backtracking

Ich versuch mal einen Ansatz zu coden ...


----------



## XHelp (1. Dez 2010)

Bei dem send+mode=money Rätsel ist es, glaube ich, auch wichtig wie man den Zahlenbereich wählt, wenn man in den negativen Bereich geht und den Bereich groß wählt, dann kommen schon ein paar Lösungen mehr raus.


----------



## Andi_CH (1. Dez 2010)

Halt: Den Buchstaben sollen *Ziffern* zugeordnet werden. Ziffern sind nur 0 - 9 und jede Ziffer wird nur einmal vergeben

Also ich hab die Lösung als Rekursion fertig codiert, aber einfach so geb ich sie dir sicher nicht ;-)
Es ist deine Hausaufgabe!

Nur dies:
Lösung gefunden
SEND + MORE = MONEY
7531 + 825 = 8356
Zuordnung = D=1 E=5 S=7 R=2 M=0 N=3 O=8 Y=6 

Das ist die erste gefundene Lösung und ich denke die reicht auch ;-)


----------



## Andi_CH (1. Dez 2010)

Hier das Framework : Konzentriere dich nur auf die Methode pruefe(int pOffset)

Alles andere läuft!

(Für die "Gurus" : JA es gibt Verbesserungsmöglichkeiten, aber was solls! - Der Booleanarray ist unnötig - ich könnte auch die Werte auf -1 prüfen, aber es läuft auch so)


```
import java.util.*;

public class Buchstabengleichung {

	private static HashMap<Character, Integer> mZuordnung = new HashMap<Character, Integer>();
	private static boolean[] mZiffern = new boolean[10];
	public static int mAnzahlBuchstaben = 0;

	//	private static String mSummand1 = "I";
	//	private static String mSummand2 = "BB";
	//	private static String mResultat = "ILL";
	private static String mSummand1 = "SEND";
	private static String mSummand2 = "MORE";
	private static String mResultat = "MONEY";

	public static void init(String pString) throws Exception {
		mZuordnung.clear();
		for(int i=0; i<=9;i++)
			mZiffern[i] = true;
		for(int j=0; j<pString.length(); j++) {
			char key = pString.charAt(j);
			if (!mZuordnung.containsKey(key) )
				mZuordnung.put(key, mAnzahlBuchstaben++);
		}
		if (mAnzahlBuchstaben>9)
			throw new Exception("Es sind zu viele Buchstaben in der Gleichung");
	}

	public static String toString (HashMap<Character, Integer> pMap) {
		String retVal = "";
		for(Character key : mZuordnung.keySet()) {
			retVal += key + "=" + pMap.get(key) + " ";
		}
		return retVal;
	}

	/**
	 * Bestimmt aufgrund der Zuordnung den Wert des Strings
	 * Wirft eine NullPointerException, wenn nicht alle Buchstaben definiert sind
	 * @param  String
	 * @return Wert
	 */
	private static int convert(String pStr) {
		int retVal = 0;
		for(int i=0; i<pStr.length(); i++)
			retVal = retVal*10 + mZuordnung.get(pStr.charAt(i));
		return retVal;
	}

	/**
	 * prüft, ob die Gleichung erfüllt ist
	 * @return true wenn die Gleichung stimmt
	 * @throws Exception 
	 */
	private static boolean gleichungErfuellt () {
		return (convert(mSummand1) + convert(mSummand2) == convert(mResultat));
	}

	private static Character getChar(int pIndex) {
		return (Character)(mZuordnung.keySet().toArray())[pIndex];
	}

	/**
	 * Falls keine Buchstaben mehr zu bearbeiten sind (Offset zeigt das), wird die Gleichung
	 * überprüft und das Resultat der Prüfung zurückgegeben.
	 * 
	 * Der Buchstabe welcher durch pOffset referenziert wird, wird nach und nach auf jede Ziffer
	 * gesetzt, die noch nicht benutzt ist.
	 * 
	 * Für jeden Wert wird pruefe für den nächsten Buchstaben (erhöhter Offset) rekursiv aufgerufen
	 * 
	 * Wenn der Aufruf meldet, dass eine Lösung gefunden wurde: return true;
	 * 
	 * Falls keine Lösung gefunden wurde, Buchstaben auf nächste Ziffer setzen und Benutzungsflags
	 * aktualisieren. 
	 * 
	 * Falls keine der Ziffern zu einer Lösung führte, wird false zurückgegeben
	 *  
	 * @param pOffset -> "Pointer" auf den zu bewertenden Buchstaben
	 * @return true, wenn eine gültige Lösung gefunden wurde
	 */
	private static boolean pruefe(int pOffset) {
		return false;
	}

	public static void main(String[] args) {
		try {
			init(mSummand1 + mSummand2 + mResultat);
			if (pruefe(0)) {
				System.out.println("Lösung gefunden");
				System.out.println(mSummand1 + " + " + mSummand2 + " = " + mResultat);
				System.out.println(convert(mSummand1) + " + " + convert(mSummand2) + " = " + convert(mResultat));
				System.out.println("Zuordnung = " + toString(mZuordnung));
			} else {
				System.out.println("Keine Lösung möglich");
			}
		} catch (Exception e) {
			e.printStackTrace();
		}
	}
}
```


----------



## Marco13 (1. Dez 2010)

Mal ausnahmsweise nur ein paar Google-Stichworte: *cryptarithmetic * *ac3 *und vielleicht noch "*artificial intelligence*" oder *AIMA*


----------

