Blog

Logikrätsel mit genau einer Lösung bauen

8 Min. Lesezeit

Ein Rätsel zu bauen ist leicht. Zu beweisen, dass es nur eine Lösung hat, ist die eigentliche Arbeit. Hier steht, wie das bei den Logikquadraten läuft und wo ich zweimal danebenlag.

Ein Logikrätsel mit zwei Lösungen ist kein Logikrätsel. Irgendwann kommt die Stelle, an der zwei Ziffern gleich gut passen, und ab da wird geraten. Deshalb geht bei mir kein Rätsel raus, dessen Eindeutigkeit nicht nachgerechnet ist. Das galt schon für mein Sudoku, und es gilt für die vier Spielarten der Logikquadrate.

Vier Rätsel, ein Gitter

Alle vier werden auf einem quadratischen Gitter gespielt. Was sie unterscheidet, ist die Art der Hinweise.

Futoshiki: ein lateinisches Quadrat, also jede Ziffer von 1 bis n genau einmal pro Zeile und Spalte. Zwischen Nachbarfeldern stehen < und >, die sagen, welches Feld größer ist.
Wolkenkratzer: wieder ein lateinisches Quadrat, aber jede Ziffer ist die Höhe eines Hauses. Die Zahlen am Rand sagen, wie viele Häuser man von dort sieht. Niedrige verschwinden hinter hohen.
Magisches Quadrat: die Zahlen von 1 bis 9 oder von 1 bis 16, jede genau einmal. Alle Zeilen, Spalten und beide Diagonalen ergeben dieselbe Summe.
Rechenquadrat, anderswo Calcudoku oder KenKen: ein lateinisches Quadrat, aufgeteilt in Käfige. Die Felder eines Käfigs ergeben zusammen eine Zielzahl, mit Plus, Minus, Mal oder Geteilt.

Das magische Quadrat ist der Ausreißer. Es ist kein lateinisches Quadrat und braucht eine eigene Suche. Die anderen drei teilen sich einen Löser.

Erzeugt wird vorab, gespielt im Browser

Die Rätsel entstehen nicht beim Spielen. Ein Python-Skript, generate-quadrate.py, erzeugt sie vorab und schreibt sie in vier JSON-Dateien. Vier Spielarten, vier Stufen, fünf Rätsel je Stufe: 80 Rätsel.

Im Browser läuft weder ein Generator noch ein Löser. Das Skript auf der Seite zeichnet das Brett und nimmt Eingaben an. Ob eine Ziffer stimmt, prüft es gegen die Lösung aus der Bank. Ein Regelwerk im Browser wäre eine zweite Wahrheit neben dem Generator, und zwei Wahrheiten laufen irgendwann auseinander. Außerdem fällt die Rechenzeit so einmal auf meinem Rechner an und nicht bei jedem Besuch.

Jedes Rätsel hat eine feste Adresse

Die Erzeugung ist zufällig, aber reproduzierbar. Jedes Rätsel bekommt seinen Startwert aus seiner Adresse in der Bank, also aus Spielart, Stufe und Nummer:

def seed_for(variant, difficulty, number):
    key = f"{variant}/{difficulty}/{number}"
    value = 0
    for ch in key:
        value = (value * 131 + ord(ch)) & 0xFFFFFFFF
    return value

Das hat zwei Folgen. Ein zweiter Lauf erzeugt dieselben Dateien, Byte für Byte. Und wenn ich eine Stufe umbaue, bleiben alle anderen Rätsel, wie sie sind, weil ihr Startwert nicht vom Rest des Laufs abhängt.

Mit --check rechnet das Skript alles neu und meldet nur, ob sich eine Bank ändern würde. Zuletzt lautete die Antwort: keine. Das dauert auf meinem Rechner knapp anderthalb Minuten. Deshalb gehört es nicht in den Veröffentlichungslauf. Ich starte es von Hand, wenn sich an der Schwierigkeit etwas ändert.

Beweisen heißt bis zwei zählen

Die Eindeutigkeit prüft ein Löser, der alle Lösungen zählt, aber nur bis zwei. Die zweite Lösung reicht als Gegenbeweis. Die dritte zu suchen kostet nur Zeit.

