Bonsai Ninja

Elite bonsai artist, you have finally created your masterpiece: a perfectly harmonious bonsai.  One night, a VERY BAD PERSON has completely destroyed your bonsai by rearranging the branching pattern. Can you find the perfect harmony once again?

Il s'agit d'un jeu de casse-tête où l'on doit transformer un arbre (au sens mathématique) d’un état initial à un état final en un minimum de mouvements. L'opération permise est celle de l'élagage et et re-grafting d'un sous-abre (en angais : subtree prune and regrafting ou SPR) :

L'opération ci-dessus se fait en deux temps. D'abord on sélectionne une branche et on la coupe (clic droit). Ensuite on prend la racine du sous-arbre détaché et la déplace vers une autre branche (drag and drop). Cette opération modifie effectivement les motifs de branchement de l'arbre.

On peut par ailleurs faire l'opération de "flip" qui inverse les relations gauche-droite des sous-arbres à un noeud donné (double clic). Cette opération ne modifie pas les motifs de branchement de l'arbre et n'incrémente donc pas le compteur de mouvements.

Le réarrangement d'arbre est un problème étudié par les chercheurs en algorithmique (https://en.wikipedia.org/wiki/Tree_rearrangement). L'intérêt de résoudre un tel problème vient de ses nombreuses applications dans le domaine de la biologie évolutive et la phylogénétique : l'arbre représente alors l'histoire évolutive des gènes ou des espèces.

Trouver la réponse exacte (i.e. le nombre minimum de mouvements) étant un problème difficile, il existe des algorithmes heuristiques qui, même s'ils ne garantissent l'optimalité de la réponse, trouvent une réponse efficacement et suffisamment proche du l'optimum.

Certains de ces algorithmes heuristiques imitent le process mental d'un être humain qui essaye de résoudre le puzzle. Par exemple, on peut se demander si l'arbre du départ et l'arbre d'arrivé partagent déjà une partie similaire, dans laquelle on peut considérer a priori qu'il n'y aura pas besoin de couper des branches.

Created by Hélio Wang

Source code: https://bitbucket.org/HelioW/bonsaininja

sudo chmod +x BonsaiNinja && ./BonsaiNinja