Hallo zusammen! Lust auf ein bisschen Denksport?
Ich möchte einen Algorithmus zur Lösung eines Rätselspiels entwickeln, komme aber auf keine effiziente Herangehensweise. Zunächst ein paar Informationen zum Ablauf des Spiels:
- Es steht von vornherein eine Zahlen-Code fest, den es zu finden gilt
- 4-stelliger Code (z.B. 5237)
- verwendete Zahlen: 1 2 3 4 5 6 7 8 9
- jede Zahl kommt maximal 1x vor
- Man hat maximal 8 Versuche (Die Regel kann erstmal außen vor gelassen werden)
- Ein Versuch besteht daraus, einen Code einzugeben
- selbe Regeln wie oben: 5555 wäre keine gültige Eingabe
- Das System vergleicht die Eingabe mit dem verstecken Code, den es zu inden gilt und meldet einem als Antwort zwei Angaben:
- Anzahl der richtigen Zahlen an richtiger Position (#x grün)
- Anzahl der richtigen Zahlen an falscher Position (#x rot)
- Ziel des Spiels ist es, 4x grün als Ausgabe zu erreichen.
Beispiel:
Verteckter Code = 5237
- Versuch: 1234
Ausgabe: 2 grün / 0 rot (2 und 3 sind richtig UND an richtiger Position) - Versuch: 5678
Ausgabe: 1 grün / 1 rot (5 richtig an richtiger Pos., 7 richtig an falscher Pos.)
[Anmerkung: Jetzt ist z.B. eindeutig, dass die 9 NICHT dabei ist, weil 8 Zahlen abgefragt wurden, unter denen 4 richtig sind!] - Versuch: 2345
Ausgabe: 0 grün / 3 rot (2, 3 und 5 sind richtig aber an der falschen Pos.) - Versuch: 3456
Ausgabe: 0 grün / 2 rot - Versuch: 4567
Ausgabe: 1 grün / 1 rot (5 richtig an falscher Pos., daher rot; 7 richtig an richtiger Pos. - Versuch: 5237
Ausgabe: 4 grün / 0 rot - Rätsel gelöst (alle Zahlen richtig und an richtiger Pos.
Hat jemand eine Idee,
- wie man lediglich durch die Ausgabe „x grün / x rot“ mit möglichst wenig Versuchen (Brute-Force benötigt zu viele) auf den richtigen Code schließen kann?
- welche Abfragen sinnigerweise zuerst durchgeführt werden sollten, um direkt bestimte Zahlen auszuschließen (wie z.B. 1234 und 5678, um die 9 auszuschließen / sicher zu sein, dass die 9 dabei ist)?
- welche Strategien wann ausgeführt werden sollten?
- z.B. wenn 0 / 1, gehe in den Fischen-Im-Dunkeln-Modus, wo jede einzelne Zahl ersetzt wird
- wenn 2 / 1, dann benutze Codes, in denen immer nur eine Zahl ausgetauscht wird
- wie viele Versuche man überhaupt braucht, um im schlimmsten Fall auf eine eindeutige Lösung zu kommen?
Wenn man ganz viel Glück hat und einen Code ausprobiert, der „0 grün / 0 rot“ liefert, kann man natürlich direkt 4 Zahlen auf einmal ausschließen.
Ich habe überlegt eine Art Score zu ermitteln. Wenn z.B. 1234 = 2g/1r ergibt, wird für jede einzelne Zahl der Score um 2 + 1 = 2 erhöht. Scheint aber eine Sackgasse zu sein. Hat ein solcher Score bei der geringen Anzahl an Versuchen überhaupt Aussagekraft? Dann müsste ja jede Zahl gleich oft abgeprüft werden, was wieder auf die Versuche geht.
LG