Le jeu Icosien

Le résultat

Fichier Flash :

Icosien est aussi disponible en version mobile, sans publicité et avec encore plus de niveaux !

Explications

Ce jeu a fait l'objet de plusieurs publications ; elles sont listées ici.

Articles sur l'algorithmie derrière le jeu :

Articles sur des petites astuces de programmation AS3 :

Articles sur le jeu :

Règle du jeu

La règle est expliquée dans le jeu. Vous la retrouverez ici :

Première partie : Euler.
Reproduisez le motif gris d'un seul mouvement de souris, sans repasser deux fois sur le même trait (mais les croisements de fil sont autorisés).
Double cliquez pour recommencer !
Ayez des mouvements amples de souris, imaginez que vous tirez un fil derrière vous : pas besoin de frôler les clous !
Pour commencer à jouer, entraînez-vous sur la flèche ci-dessous.
Cliquez sur un clou pour attacher votre corde et commencer.
Seconde partie : Hamilton.
Vous avez maintenant fini l'échauffement, passons à la partie intéressante !
Changement de règle : il faut passer une et une seule fois sur chaque clou, en utilisant uniquement les traits disponibles pour joindre deux clous (mais vous n'êtes pas obligés de passer sur tous les traits).
Contrainte supplémentaire : il faut commencer et finir sur le même point.

À propos du concept

Cette animation Flash met en jeu deux concepts mathématiques extraits de la théorie des graphes.

Pour rappel, un graphe est un ensemble constitué de points (nommés « n?uds ») et de liens entre ces points (« arêtes »). Notons qu'un graphe mathématique peut être placé n'importe comment, les dispositions choisies servant simplement à faciliter la compréhension du niveau ou à berner l'utilisateur pour complexifier artificiellement le niveau (après tout, on pourrait afficher tous les n?uds dans l'ordre pour faciliter le problème ! )

Première partie : graphes eulériens

Dans la première partie (une dizaine de niveaux) c'est le concept de graphe eulérien qui est utilisé.
Pour expliquer clairement, un graphe est dit « eulérien » si l'on peut le dessiner d'un seul coup sans lever le stylo et en finissant sur le point de départ.
Pour Icosien, nul besoin de finir au même point que le départ (ce qui facilite la chose) : on ne peut donc pas dire qu'il s'agit d'une recherche de cycle d'Euler.

