Inondez-le !

« Flood It » est un jeu de réflexion stratégique qui se joue sur une grille composée de cases dont la couleur est déterminée aléatoirement. Le joueur contrôle la case située en haut à gauche et, à chaque tour, en change la couleur. Toutes les cases adjacentes de la même couleur que la case d'origine (la « vague ») adoptent la nouvelle couleur, élargissant ainsi la zone inondée. Le but est d'inonder l'ensemble du plateau d'une seule couleur en un nombre limité de coups. Le jeu utilise généralement une grille de 14x14 avec 6 couleurs et autorise environ 25 coups.

Règles

1. Une grille carrée (généralement de 14x14) est remplie de cases colorées au hasard, à l’aide de 6 couleurs.
2. Le joueur commence en contrôlant la case en haut à gauche.
3. À chaque tour, le joueur choisit l’une des couleurs disponibles.
4. La case en haut à gauche et toutes les cases qui lui sont reliées (la « zone d’inondation ») prennent la couleur choisie.
5. Par « reliées », on entend les cases de la même couleur qui sont adjacentes horizontalement ou verticalement à la zone d’inondation, formant ainsi un groupe contigu.
6. La zone d’inondation s’agrandit à chaque fois qu’elle absorbe des cases adjacentes de la nouvelle couleur choisie.
7. Le but est de rendre l’ensemble du plateau d’une seule couleur en respectant la limite de coups.

Stratégies

• Maximiser l’absorption : choisissez la couleur qui permettra d’absorber le plus grand nombre de nouvelles cases dans la zone d’inondation. Observez la limite de la zone actuelle et comptez le nombre de cases de chaque couleur qui lui sont adjacentes.
• Anticipez : au lieu de vous contenter d’optimiser le coup actuel, anticipez deux ou trois coups à l’avance. Une couleur qui n’absorbe que peu de cases aujourd’hui pourrait permettre une absorption bien plus importante au tour suivant.
• Privilégiez les couleurs rares : si une couleur n’apparaît que quelques fois sur le plateau et que ces cellules sont proches de la limite de la zone d’inondation, absorbez-les rapidement. Cela réduit le nombre de couleurs distinctes restantes.
• Étendez-vous vers les bords : le coin inférieur droit est le point le plus éloigné du point de départ. Planifiez votre expansion de manière à atteindre rapidement les coins éloignés plutôt que de saturer les zones proches.
• Stratégie du « pont » : il est parfois plus efficace de choisir une couleur qui crée un « pont » vers un groupe éloigné de cellules de la même couleur plutôt que d'absorber le plus grand groupe adjacent.
• Comptez les coups restants : s’il vous reste N coups et qu’il y a encore N couleurs sur le plateau, vous devez absorber au moins une couleur par coup. Planifiez en conséquence.

Flood It a fait son apparition à la fin des années 2000 sous la forme d'un jeu occasionnel sur le Web et sur mobile, avec plusieurs versions indépendantes apparues entre 2006 et 2010. Son origine exacte est difficile à déterminer, car le concept a été développé indépendamment par plusieurs programmeurs. L'une des premières versions les plus connues était une application Facebook qui a attiré des millions d'utilisateurs vers 2008-2009.

Les mécanismes sous-jacents du jeu s’inspirent du concept mathématique du « remplissage par inondation », un algorithme fondamental en infographie utilisé pour remplir des zones contiguës de même couleur (l’outil « pot de peinture » dans les éditeurs d’images). Cet algorithme remonte aux débuts de l’infographie, dans les années 1960 et 1970. « Flood It » transforme essentiellement cet algorithme en jeu en amenant le joueur à choisir stratégiquement la couleur de remplissage.

Du point de vue de la complexité algorithmique, « Flood It » a fait l’objet de nombreuses études de la part des chercheurs. En 2010, Clifford, Jalsenius, Montanaro et Pilkington ont démontré que déterminer le nombre minimal de coups nécessaires pour remplir un plateau est un problème NP-difficile, même lorsqu’on se limite à seulement 3 couleurs. Cela signifie que trouver la solution optimale pour de grands plateaux est intraitable d’un point de vue informatique, et que le jeu pratique repose sur des stratégies heuristiques. Les algorithmes « gloutons », qui choisissent systématiquement la couleur absorbant le plus grand nombre de cases, donnent des résultats raisonnablement bons mais ne sont pas optimaux.

Le jeu a été largement cloné et adapté sur différentes plateformes, avec des versions disponibles sur iOS, Android et le Web sous divers noms. Ses règles simples, sa progression visuelle satisfaisante et sa profondeur stratégique en font un jeu occasionnel dont la popularité ne se dément pas. Parmi les variantes, on trouve des grilles de tailles différentes, des grilles hexagonales, ainsi que des versions où le joueur peut commencer depuis n’importe quelle case plutôt que uniquement depuis le coin supérieur gauche.