CC — Clément Chardine

Das „Make 10“-Spiel per Brute Force lösen

Veröffentlicht am 3 Min. Lesezeit Algorithmen · Rätsel

Ein kleines Projekt, das das „Make 10“-Rätsel für jede vierstellige Eingabe (0000–9999) per Brute Force löst: die Regeln, die erlaubten Operationen und die Ergebnisse des Solvers.

Neulich bin ich auf ein YouTube- oder Instagram-Short gestoßen, in dem jemand das Sydney Train Game zu lösen versuchte. Die Idee ist einfach: Man nimmt die vier Ziffern der Waggonnummer und kombiniert sie mit Grundrechenarten, bis 24 herauskommt. Ich habe ein paar Beispiele ausprobiert, aber die meisten waren sehr leicht. Ich wollte also etwas Anspruchsvolleres.

Um es schwieriger zu machen, habe ich das Ziel von 24 auf 10 geändert, das weniger Teiler hat, und mich auf geordnete Operationen beschränkt (die Ziffern dürfen also nicht umsortiert werden). Ich bin sicher nicht der Erste mit dieser Variante, aber mangels besseren Namens nenne ich sie das „Make 10“-Spiel.

Es hat mich eine Weile beschäftigt, aber als Entwickler musste ich natürlich Zeit investieren, um die Lösung zu automatisieren.

Das Ergebnis ist ein Brute-Force-Solver, der alle möglichen Kombinationen von Operationen durchprobiert, um für jede vierstellige Eingabe (von 0000 bis 9999) die 10 zu erreichen. Unten beschreibe ich die Regeln, die erlaubten Operationen und die Ergebnisse des Solvers.

Die Regeln

Das Ziel ist immer 10. Die Eingabe ist eine vierstellige Zeichenfolge. Die Reihenfolge ist fest. Alle vier Ziffern müssen genau einmal verwendet werden.

Die Operationen

Das Rätsel sollte schwierig, aber lösbar bleiben.

Um dem Geist des ursprünglichen Spiels treu zu bleiben, habe ich mich auf Operationen beschränkt, die sich zweifelsfrei von links nach rechts lesen lassen (deshalb wird die Division unüblich mit einem Schrägstrich geschrieben).

Damit es interessant (und lösbar) wird, musste ich den Standardsatz an Operatoren erweitern. Grundrechenarten allein decken den Suchraum nicht ab, aber unendliche Komplexität wollte ich auch nicht zulassen.

Diese Operationen habe ich erlaubt:

Mir ist klar, dass sich manche dieser Operationen (wie Fakultäten oder Logarithmen) in einem einfachen Rechenspiel ein bisschen wie „Schummeln“ anfühlen. Sie fügen aber eine interessante Ebene an Komplexität hinzu und eröffnen mehr Wege zur Zielzahl. Bei meinen ersten Versuchen waren etwa 10 % der Eingaben mit reiner Grundrechnung unlösbar, die zusätzlichen Operationen waren also nötig, um mehr Eingaben abzudecken.

Unten findest du die vollständige, exportierte Liste der Lösungen, die der Solver für jede vierstellige Eingabe gefunden hat. Die interaktive Liste enthält jeweils den einfachsten gefundenen Ausdruck.

10,000 von 10,000 Lösungen

  1. 0000((0! + 0!) · (0! + 0!))?
  2. 0001((0! + 0!) · (0! + 1))?
  3. 00020 + 0 + (0! + 2?)?
  4. 00030 + 0 + (0! + 3)?
  5. 0004(0! + 0!) · (0! + 4)
  6. 0005(0! + 0!) / (0! / 5)
  7. 0006(0! + 0!) · |(0! - 6)|
  8. 00070! + 0! + 0! + 7
  9. 00080! + 0! - (0 - 8)
  10. 00090 + 0! - (0 - 9)
  11. 0010((0! + 0!) · (1 + 0!))?
  12. 0011((0! + 0!) · (1 + 1))?

Die Implementierung

Der Code selbst ist nichts Revolutionäres. Es ist eine Brute-Force-Tiefensuche, die einen Ausdrucksbaum aufbaut. Die größte Herausforderung war nicht die Mathematik, sondern die Grenzen der Maschine.

  1. Terminierung: Verschachtelte Fakultäten und Dreieckszahlen führen sehr schnell zu Überläufen. Ich musste die Suchtiefe aggressiv begrenzen, damit der Code nicht bis zum Wärmetod des Universums läuft.
  2. Formatierung: Ich habe unvernünftig viel Zeit damit verbracht, mit LaTeX zu kämpfen, damit die Ausgabe nicht wie ASCII-Suppe aussieht.
  3. Heuristiken: Ich wollte nicht irgendeine Lösung, sondern die einfachste. Ich habe den Solver so gewichtet, dass er Grundrechenarten (+, -) gegenüber „Massenvernichtungswaffen“ wie dem Dreiecksoperator oder verschachtelten Wurzeln bevorzugt. Die schwere Artillerie holt er nur hervor, wenn es wirklich nicht anders geht (zumindest habe ich das versucht).

Und falls du welche findest: Ich würde mich über einfachere Lösungen freuen, die ohne Modulo (mod) oder den Dreiecksoperator (?) auskommen. Teil sie mit mir, und ich nehme sie auf.

Weitere Experimente