Bulls and Cows (in Japan Hit & Blow) ist ein Rätsel, das sich gut vom Computer lösen lässt. Die Idee ist ganz einfach: „Schreibe alle möglichen Lösungen auf und streiche die, die den Hinweisen widersprechen.“

Die Idee

  1. Erzeuge alle möglichen Lösungen (bei 4 Stellen sind es 5040).
  2. Wähle eine davon und tippe sie.
  3. Prüfe anhand der Treffer und Fast für jede Möglichkeit: „Wenn sie die Lösung wäre, kämen dann dieselben Treffer und Fast heraus?“ Alle, bei denen das nicht stimmt, werden gestrichen.
  4. Wiederhole 2 und 3, bis die Lösung gefunden ist.

Der Schlüssel liegt in Schritt 3, „nur die Möglichkeiten behalten, die denselben Hinweis ergeben“. Das ist dieselbe Überlegung, die du im Kopf machst, nur mechanisch für alle Möglichkeiten.

Das Programm

In JavaScript sieht es so aus. Du kannst es in den Entwicklerwerkzeugen des Browsers oder mit Node.js auf dem Computer ausführen.

// Treffer und Fast zählen
function judge(answer, guess) {
  let hit = 0, blow = 0;
  for (let i = 0; i < guess.length; i++) {
    if (guess[i] === answer[i]) hit++;
    else if (answer.includes(guess[i])) blow++;
  }
  return [hit, blow];
}

// Alle Reihen aus lauter verschiedenen Ziffern erzeugen
function allCodes(digits, prefix = '') {
  if (prefix.length === digits) return [prefix];
  const list = [];
  for (const d of '0123456789') {
    if (!prefix.includes(d)) list.push(...allCodes(digits, prefix + d));
  }
  return list;
}

// Immer die erste Möglichkeit tippen, die zu den Hinweisen passt
function solve(answer) {
  let candidates = allCodes(answer.length);
  for (let turn = 1; ; turn++) {
    const guess = candidates[0];
    const [hit, blow] = judge(answer, guess);
    console.log(turn, guess, hit, blow, candidates.length);
    if (hit === answer.length) return turn;
    candidates = candidates.filter((c) => {
      const [h, b] = judge(c, guess);
      return h === hit && b === blow;
    });
  }
}

solve('4719');
  • judge zählt aus Lösung und Tipp die Treffer und Fast. Weil alle Symbole verschieden sind, gilt: „Stimmt die Stelle, ist es ein Treffer. Stimmt sie nicht, aber das Symbol kommt in der Lösung vor, ist es ein Fast.“
  • allCodes erzeugt alle Reihen aus lauter verschiedenen Ziffern.
  • solve tippt die erste Möglichkeit und behält nur die, die denselben Hinweis ergeben, und das immer wieder.

Ergebnis

Bei der Lösung „4719“ wurde Folgendes ausgegeben (von links: Nummer des Versuchs, Tipp, Treffer, Fast und Zahl der Möglichkeiten vor dem Tipp).

1 0123 0 1 5040
2 1456 0 2 1440
3 2547 0 2 369
4 3674 0 2 80
5 4268 1 0 15
6 4395 1 1 6
7 4719 4 0 1

Die Möglichkeiten sanken von 5040 auf 1440, 369, 80, 15, 6 und 1, und im 7. Versuch war die Lösung gefunden. Lässt man dieses Programm alle 5040 Lösungen lösen, braucht es im Durchschnitt etwa 5,56 Versuche und für die schwerste Lösung 9.

Wie es mit weniger Versuchen geht

Dieses Programm tippt immer „die erste Möglichkeit“. Wählt man die Tipps geschickter, werden es weniger Versuche.

  • Einen Tipp wählen, der den Rest gut aufteilt: Für jeden möglichen Tipp zählt man, wie sich die Möglichkeiten auf die denkbaren Hinweise verteilen, und wählt den Tipp, bei dem die größte übrig bleibende Gruppe möglichst klein ist oder der Rest im Durchschnitt möglichst klein wird.
  • Auch Reihen tippen, die nicht mehr möglich sind: Selbst eine Reihe, von der man weiß, dass sie falsch ist, lohnt sich manchmal, wenn sie die Möglichkeiten gut aufteilt.

Mit diesen Kniffen sind es bei 4 Stellen für jede Lösung höchstens 7 Versuche, im Durchschnitt etwa 5,3 (Gibt es eine Gewinnstrategie bei Bulls and Cows?). Dafür muss man für jeden Tipp sehr viele Kombinationen prüfen, die Berechnung dauert also länger.

Der „Tipp“ der App folgt derselben Idee

Auch der „Tipp“ der App „Bulls and Cows“ zählt alle Lösungen, die zu den bisherigen Hinweisen passen, und zeigt eine Sache in dieser Reihenfolge:

  1. Gibt es eine Stelle, an der bei jeder Möglichkeit dasselbe Symbol steht, zeigt er diese Stelle.
  2. Gibt es ein Symbol, das in keiner Möglichkeit vorkommt, zeigt er dieses.
  3. Gibt es beides nicht, deckt er eine Stelle der Lösung auf.

(So nutzt du den Tipp)

Wenn du selbst ein Spiel bauen möchtest, lies auch So baust du ein Zahlenrate-Spiel.