La règle du non-contact n'est vraiment qu'un écart de colonne
Chaque page de règles de ce jeu dit la même chose : deux chats ne peuvent jamais occuper des cases qui se touchent, même en diagonale, et chaque chat élimine les huit cases autour de lui. Pris au pied de la lettre, cela revient à vérifier huit voisins pour chaque chat posé. Le validateur qui bloque réellement un coup illégal ne fait jamais autant de travail, parce qu'un plateau Meowdoku a une propriété qui rend la plupart de ces huit voisins sans importance avant même d'avoir regardé une seule colonne.
La règle telle qu'elle est écrite
Deux chats ne peuvent jamais occuper des cases qui se touchent. Cela inclut les quatre cases qui partagent un bord avec un chat et les quatre qui ne partagent qu'un coin, si bien qu'un chat fraîchement posé élimine huit cases d'un coup, en plus de sa ligne, sa colonne et sa région. Chaque guide de ce site formule la règle ainsi, parce que c'est exactement ce qu'elle interdit.
Le code qui l'applique coup par coup est tout aussi direct : on pose un chat, et le validateur parcourt les huit décalages autour de lui et rejette le coup si l'un d'eux contient déjà un chat. Cette boucle tourne à chaque pose, ce qui mérite d'être questionné. Huit cases, c'est beaucoup à vérifier quand seules certaines d'entre elles étaient réellement en danger.
Pourquoi une seule ligne peut jamais gêner
Partons d'un fait qui n'a rien à voir avec le contact : un plateau à N lignes exige exactement N chats, et aucune ligne ne peut en contenir deux, donc une fois le plateau résolu, chaque ligne en contient exactement un. C'est simplement la règle des lignes énoncée à l'envers.
Le contact est une relation à distance 1 : deux cases se touchent seulement quand leur écart de ligne et leur écart de colonne valent tous les deux 0 ou 1. En combinant cela avec un chat par ligne, la portée de la règle s'effondre immédiatement. Un chat en ligne 2 et un chat en ligne 5 sont séparés de trois lignes, donc aucun appariement de colonnes entre eux ne peut jamais se toucher — l'écart de ligne seul dépasse déjà le test ±1. Les seules paires de chats qui peuvent éventuellement se toucher sont celles situées sur des lignes voisines.
Le solveur du jeu lui-même est écrit autour exactement de ce raccourci. Son module de contraintes compresse une solution complète en un seul numéro de colonne par ligne et énonce directement cette réduction dans ses propres commentaires : avec un chat par ligne garanti, la quatrième règle dégénère en « les numéros de colonne des lignes voisines diffèrent d'au moins 2 » — rien d'autre à revérifier.
Le haut, le bas, la gauche et la droite sont déjà pris en charge
Parmi les huit cases voisines d'un chat, quatre se trouvent juste au-dessus, en dessous, à gauche ou à droite. Chacune de ces quatre partage soit la ligne du chat, soit sa colonne — c'est ce qui les rend orthogonales plutôt que diagonales. La règle des lignes et celle des colonnes interdisent déjà un second chat sur l'une d'elles, donc la règle de contact n'est pas la raison pour laquelle ces quatre cases sont illégales. Elle ne fait que confirmer un verdict que deux règles plus simples ont déjà rendu.
Les quatre cases diagonales sont le seul endroit où la règle de contact peut réellement apporter une information que le reste des règles ne fournit pas déjà, car un voisin en diagonale ne partage ni la ligne ni la colonne du chat. Tout le contenu pratique du « pas de contact » tient donc dans quatre cases, pas huit — et même ces quatre-là sont parfois déjà mortes pour une raison sans rapport : une case en diagonale peut se trouver dans la même région colorée que le chat, ce que la règle de région élimine à elle seule.
Quelle part de cela est vraiment nouvelle
Sur quatre cents plateaux fraîchement générés par difficulté, voici ce qui se passe quand on vérifie, pour chaque chat du plateau résolu, combien de ses voisins diagonaux (jusqu'à quatre) étaient déjà illégaux par ligne, colonne ou région avant même que la règle de contact n'intervienne :
| Plateau | Déjà mort par ligne, colonne ou région | Nouvelle élimination due au seul contact |
|---|---|---|
| Facile 5×5 | 37% | 63% |
| Normal 7×7 | 44% | 56% |
| Difficile 9×9 | 47% | 53% |
| Extrême 10×10 | 49% | 51% |
À chaque difficulté, plus d'un tiers de la portée apparente de la règle de contact ne faisait en réalité jamais rien — la règle de région avait déjà tranché. Ce qui reste, les éliminations vraiment nouvelles, constitue toujours la majorité des cases diagonales, mais cette part rétrécit régulièrement à mesure que les plateaux grandissent : de 63 % en Facile à environ la moitié en Extrême.
Cette tendance suit la taille des régions, pas la règle de contact elle-même. Les régions grandissent avec les plateaux — une région Facile compte en moyenne cinq cases, une région Extrême en moyenne dix — donc un voisin diagonal pris au hasard a plus de chances de tomber dans la propre région du chat sur un grand plateau que sur un petit, et une part croissante du travail de la règle de contact se retrouve dupliquée par la règle de région avant même d'être nécessaire.
L'écart, mesuré
La règle qui survit à tout cela tient en un seul chiffre : pour chaque paire de lignes voisines du plateau résolu, l'écart de colonnes entre leurs deux chats doit être d'au moins 2. Un écart de 2 est la valeur la plus serrée que la règle autorise — une colonne de moins et les deux chats se toucheraient en diagonale. Voici la fréquence à laquelle les plateaux résolus atterrissent réellement sur ce minimum :
| Plateau | Lignes à l'écart légal minimum (2) | Écart moyen | Écart maximal possible |
|---|---|---|---|
| Facile 5×5 | 57.8% | 2.5 | 4 |
| Normal 7×7 | 35.1% | 3.2 | 6 |
| Difficile 9×9 | 27.5% | 3.9 | 8 |
| Extrême 10×10 | 26.2% | 4.2 | 9 |
Un écart exactement égal à 2 est le résultat le plus fréquent à chaque difficulté, devant toute autre valeur d'écart individuelle, même sur les plateaux où il ne représente qu'à peine un quart des lignes. C'est aussi, par définition, la valeur sans aucune marge : rapprochez l'un ou l'autre chat d'une colonne et le plateau cesse d'être légal.
Pourquoi les petits plateaux semblent plus serrés
C'est en Facile que la règle de contact mord le plus fort, et la raison est simplement l'espace disponible. Un plateau 5×5 n'a que cinq colonnes pour répartir cinq chats sur deux lignes voisines, donc un écart de 2 ou 3 couvre presque tous les appariements légaux — l'écart moyen, 2,5, dépasse à peine le minimum. Un plateau 10×10 a deux fois plus de colonnes et le même écart minimal de 2, donc un appariement a bien plus d'espace pour se retrouver confortablement loin de ce minimum, et la moyenne grimpe à 4,2.
Le minimum lui-même ne bouge jamais. Un écart de 1 correspond à un contact diagonal, quelle que soit la taille du plateau, à partir de 5×5. Ce qui change, c'est la fréquence à laquelle le plateau y atterrit, et ce chiffre baisse régulièrement à mesure que la grille grandit et que les chats ont plus de colonnes sur lesquelles se répartir.
Ce que cela vous apporte sur le plateau
Rien de tout cela ne change ce qui compte comme un placement légal — cela change la portion du plateau à regarder pour en vérifier un. Abandonnez l'habitude de scanner les huit voisins d'un nouveau chat, et utilisez plutôt ceci :
- Seules la ligne au-dessus et la ligne en dessous comptent. Un chat sur une ligne à deux lignes ou plus de celle où vous posez ne peut jamais rendre le coup illégal par contact. Si cette ligne n'est pas adjacente, ne perdez pas de temps dessus.
- Sur chacune de ces deux lignes, seules deux cases sont réellement à risque. Les cases juste au-dessus et en dessous sont déjà couvertes par la règle de colonne. Seules les deux cases en diagonale — une colonne à gauche, une à droite — portent une information que les règles de ligne et de colonne ne donnent pas.
- Un écart de exactement 2 est le cas serré, et il est fréquent. Quand le chat d'une ligne voisine se trouve à deux colonnes de l'endroit où vous vous apprêtez à poser, traitez cela comme un cas limite qui mérite une double vérification plutôt que comme une exception rare — c'est l'écart le plus probable, quelle que soit la taille du plateau.
- Les régions peuvent devancer la vérification. Si un voisin en diagonale partage déjà la région colorée de votre chat, il était déjà illégal avant même que le contact n'entre en jeu — environ une fois sur deux sur un grand plateau.
Comment cela a été mesuré
Les deux tableaux proviennent du générateur du jeu lui-même, le même code qui construit les plateaux auxquels vous jouez, exécuté sur quatre cents plateaux frais à chacune des quatre difficultés. « Déjà mort par ligne, colonne ou région » signifie que la case diagonale partage la région colorée du chat — partager sa ligne ou sa colonne est géométriquement impossible pour une case diagonale, donc la région est la seule autre règle capable de devancer le contact vers le même verdict. « Écart minimal légal » signifie une différence de colonnes de exactement 2 entre les chats de deux lignes voisines dans la solution finale.
Ce sont des propriétés des plateaux que ce générateur produit actuellement, et le générateur a déjà été réajusté par le passé. La suite de tests livrée avec cet article redérive les deux tableaux à partir de plateaux fraîchement générés à chaque exécution, si bien qu'un futur changement de la taille des régions ou du placement des colonnes fait échouer la build au lieu de laisser une statistique obsolète en ligne.
Essayez la règle de l'écart sur un vrai plateau
Lancez un plateau Difficile 9×9 et posez deux chats sur des lignes voisines sans compter les huit voisins de chacun — vérifiez simplement l'écart de colonnes entre eux. Tout ce qui est à 2 ou plus est légal ; exactement 2 est le cas serré qui mérite un second regard, et c'est l'écart le plus fréquent dans le plateau terminé.
Les grilles sont générées dans votre navigateur. Rien de ce que vous jouez n'est envoyé où que ce soit.