Der Löser füllt das Gitter Zeile für Zeile, von links oben. Für jedes Feld probiert er die Ziffern, die in Zeile und Spalte noch frei sind, und geht einen Schritt zurück, sobald eine Regel verletzt ist. Das Verfahren heißt Backtracking. Die Reihenfolge ist Absicht: Wenn ein Feld gesetzt wird, stehen sein linker und sein oberer Nachbar schon fest. Ein Futoshiki-Zeichen lässt sich also sofort prüfen, und eine Wolkenkratzer-Zeile ist genau dann fertig, wenn ihr letztes Feld steht. Keine Regel muss über leere Felder hinwegschauen.

Die drei lateinischen Spielarten hängen nur ihre Zusatzregel an diesen Löser. Beim Wolkenkratzer gehört eine Teilprüfung dazu: Sieht man von links schon mehr Häuser, als die Randzahl erlaubt, kann die Zeile nicht mehr stimmen. Die Zahl kann nur noch wachsen. Das spart beim 6×6 den Großteil des Suchbaums.

Vom vollen Satz abwärts

Futoshiki, Wolkenkratzer und das magische Quadrat folgen demselben Muster. Zuerst entsteht eine zufällige fertige Lösung. Dann kommen alle Hinweise dazu, die zu ihr passen: alle Ungleichungen, alle Randzahlen, beim magischen Quadrat alle Zahlen. Danach wird gestrichen. Jeder Hinweis fliegt probeweise raus. Bleibt das Rätsel eindeutig, bleibt er draußen, sonst kommt er zurück.

Der umgekehrte Weg, Hinweise einzeln dazuzulegen, bis das Rätsel eindeutig ist, endet oft mit einem zu viel. Der zuletzt gelegte macht eindeutig, ein früherer wäre danach entbehrlich, und niemand schaut noch einmal nach. Wer dagegen vom vollen Satz aus streicht, bis nichts mehr geht, behält keinen Hinweis, der fehlen dürfte.

Falle 1: Alle Hinweise heißt nicht eindeutig

Diese und die nächste Falle haben mich einen Umbau gekostet. Naheliegend ist die Annahme, ein Rätsel mit allen Hinweisen sei eindeutig und das Streichen könne einfach dort beginnen. Das stimmt nicht. Ein 4×4-Wolkenkratzer mit allen sechzehn Randzahlen hat regelmäßig vier bis sechs Lösungen. Die Randzahl sagt nur, wie viele Häuser herausragen, nicht welche. Beim Futoshiki ist es ähnlich: Die Ungleichungen beschreiben die Reihenfolge innerhalb einer Zeile oder Spalte, nicht die Werte, und lassen oft zwei Quadrate zu.

Tückisch ist, dass nichts kaputt aussieht. Ist das Rätsel schon vor dem Streichen mehrdeutig, scheitert jede einzelne Streichung. Das Rätsel behält alle Hinweise und wirkt bloß sehr großzügig. Dass das Streichen nie gegriffen hat, sieht man der Ausgabe nicht an.

Die Lösung heißt fill_until_unique. Bevor gestrichen wird, legt sie so lange Ziffern aus der Lösung ins Gitter, bis es genau eine Lösung gibt:

def fill_until_unique(n, solution, givens, spots, count):
    placed = []
    while count() != 1:
        if not spots:
            raise RuntimeError("kein eindeutiges Rätsel trotz voller Vorgaben")
        index = spots.pop()
        r, c = divmod(index, n)
        givens[r][c] = solution[r][c]
        placed.append(index)
    return placed

Die Schleife endet sicher: Ist jedes Feld vorgegeben, gibt es genau eine Lösung. Danach werden zuerst diese Ziffern wieder gestrichen, so weit es geht, und erst dann die Zeichen oder Randzahlen. Ein Wolkenkratzer soll am Rand gelöst werden, und jede Ziffer im Feld nimmt genau das weg. Beim Futoshiki ist es dasselbe: Die leichte Stufe soll mehr Zeichen zeigen, nicht mehr Ziffern.

Falle 2: Summen, die doppelt zählen

Beim magischen Quadrat gibt es keine Regel wie „jede Ziffer einmal pro Zeile“, nur Summen. Die Suche prüft deshalb für jede angefangene Zeile, Spalte und Diagonale, ob sie ihre Zielsumme mit den noch freien Zahlen überhaupt erreichen kann. Dazu addiert sie die kleinsten und die größten freien Zahlen, eine je offenes Feld. Das ist die Schranke. Beim 3×3 liegt die Zielsumme bei 15, beim 4×4 bei 34. Am Zeilenende muss die Suche nicht raten, sie rechnet den fehlenden Wert aus.