Vous l'aurez remarqué en jouant, le point de départ est important. Effectivement, il faut commencer par un n?ud qui a un nombre impair d'arêtes (s'il y en a). Pourquoi ? Parce que un passage sur le n?ud enlève deux itinéraires à chaque fois : l'arête par laquelle on arrive, et l'arête par laquelle on repart. Pour les n?uds incidents à un nombre pair d'arêtes (2n par exemple), on passera donc n fois autour du n?ud. Mais pour les n?uds incidents à un nombre impair (3 arêtes par exemple), un passage réduira à 1 le nombre d'arête disponible? ce qui force donc à prendre ce n?ud pour départ, ou pour arrivée.

À quoi ça sert, un graphe eulérien dans la vraie vie ? Imaginez par exemple que vous soyez responsables de la distribution du courrier dans une ville. Pour éviter le temps perdu, il faudrait idéalement trouver le chemin qui emprunte toutes les routes une seule fois, et revient au point de départ. Et voilà un graphe eulérien !

Mathématiquement, les graphes eulériens sont assez simples à analyser et sont l'objet de peu de recherches. On connait plusieurs algorithmes pour trouver rapidement un cycle eulérien ; le plus élégant étant sans conteste l'algorithme de Fleury.

Seconde partie : graphes hamiltoniens

Dans la deuxième partie, la règle du jeu change : on ne demande plus de passer une fois sur chaque arête, mais de passer une fois sur chaque n?ud (en empruntant uniquement certaines arêtes, sinon c'est bien entendu évident ! ).
Plus complexe encore, puisqu'il faudra aussi finir sur le point de départ pour obtenir un cycle.
Ce type de parcours s'appelle un cycle hamiltonien. Notons d'ailleurs qu'un même graphe peut avoir plusieurs cycles hamiltoniens !

Cette fois, le point de départ n'a aucune importance : c'est presque aussi incohérent que de demander où commencer à dessiner un cercle ! Cependant, intuitivement on préfère commencer sur les n?uds qui ont beaucoup d'arêtes incidentes ? ce qui est idiot, mieux vaut se réserver ces carrefours pour sortir d'une situation bloquée.

Et dans la vraie vie, un graphe hamiltonien ? Les graphes hamiltoniens peuvent être utiles pour rechercher le plus long cycle / chemin dans un graphe (reconnaissance d'images). Plus prosaïquement, prenez un voyageur qui décide de visiter certaines villes (les n?uds) dont il connait les distances entre elles (la longueur des arêtes) : le cycle hamiltonien est un cas particulier de cette recherche.

Mathématiquement, on ne sait pas calculer rapidement un cycle hamiltonien : grossièrement, on est obligé d'examiner chaque possibilité avec un ordinateur. On peut faire des petites optimisations, mais rien de probant. En fait, la recherche d'un cycle hamiltonien (ou d'un chemin hamiltonien, puisque mathématiquement la complexité est similaire) est un problème dit NP-complet, un domaine de recherche sur lequel les plus grands scientifiques s'arrachent actuellement les cheveux ;)
Et pour complexifier le tout, même l'ajout de propriétés habituellement simplificatrices (par exemple, graphe planaire) laisse le problème NP-complet.

Graphes eulériens vs. graphes hamiltoniens

À première vue, les deux concepts sont très similaires : passer une seule fois sur chaque élément. Mais en fait, les deux problèmes sont bien distincts, et on peut avoir de tout : un graphe hamiltonien et eulérien, un graphe eulérien et non hamiltonien, un graphe hamiltonien et non eulérien, ou un graphe qui n'est ni hamiltonien, ni eulérien.

De plus, la recherche d'un cycle eulérien ou hamiltonien ne fonctionne pas du tout selon le même principe, et comme je le soulignais la recherche hamiltonienne continue de défier les chercheurs !

Graphes utilisés

Cette fois, je n'ai que peu innové et je me suis inspiré de graphes existants aux propriétés bien connues.
On retrouvera donc :

La flèche du premier tutoriel, pas très originale ; )
La Maison, ou enveloppe, bien connue sur les bancs de l'école primaire « dessine-ça sans lever le crayon », l'astuce étant bien évidemment de commencer en bas.
Labelled Eulergraph
Cuboctahedral Graph
Graphe d'explication algorithme de Fleury modifié pour le complexifier
Cocktail Party Graph
Des étoiles plein la tête !
Small Rhombicuboctahedral Graph
Doyle Graph ; avec une petite subtilité : il faut bien choisir son point de départ !
La flèche du second tutoriel, qui est hamiltonienne mais pas eulérienne (pour forcer les gens à assimiler la nouvelle règle ! )
Moser Spindle
Franklin Graph
Dodecahedron
Grötzsch graph
Graphe Hypohamitonien de Lindgren ; un graphe hypohamiltonien est un graphe qui n'est pas hamiltonien, mais dont la suppression d'un n?ud (n'importe lequel) le rend hamiltonien. Ici, j'ai supprimé le n?ud en haut du cercle.
First Blanusa Snarks : lui aussi est hypohamiltonien, j'ai viré un n?ud.
Pappus Graph : non eulérien, non planaire? mais hamiltonien !
McGee graph modifié (suppression d'arêtes)
60 Graph Thomassen hypohamiltonien, 60 sommets, 99 arêtes (moins dans le jeu, puisque j'en ai supprimé un sommet) !
Tauraso's graph : un graphe d'exemple présentant un nouvel algorithme pour trouver des cycles hamiltoniens.

Historique

Démarrage du codage : 1/06/10
Version α : 1/06/10 (Testeurs : Licoti, Vertigo [un peu !])
Version β : 5/06/10 (Testeurs : Licoti, Vertigo)
Version RC1 : Futur (Testeurs : Licoti, Vertigo, Serge, Bom, Lagile, Malphas, Ugo, MyGB, Goulu, Grebnetor, Jolo2, Lagile, Goulu, rastagong)

Remerciements

Merci à Licoti qui s'est beaucoup investi dans le jeu et qui a fait les graphismes, au Dr Goulu qui a bien participé aux tests, et à Yannish qui a aidé pour la traduction anglaise.

Le code

À propos du code

Je commence à bien m'amuser avec Actionscript 3, et le code est... disons, pas trop sale ;)

Afin d'éviter l'engorgement du serveur, le code est décentralisé sur une page externe.