Comment le solveur Meowdoku lit un plateau depuis une capture d'écran
Le solveur Meowdoku prend une entrée inhabituelle : une photo du puzzle plutôt que le puzzle lui-même. Avant de pouvoir résoudre quoi que ce soit, il doit déterminer où se trouve le plateau dans votre capture d'écran, en combien de cases il est divisé, et quelles cases partagent une couleur. Voici comment chacune de ces questions est tranchée, et où cela se trompe encore.
La partie difficile, ce n'est pas de lire les couleurs
Une capture d'écran Meowdoku n'est en majorité pas le plateau. Il y a un en-tête, une rangée de puces de règles, un chronomètre, et généralement une barre d'état système avec le pourcentage de batterie de quelqu'un dessus. Le plateau est un bloc carré quelque part au milieu, à une position et une taille qui dépendent du téléphone d'origine, et rien dans l'image n'est étiqueté.
Trois inconnues doivent être fixées avant qu'une seule couleur ne vaille la peine d'être lue, et en manquer une seule ne rend pas la réponse un peu fausse. Cela en fait un puzzle différent, résolu avec assurance.
Tout s'exécute dans votre navigateur
La capture d'écran n'est jamais envoyée. L'image est dessinée sur un canevas, les pixels en sont relus, et chaque étape ci-dessous s'exécute sur ce tableau de nombres dans votre propre onglet. Aucun serveur ne voit l'image, et aucune copie n'en existe nulle part ailleurs que sur votre appareil.
Une image que vous n'envoyez jamais est une image que personne n'a besoin de stocker ni de vous promettre avoir supprimée, et un pipeline sans aucun aller-retour réseau retourne un plateau en bien moins d'une seconde.
La première chose qu'il fait est de réduire l'image pour que son côté le plus long fasse au plus 900 pixels. Rien en aval ne veut plus de détail que cela, puisque l'objectif est une couleur représentative par case plutôt qu'une image nette, et le travail par pixel chute avec le carré de l'échelle.
Étape 1 : trouver le plateau
Le solveur commence par deviner l'arrière-plan de la page. Il échantillonne la bande de 7 % autour des quatre bords de l'image et prend la médiane de chaque canal de couleur, en écartant d'abord les pixels vifs de l'échantillon pour qu'une bannière très colorée coupant un coin ne puisse pas fausser l'estimation.
Chaque pixel est ensuite étiqueté arrière-plan ou non-arrière-plan selon sa distance à cette estimation, et les pixels non-arrière-plan sont comptés ligne par ligne. Cela donne un profil de densité le long de l'image : proche de zéro dans les marges vides, élevé sur le plateau, quelque part entre les deux sur un en-tête. Les séries de lignes à forte densité deviennent des candidats. Les creux fins que les limites de cases entaillent dans le profil sont comblés, parce qu'une ligne de grille d'un pixel n'est pas un vide, alors que le véritable espace au-dessus du plateau ne l'est pas, ce qui garde les puces de règles hors du candidat.
Vient ensuite le test qui fait le vrai travail : la forme carrée. Chaque candidat est balayé sur l'autre axe pour trouver un bord gauche et droit, et seuls ceux dont la largeur et la hauteur sont à environ un tiers l'une de l'autre, couvrant au moins 3 % du cadre, survivent. Bannières, rangées de puces et barres d'état sont toutes larges et courtes. Sur une capture Meowdoku, le plateau est la seule chose qui soit carrée.
Quand rien de carré ne ressort, le solveur suppose que vous avez déjà recadré sur le plateau et utilise le cadre entier. C'est un bon échec à avoir : l'image qu'il n'arrive pas à localiser est généralement celle qui n'avait pas besoin de l'être.
Étape 2 : compter la grille
Savoir où est le plateau ne dit pas s'il s'agit d'un 7×7 ou d'un 9×9. Pour trancher, le solveur parcourt le cadre du plateau en 400 pas et mesure à chaque pas combien la couleur a changé par rapport au pas précédent, moyenné sur 48 lignes parallèles couvrant l'autre axe pour qu'un seul chat sombre ne puisse pas passer pour une limite. Les bords de case ressortent comme des pics réguliers.
Plutôt que de mesurer l'espacement entre les pics, il teste des hypothèses. Pour chaque N de 4 à 12, il calcule où tomberaient les N−1 limites internes de cette grille, cherche un pic près de chaque position, et note l'hypothèse selon la qualité moyenne de la correspondance de ses limites. Le N qui explique le mieux le profil l'emporte.
Les deux axes sont mesurés indépendamment puis réconciliés, parce qu'un vrai plateau est carré. Si la passe horizontale dit 8 et la verticale dit 7, l'une des deux a manqué une ligne peu marquée, donc c'est le plus grand des deux comptes qu'il faut croire.
Étape 3 : échantillonner chaque case sur un anneau, pas en son centre
C'est l'étape qui n'est pas évidente. Le plateau localisé et la grille comptée, le solveur a besoin d'une couleur par case, et le geste naturel est de lire le pixel au milieu de la case.
C'est précisément le mauvais pixel. Le milieu de la case est là où se trouve le chat, et là où se trouve le ✕ sur une case que vous avez exclue. Sur un plateau partiellement résolu, c'est-à-dire n'importe quel plateau pour lequel vous voudriez vraiment de l'aide, l'échantillonnage au centre lit une grande part des cases comme colorées par le chat et invente des régions qui n'apparaissent nulle part sur votre écran.
Chaque case est donc échantillonnée sur trois anneaux concentriques à la place, à 28 %, 36 % et 43 % de la distance depuis son centre, à seize angles chacun : quarante-huit échantillons par case. Cet anneau se trouve à l'intérieur de la limite de la case, donc il ne capte jamais une ligne de grille, et à l'extérieur du glyphe, donc aucun chat ne peut détourner la lecture. Les échantillons sont réduits en prenant la médiane de chaque canal plutôt que la moyenne, ce qui écarte par le vote les quelques-uns qui tombent sur un bord anticrénelé ou un reflet plutôt que de les mélanger.
Étape 4 : regrouper les couleurs en exactement N régions
Il y a maintenant N×N couleurs à trier en régions. C'est un problème de clustering, et les problèmes de clustering sont généralement difficiles d'une manière particulière : on ne sait pas combien de groupes chercher, et se tromper ruine silencieusement la réponse.
Meowdoku le sait. Les règles le fixent. Un plateau N×N est divisé en exactement N régions connexes, donc un plateau 9×9 en a neuf, jamais huit et jamais dix. Ce seul fait transforme une question ouverte en question fermée, un k-means avec k déjà connu, et c'est pourquoi cette étape est fiable alors que les deux précédentes sont au mieux des efforts raisonnables.
Deux détails la stabilisent. Les centres de départ sont choisis en « plus éloigné d'abord » : chaque nouveau centre est la couleur la plus éloignée de tous les centres déjà choisis, ce qui répartit les points de départ sur les teintes réellement présentes plutôt que d'en laisser deux se disputer le même jaune pâle. Et comme cet amorçage est déterministe plutôt qu'aléatoire, une même capture d'écran donne toujours le même plateau. Un solveur qui répondrait différemment sur deux imports d'une même image serait pire que pas de solveur du tout.
Les identifiants de région sont ensuite renumérotés dans l'ordre de lecture, si bien que la région contenant la case en haut à gauche vient en premier. Rien dans la résolution n'en dépend ; le plateau arrive simplement numéroté comme une personne le numéroterait.
Étape 5 : résoudre, et ce que dit une seconde solution
Avec une grille d'identifiants de région et une taille, résoudre est la partie directe, en exécutant le même solveur de contraintes que celui utilisé par le jeu pour construire les plateaux. La décision intéressante est qu'il demande deux solutions, pas une.
Un plateau Meowdoku correctement lu a exactement une solution, parce que le générateur le garantit en le construisant. Donc deux solutions signifient que le plateau en cours de résolution n'est pas le plateau de votre capture d'écran, et qu'une case est allée dans la mauvaise région. Aucune solution signifie qu'une erreur de lecture dans l'autre sens fait maintenant se contredire les contraintes. Demander une seconde réponse transforme le résultat en verdict sur la lecture qui l'a produit.
Où cela échoue, et pourquoi vous pouvez peindre
Tout ce qui précède l'étape 4 est un effort raisonnable, et tout peut être mis en défaut. Voici les cas qui se présentent réellement :
- Deux teintes proches dans une capture compressée. De lourds artefacts JPEG peuvent rapprocher suffisamment deux couleurs de région pour que k-means les fusionne, puis coupe en deux une troisième région pour garder le compte à N.
- Une photo d'un écran plutôt qu'une capture. Prise en angle, les cases cessent d'être régulièrement espacées, ce qui casse l'hypothèse sous-jacente au comptage de grille comme à l'échantillonnage sur anneau.
- Un recadrage qui garde une partie de l'interface. Une demi-puce de règle restée dans le cadre peut décaler la boîte du plateau de quelques pixels, et près des bords cela suffit à faire glisser les anneaux dans la case voisine.
- Un plateau presque terminé. Plus il y a de chats et de ✕ dessus, plus chaque case est couverte. Les anneaux aident beaucoup ici, mais ils ne sont pas magiques.
L'outil de peinture est le design, pas une roue de secours
C'est pourquoi chaque case détectée peut être repeinte en glissant sur le plateau, et pourquoi le solveur refuse de s'exécuter tant qu'exactement N régions distinctes ne sont pas présentes, en vous disant combien vous en avez actuellement. Ce garde-fou attrape l'échec de fusion-puis-division ci-dessus avant qu'il ne produise une réponse fausse mais confiante.
Le plateau vous est aussi redessiné dans les couleurs échantillonnées depuis votre propre capture d'écran plutôt que dans la palette du jeu, afin que vous puissiez vérifier la lecture d'un coup d'œil plutôt que de lui faire confiance aveuglément. Si une case a la mauvaise couleur sur notre plateau, c'est qu'elle a la mauvaise couleur, et un glisser la corrige. La détection fait les quatre-vingt-dix et quelques pour cent fastidieux ; vous fournissez le jugement pour le reste.
Essayez-le sur un de vos plateaux
Prenez une capture d'écran d'un plateau où vous êtes bloqué, déposez-la dans le solveur, et observez quelles cases il se trompe. Les erreurs de lecture sont presque toujours aux endroits que cet article prédit.
Le solveur s'exécute entièrement dans votre navigateur. Les captures d'écran sont lues sur votre appareil et ne sont jamais envoyées.