Comment résoudre de manière optimale l'énigme du comblement des crues ?

Question

J'aime jouer au jeu de puzzle Flood-It, qui peut être joué en ligne sur le site :

https://www.lemoda.net/javascript/flood-it/game.html

Il est également disponible sous forme de gadget iGoogle. Le but est de remplir l'ensemble du tableau avec le moins de remplissages successifs.

J'essaie d'écrire un programme qui puisse résoudre ce puzzle de manière optimale. Quelle est la meilleure façon d'aborder ce problème ? Idéalement, je veux utiliser le A* mais je n'ai aucune idée de ce que devrait être la fonction estimant le nombre d'étapes restantes. J'ai écrit un programme qui a effectué une recherche par force brute en profondeur 4 pour maximiser la surface remplie. Il a raisonnablement bien fonctionné et m'a battu dans la résolution du puzzle, mais je ne suis pas complètement satisfait de cet algorithme.

Des suggestions ? Merci d'avance.

Answer 1

La réponse de Smashery peut être légèrement modifié. Pour l'estimation du nombre total de coups, s'il y a 'k' couleurs à la distance maximale, ajoutez 'k-1' à l'estimation du nombre de coups.

Plus généralement, pour chaque couleur, on considère la distance maximale à laquelle la couleur peut être effacée. Cela nous donne un dictionnaire qui met en correspondance certaines distances maximales avec un nombre non nul de couleurs qui peuvent être éliminées à cette distance. Additionnez la valeur 1 de toutes les clés et ajoutez-la à la distance maximale pour obtenir une estimation du nombre de coups.

De plus, il y a certains cas libres. Si, à un moment donné, nous pouvons éliminer une couleur en un seul coup, nous pouvons jouer ce coup sans tenir compte des autres coups.

Answer 2

Voici une idée pour implémenter le graphique pour supporter L'heuristique de Smashery .

Représentez chaque groupe de carrés contigus de même couleur dans un ensemble disjoint et une liste de groupes de carrés adjacents. Un remplissage par inondation fusionne un ensemble avec tous ses ensembles adjacents, et fusionne les listes d'adjacence. Cette structure de graphe implicite vous permettra de trouver la distance entre le coin supérieur gauche et le nœud le plus éloigné.

Answer 3

Je pense que vous pourriez considérer le nombre de carrés qui correspondent ou non à la couleur actuelle. Ainsi, votre mesure heuristique de la "distance" serait le nombre de carrés sur le plateau qui ne sont -pas- de la même couleur que la couleur choisie, plutôt que le nombre de pas.

Answer 4

Une heuristique naïve pourrait être d'utiliser le nombre de couleurs restantes (moins 1) - ceci est admissible car il faudra au moins autant de clics pour effacer le tableau.

Answer 5

Je ne suis pas certain, mais je suis presque sûr que cela pourrait être résolu de manière avide. Vous essayez de réduire le nombre de champs de couleur à 1, donc réduire plus de champs de couleur plus tôt ne devrait pas être moins efficace que réduire moins plus tôt.

1) Définir une collection de groupes existants de même couleur.

2) Pour chaque collection, comptez le nombre de collections voisines par couleur. Le plus grand nombre de collections voisines d'une même couleur est le poids de cette collection.

3) Prenez la collection avec le plus grand nombre de voisins d'une même couleur, et remplissez-la de cette couleur. Fusionnez les collections, et mettez à jour le tri pour toutes les collections affectées par la fusion (tous les nouveaux voisins de la collection fusionnée).

Globalement, je pense que le calcul devrait se faire en O(n log n), où n est le nombre de pixels et où le log(n) provient uniquement du maintien de la liste triée des poids.

Je ne suis pas sûr qu'il soit nécessaire d'établir un critère d'égalité lorsque plusieurs champs ont le même poids. Peut-être que la couleur commune au plus grand nombre de groupes sur la carte est déterminante.

Quoi qu'il en soit, notez que le but du jeu est de réduire le nombre de champs de couleurs distinctes et non de maximiser le périmètre, car différents schémas de couleurs peuvent parfois faire d'un champ plus grand un choix sous-optimal. Considérons le champ :

3 3 3 3 3

1 1 1 1 1

1 1 1 1 1

2 2 2 2 2

1 2 2 2 2

La couleur 1 a le plus grand périmètre, quelle que soit la mesure, mais la couleur 2 est le choix optimal.

EDIT>

Grattez ça. L'exemple :

3 1 3 1 3

1 1 1 1 1

1 1 1 1 1

2 2 2 2 2

1 2 2 2 2

Invalide mon propre algorithme gourmand. Mais je ne suis pas convaincu qu'il s'agisse d'une simple traversée de graphe, puisque le passage à une couleur partagée par 2 voisins visite 2 et non 1.

L'élimination des couleurs devrait probablement jouer un certain rôle dans l'heuristique.

1) Il n'est jamais correct de remplir avec une couleur qui n'est pas déjà sur le graphique.

2) S'il y a un champ de couleur avec une couleur unique, au moins un remplissage sera nécessaire pour lui. Il ne peut pas être regroupé avec d'autres remplissages. Je pense que cela signifie qu'il est prudent de le remplir plus tôt que tard.

3) L'algorithme gourmand pour le comptage des champs voisins a du sens pour une carte à 2 couleurs.