View Single Post

Dici's Avatar


Dici
10.11.2012 , 04:40 AM | #3
Chacun des 9 pylônes a 2 états : allumé ou éteint. Si on veut représenter harmonieusement le montage, on choisit la forme d'un octogone dont chaque sommet est un pylône, chaque arête une connexion, et le centre est également un pylône relié à quatre sommets deux à deux non consécutifs.

Le but est, à partir d'une configuration quelconque d'états (allumé/éteint) de l'ensemble des pylônes, d'arriver à tous les allumer. Dans le jeu, quand on les allume tous ça alimente une tourelle qui fait feu sur un vaisseau qui se crash, et on doit récupérer quelque chose dessus.

En fait, avec ce que j'ai expliqué, on peut généraliser le problème en imposant d'accéder à partir d'un état quelconque à un autre état quelconque.

PS : je me rends désormais compte qu'on peut généraliser l'alphabet à tout polygone ayant un nombre pair > 4 de sommets (+ le centre où on garde toujours un pylône). Si on considère que ce problème est de taille 2(n+3), alors la résolution se fait en O(n) affectations. Pour 4 sommets l'alphabet n'a que deux lettres.