Der Fehler steckte in den laufenden Summen. Ich hatte sie anfangs aus dem Gitter vorbelegt, samt der Vorgaben. Eine Vorgabe rechts vom aktuellen Feld steckte dann schon in der Summe und zählte in der Schranke zugleich als offenes Feld. Sie zählte doppelt, und die Suche verwarf Wege, die gangbar waren. Jetzt laufen die Summen mit der Suche mit: Die Zeilensumme enthält nur die Felder links vom aktuellen. Eine vorgegebene Zahl ist trotzdem sofort für alle anderen Felder gesperrt, auch bevor die Suche bei ihr ankommt.

Die Schwierigkeit steckt in einer Tabelle

Wie schwer ein Rätsel wird, regelt eine einzige Tabelle namens PLAN. Sie legt pro Spielart und Stufe die Kantenlänge fest und keep: die Zahl der Hinweise, bei der das Streichen aufhört. Null heißt: bis zum Minimum.

Futoshiki geht von 4×4 bis 6×6. Die leichteste Stufe behält 12 Hinweise, die Profistufe im 5×5 kommt mit 9 bis 12 aus.
Wolkenkratzer bleibt in den ersten beiden Stufen bei 4×4. Die zweite streicht bis zum Minimum, übrig bleiben 4 oder 5 Hinweise.
Magisches Quadrat bleibt bei 3×3 und 4×4. Ab 5×5 schneidet die Summe den Suchraum kaum noch ein, Lösen wird zum Probieren, und schon ein einziges Quadrat zu erzeugen dauert länger als eine ganze Bank der anderen Spielarten.
Rechenquadrat wächst von 4×4 mit Käfigen aus höchstens zwei Feldern bis 6×6 mit Käfigen aus bis zu vier.

Beim magischen Quadrat ist das Minimum bewusst nicht das Ziel. Ein 4×4 lässt sich bis auf drei Vorgaben ausdünnen und bleibt eindeutig, ist dann aber nur noch durch Absuchen lösbar. Genau das soll ein Logikrätsel einem ersparen. Die beiden 4×4-Stufen hören deshalb bei neun und bei sechs Vorgaben auf.

Das Rechenquadrat fällt aus dem Muster. Die Käfige bedecken das ganze Gitter, einen wegzulassen hinterließe ein Loch. Statt zu streichen, würfelt das Skript die Käfige neu, bis zu 400 Mal. Nach 250 Fehlversuchen darf der größte Käfig ein Feld weniger haben, weil kleine Käfige mehr verraten. Dazu kommen ein paar Regeln für lesbare Käfige. Minus und Geteilt gibt es nur bei zwei Feldern, weil bei dreien die Reihenfolge offen wäre. „Geteilt durch 1“ fällt weg, das verrät nichts. Produkte über 200 auch, sie lassen fast jede Kombination zu.

Warum das Skript so schlicht aussieht

Wer Python kennt, wird manches umständlich finden. Das ist Absicht: Rekursion, Listen, Bitmasken, keine Python-Eigenheiten. Das Skript ist die Vorlage für Quadrivium, meine iOS-Sammlung mit denselben vier Spielarten, seit August 2026 im App Store. Die Algorithmen sollen sich nach Swift übertragen lassen, ohne dass man sie neu erfinden muss. Wer im Skript etwas ändert, ändert die Referenz.

Der Unterschied liegt in der Arbeitsteilung. Die Browserseite spielt eine feste Bank mit 80 Rätseln ab, in der App entsteht jedes Rätsel beim Start neu. Der Anspruch ist derselbe: lösbar ohne Raten.

Quellen

Wikipedia: Futoshiki, Regeln der Ungleichungsrätsel
Wikipedia: Lateinisches Quadrat, die gemeinsame Grundregel von drei der vier Spielarten
Wikipedia: Magisches Quadrat, Aufbau und magische Summe
Wikipedia: Backtracking, das Suchverfahren hinter Generator und Löser
Conceptis Puzzles: Skyscrapers rules, Regeln der Wolkenkratzer-Rätsel
Simon Tatham: Towers, Wolkenkratzer aus einem anderen Generator, bei schweren oder großen Rätseln ebenfalls mit vorgegebenen Feldern
Wikipedia: KenKen, Rechenkäfig-Rätsel, auch Calcudoku genannt