Symbolrätsel Backtracking

B

blade

Bekanntes Mitglied
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
 
A

Andi_CH

Top Contributor
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
 
Zuletzt bearbeitet:
J

Jens81

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

Andi_CH

Top Contributor
blade hat gesagt.:
woher weist du dass das die einzigste möglichkeit ist?
Zum Vergrößern anklicken....

"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 ...
 
Zuletzt bearbeitet:
X

XHelp

Top Contributor
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.
 
A

Andi_CH

Top Contributor
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 ;-)
 
Zuletzt bearbeitet:
A

Andi_CH

Top Contributor
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)

Java: 
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();
		}
	}
}
 
M

Marco13

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

Aktuelle Jobs

Neue Themen


Oben