Wie der Meowdoku-Solver ein Spielfeld aus einem Screenshot liest
Der Meowdoku-Solver bekommt eine ungewöhnliche Eingabe: ein Foto des Rätsels statt des Rätsels selbst. Bevor er irgendetwas lösen kann, muss er herausfinden, wo sich das Spielfeld in deinem Screenshot befindet, in wie viele Zellen es unterteilt ist und welche Zellen sich eine Farbe teilen. So wird jede dieser Fragen entschieden — und hier liegt er noch daneben.
Das Schwierige ist nicht das Ablesen der Farben
Ein Meowdoku-Screenshot ist größtenteils nicht das Spielfeld. Es gibt einen Header, eine Reihe von Regel-Chips, eine Stoppuhr und meist eine System-Statusleiste mit irgendjemandes Akkuprozentsatz darauf. Das Spielfeld ist ein quadratischer Block irgendwo in der Mitte, an einer Position und in einer Größe, die vom Ursprungstelefon abhängen, und nichts im Bild ist beschriftet.
Drei Unbekannte müssen feststehen, bevor auch nur eine einzige Farbe abzulesen sich lohnt, und eine davon zu verpassen macht die Antwort nicht leicht falsch. Es macht daraus ein anderes Rätsel, das selbstbewusst gelöst wird.
Alles läuft in deinem Browser
Der Screenshot wird nie hochgeladen. Das Bild wird auf ein Canvas gezeichnet, die Pixel werden daraus wieder ausgelesen, und jeder Schritt unten läuft auf diesem Zahlenarray in deinem eigenen Tab. Kein Server sieht das Bild, und keine Kopie davon existiert irgendwo außer auf deinem Gerät.
Ein Bild, das du nie versendest, muss niemand speichern oder dir versprechen, gelöscht zu haben, und eine Pipeline ohne einen einzigen Netzwerk-Hop liefert ein Spielfeld in deutlich unter einer Sekunde.
Das Erste, was passiert, ist, dass das Bild so verkleinert wird, dass seine längere Seite höchstens 900 Pixel hat. Nachgelagert will niemand mehr Detail als das, denn das Ziel ist eine repräsentative Farbe pro Zelle statt eines scharfen Bildes, und der Aufwand pro Pixel fällt mit dem Quadrat des Maßstabs.
Schritt 1: das Spielfeld finden
Der Solver rät zuerst den Seitenhintergrund. Er tastet den 7-%-Streifen an allen vier Bildrändern ab und nimmt den Median jedes Farbkanals, wobei zuerst grelle Pixel aus der Stichprobe entfernt werden, damit ein knallbuntes Banner, das in eine Ecke hineinragt, die Schätzung nicht verzerren kann.
Jedes Pixel wird dann anhand seines Abstands zu dieser Schätzung als Hintergrund oder Nicht-Hintergrund markiert, und die Nicht-Hintergrund-Pixel werden zeilenweise gezählt. Das ergibt ein Dichteprofil über das Bild hinweg: nahe null in leeren Rändern, hoch über dem Spielfeld, irgendwo dazwischen über einem Header. Läufe von Zeilen mit hoher Dichte werden zu Kandidaten. Die schmalen Einbrüche, die Zellgrenzen in das Profil schneiden, werden überbrückt, weil eine ein Pixel breite Rasterlinie keine Lücke ist, während der echte Freiraum über dem Spielfeld das nicht ist — das hält die Regel-Chips aus dem Kandidaten heraus.
Dann kommt der Test, der die eigentliche Arbeit macht: Quadratform. Jeder Kandidat wird entlang der anderen Achse nach einem linken und rechten Rand abgesucht, und nur jene, deren Breite und Höhe innerhalb von etwa einem Drittel voneinander liegen und mindestens 3 % des Bildausschnitts abdecken, überleben. Banner, Chip-Reihen und Statusleisten sind alle breit und flach. Auf einem Meowdoku-Screenshot ist das Spielfeld das Einzige, das quadratisch ist.
Sticht nichts Quadratisches heraus, nimmt der Solver an, dass du schon auf das Spielfeld zugeschnitten hast, und verwendet das gesamte Bild. Das ist ein gutes Versagen: Das Bild, das er nicht lokalisieren kann, ist meist das Bild, das gar keine Lokalisierung brauchte.
Schritt 2: das Raster zählen
Zu wissen, wo das Spielfeld ist, sagt nicht, ob es ein 7×7 oder ein 9×9 ist. Um das zu klären, durchläuft der Solver das Spielfeld-Rechteck in 400 Schritten und misst bei jedem Schritt, wie stark sich die Farbe gegenüber dem vorherigen Schritt geändert hat, gemittelt über 48 parallele Linien entlang der anderen Achse, damit eine einzelne dunkle Katze nicht als Grenze durchgeht. Zellgrenzen erscheinen als regelmäßige Spitzen.
Statt den Abstand zwischen den Spitzen zu messen, testet er Hypothesen. Für jedes N von 4 bis 12 berechnet er, wo die N−1 inneren Grenzen dieses Rasters liegen würden, sucht nahe jeder Position nach einer Spitze und bewertet die Hypothese danach, wie gut ihre Grenzen im Schnitt getroffen werden. Das N, das das Profil am besten erklärt, gewinnt.
Beide Achsen werden unabhängig gemessen und dann abgeglichen, weil ein echtes Spielfeld quadratisch ist. Sagt der horizontale Durchgang 8 und der vertikale 7, hat einer von beiden eine schwache Linie verpasst — also gilt die größere der beiden Zahlen.
Schritt 3: jede Zelle auf einem Ring abtasten, nicht in ihrer Mitte
Das ist der Schritt, der nicht offensichtlich ist. Mit lokalisiertem Spielfeld und gezähltem Raster braucht der Solver eine Farbe pro Zelle, und der naheliegende Griff ist, das Pixel in der Mitte der Zelle zu lesen.
Das ist genau das falsche Pixel. Die Mitte der Zelle ist dort, wo die Katze sitzt, und dort, wo das ✕ auf einer ausgeschlossenen Zelle sitzt. Auf einem teilweise gelösten Feld — also jedem Feld, bei dem du tatsächlich Hilfe wollen würdest — liest die Mittenabtastung einen großen Teil der Zellen als katzenfarben und erfindet Regionen, die nirgendwo auf deinem Bildschirm existieren.
Also wird jede Zelle stattdessen auf drei konzentrischen Ringen abgetastet, bei 28 %, 36 % und 43 % des Weges von ihrer Mitte nach außen, mit je sechzehn Winkeln: achtundvierzig Proben pro Zelle. Dieser Ring liegt innerhalb der Zellgrenze, erwischt also nie eine Rasterlinie, und außerhalb des Symbols, sodass keine Katze die Ablesung kapern kann. Die Proben werden über den Median jedes Kanals statt über den Mittelwert reduziert, was die wenigen, die auf einer Antialiasing-Kante oder einem Glanzlicht landen, aussticht, statt sie einzumischen.
Schritt 4: die Farben in genau N Regionen gruppieren
Jetzt gibt es N×N Farben, die in Regionen sortiert werden müssen. Das ist ein Clustering-Problem, und Clustering-Probleme sind meist auf eine bestimmte Art schwierig: Man weiß nicht, nach wie vielen Clustern man suchen soll, und sich zu verschätzen ruiniert die Antwort still.
Meowdoku weiß es. Die Regeln legen es fest. Ein N×N-Feld ist in genau N zusammenhängende Regionen unterteilt, also hat ein 9×9-Feld neun, nie acht und nie zehn. Allein diese Tatsache macht aus einer offenen eine geschlossene Frage — k-means mit bereits bekanntem k —, und deshalb ist dieser Schritt zuverlässig, während die beiden davor bestenfalls nach Bestem Bemühen arbeiten.
Zwei Details halten ihn stabil. Die Startzentren werden nach dem Prinzip „am weitesten zuerst“ gewählt: Jedes neue ist die Farbe, die von allen bisher gewählten Zentren am weitesten entfernt ist, was die Startpunkte über die tatsächlich vorhandenen Farbtöne verteilt, statt zwei um denselben blassen Gelbton streiten zu lassen. Und weil dieses Seeding deterministisch statt zufällig ist, liefert ein Screenshot immer dasselbe Spielfeld. Ein Solver, der bei zwei Uploads desselben Bildes unterschiedlich antwortet, wäre schlechter als gar keiner.
Die Regions-IDs werden anschließend in Lesereihenfolge neu nummeriert, sodass die Region mit der Zelle oben links zuerst kommt. Nichts an der Lösung hängt davon ab; das Spielfeld kommt einfach so nummeriert an, wie es ein Mensch nummerieren würde.
Schritt 5: lösen, und was eine zweite Lösung verrät
Mit einem Raster aus Regions-IDs und einer Größe ist das Lösen der geradlinige Teil, wobei derselbe Constraint-Solver läuft, den das Spiel zum Bauen von Spielfeldern nutzt. Die interessante Entscheidung ist, dass er nach zwei Lösungen fragt, nicht nach einer.
Ein korrekt gelesenes Meowdoku-Feld hat genau eine Lösung, weil der Generator das beim Bauen garantiert. Zwei Lösungen bedeuten also, dass das gelöste Feld nicht das Feld in deinem Screenshot ist und irgendeine Zelle in die falsche Region geraten ist. Keine Lösung bedeutet, dass ein Fehler in die andere Richtung die Bedingungen jetzt widersprüchlich macht. Nach einer zweiten Antwort zu fragen, macht aus dem Ergebnis ein Urteil über die Ablesung, die es hervorgebracht hat.
Wo es scheitert, und warum du malen kannst
Alles vor Schritt 4 ist bestes Bemühen, und alles davon lässt sich austricksen. Das sind die Fälle, die tatsächlich vorkommen:
- Zwei nahe beieinanderliegende Farbtöne in einem komprimierten Screenshot. Starke JPEG-Artefakte können zwei Regionsfarben nah genug zusammenziehen, dass k-means sie verschmilzt und dann eine dritte Region halbiert, um die Zahl bei N zu halten.
- Ein Foto eines Bildschirms statt ein Screenshot. Aus einem Winkel aufgenommen, hören Zellen auf, gleichmäßig verteilt zu sein, was sowohl die Annahme hinter der Rasterzählung als auch die des Ring-Samplings bricht.
- Ein Ausschnitt, der einen Teil der Oberfläche behält. Ein halber Regel-Chip im Bild kann die Spielfeldbox um ein paar Pixel verschieben, und nahe den Rändern reicht das, um die Ringe in die Nachbarzelle rutschen zu lassen.
- Ein fast fertiges Spielfeld. Je mehr Katzen und ✕-Markierungen darauf sind, desto mehr von jeder Zelle ist verdeckt. Die Ringe helfen hier sehr, sind aber keine Magie.
Das Mal-Werkzeug ist das Design, nicht der Notbehelf
Deshalb lässt sich jede erkannte Zelle durch Ziehen über das Spielfeld neu einfärben, und deshalb weigert sich der Solver, zu laufen, bevor genau N unterschiedliche Regionen vorhanden sind — und sagt dir, wie viele du gerade hast. Diese Absicherung fängt den Verschmelzen-und-Teilen-Fehler von oben ab, bevor er eine selbstsichere, aber falsche Antwort erzeugt.
Das Spielfeld wird dir außerdem in den aus deinem eigenen Screenshot abgetasteten Farben zurückgezeichnet statt in der Palette des Spiels, damit du die Ablesung auf einen Blick prüfen kannst, statt ihr zu vertrauen. Sieht eine Zelle auf unserem Feld in der falschen Farbe aus, dann ist sie falsch, und ein Ziehen korrigiert es. Die Erkennung erledigt die mühsamen gut neunzig Prozent; du lieferst das Urteilsvermögen für den Rest.
Probiere es an einem eigenen Spielfeld
Mach einen Screenshot von einem Feld, an dem du feststeckst, wirf ihn in den Solver und beobachte, welche Zellen er falsch liest. Die Fehllesungen liegen fast immer genau dort, wo dieser Beitrag es vorhersagt.
Der Solver läuft vollständig in deinem Browser. Screenshots werden auf deinem Gerät gelesen und nie hochgeladen.