View Single Post

Hovergame's Avatar


Hovergame
11.02.2012 , 07:10 PM | #16
Mathématiquement, ce problème est du même acabit que le Rubik's Cube, en plus simple. Ces 2 problèmes se situent dans une domaine encore plus vaste : soit G un groupe fini dont on donne les générateur et g un de ses éléments; donner l'inverse de g en fonction des générateurs du groupe.

Parlons un peu math et algorithmique
Le fait qu'on puisse allumer chaque pylône indépendamment prouve qu'il y a 2^9 positions distinctes. en regardant le problème sous forme d'un groupe, omme tout élément est d'ordre 2 et commutatif, tu prouves qu'il existe des positions qui demandent au moins 9 mouvements.Tu prouves aussi l'unicité (à permutation des éléments prêts) de la solution (comme la décomposition en nombres premiers).

Question algorithmique, non tu n'es pas en O(n) à moins que tu ne me prouve que modifier un unique pylône est en O(1), et ça ne me semble pas le cas (au pifomètre, ça me semble du O(n), donc ton algo est en O(n²)).

Au final, ta solution est optimale mathématiquement (par unicité à permutation près et parle fait que tu n'as pas de répétitions), mais l'algorithme n'est sûrement pas en complexité optimale (ça reste à montrer, et c'est trop difficile ppur moi). Et de plus, déjà en 5x5, il existe des positions sans solutions (et le nombre de cas de base n'est plus 3 mais 6), donc je doute que ton approche se généralise