Galaxies (Tentai Show)

« Galaxies », également connu sous le nom de « Tentai Show » ou « Spiral Galaxies », est un casse-tête de grille dans lequel le joueur divise une grille rectangulaire en régions, chacune contenant exactement un point (le « centre de la galaxie »). Chaque région doit présenter une symétrie de rotation autour de son point central : si l’on fait pivoter la région de 180 degrés autour de ce point, elle reste exactement identique. Les points peuvent être placés au centre des cases, sur leurs bords ou à leurs intersections, ce qui permet de créer des régions de formes et de tailles variées.

Règles

1. La grille contient des points placés à différents emplacements (au centre des cases, sur les bords ou aux intersections).
2. Divisez l'ensemble de la grille en régions de manière à ce que chaque case appartienne à une seule et même région.
3. Chaque région contient exactement un point.
4. Chaque région doit présenter une symétrie de rotation de 180 degrés autour de son point. Autrement dit, pour chaque case de la région, la case située du côté opposé au point (à égale distance, en symétrie par rapport au point) doit également se trouver dans la région.

Stratégies

• La position du point détermine la taille minimale : un point situé au centre d’une case nécessite au moins cette case. Un point situé sur un bord entre deux cases nécessite au moins ces deux cases. Un point situé à une intersection nécessite au moins les quatre cases environnantes.
• Contrainte de symétrie : pour chaque case que vous attribuez à une région, vous devez également attribuer sa contrepartie de rotation par rapport au point de la région. Cela signifie que les régions comportent toujours un nombre pair de cases (à moins que le point ne se trouve au centre d’une case, ce qui donne un nombre impair).
• Propagation des limites : si une case située au bord de la grille appartient à une région, sa contrepartie symétrique doit également se trouver à l’intérieur de la grille. Les cases proches des bords ont souvent des possibilités limitées.
• Exclusion des voisins : si deux points sont proches l’un de l’autre, leurs régions ne peuvent pas se chevaucher. Déterminez la frontière entre elles en examinant quelles cellules chaque point peut revendiquer tout en conservant la symétrie.
• Expansion à partir d’un point : partez de chaque point et déterminez quelles cellules il doit revendiquer. Si un point est proche d’un coin, la contrainte de symétrie limite fortement la forme de la région.
• Espace restant : À mesure que les régions sont déterminées, les cellules restantes non attribuées doivent appartenir aux points voisins. Si un seul point peut revendiquer symétriquement une cellule, cette attribution est imposée.

Le jeu « Galaxies » a été inventé par Nikoli, l'éditeur japonais de jeux de réflexion, et est apparu pour la première fois dans ses magazines de jeux en 2001 sous le nom japonais « Tentai Show » (qui se traduit approximativement par « spectacle astronomique » ou « spectacle céleste », évoquant l'image des galaxies spirales). Le nom anglais « Galaxies » ou « Spiral Galaxies » a été adopté pour le public international, en référence à la ressemblance visuelle entre ces zones symétriques et la forme des galaxies spirales.

Ce casse-tête est un bel exemple de la philosophie de conception de Nikoli : une seule contrainte élégante (la symétrie de rotation) donne lieu à de riches défis logiques. Le placement des points sur les bords et aux intersections (et pas seulement au centre des cases) a été un choix de conception particulièrement astucieux, car il crée des zones de tailles et de formes variées qui s’imbriquent de manière complexe.

Galaxies a été présenté lors du Championnat du monde de casse-tête et est l’un des favoris des amateurs de casse-tête de compétition en raison des exigences qu’il impose en matière de raisonnement visuel et spatial. Contrairement à de nombreux casse-têtes sur grille qui reposent sur des chiffres et l’arithmétique, « Galaxies » est purement géométrique, ce qui oblige le joueur à réfléchir à la symétrie et aux formes.

Ce casse-tête a été inclus dans la « Portable Puzzle Collection » de Simon Tatham sous le nom de « Galaxies », ce qui a contribué à le faire connaître à un public plus large. Il est depuis apparu dans diverses applications de casse-têtes et sur des plateformes en ligne dédiées. Ce casse-tête a également suscité l’intérêt des chercheurs en informatique, car la complexité algorithmique de la résolution d’instances générales de Galaxies a fait l’objet d’études : le problème est NP-complet, bien que les casse-têtes bien conçus puissent être résolus par pure déduction.