Instant Insanity

Définition :

• Instant Insanity est le nom donné par Parker Brothers à leur version de 1967 d'un puzzle qui existe depuis l'Antiquité.

Ce problème se présente de la façon suivante :

• Vous avez 4 cubes disposez devant vous et sur chacun d'eux se trouve 4 couleurs (autant de couleurs que de cubes).
  • Dans la version de Parker Brother les couleurs était disposée sur les cubes de façon précise.

Dans notre cas il sera possible d'avoir un cubes entièrement d'une couleur ou alors un cube composé de chaque couleurs.

Les REGLES

Il faut aligner les 4 cubes de façon à ce que sans bouger les cubes, les faces de devant, derrière, en haut et en bas contiennent exactement une fois chaque couleurs.

Le Problème

Chaque cube contient 6 faces et si on fixe la face de devant face à nous on peut encore orienter le cube de quatre façon en le faisant pivoter. Comme on peut choisir n'importe qu'elle des 6 faces de chaque cube pour être devant et qu'on peut ensuite la faire pivoter de quatre façon pour choisir les face du haut/bas on arrive à 24 agencement diffèrent par cube. Cela ne parait pas comme ça mais avec nos 4 cubes nous sommes déjà rendu à 331 000 combinaison possible. (Il peut évidement avoir plusieurs combinaisons gagnantes).

• Pour 5 cubes il y a donc 7,9 millions de combinaisons possibles.(Dans le cas ou on rajouterais autant de couleurs que de cube)
• Pour 10 cubes on passe à 69 miles milliards de combinaison.

On retrouve rapidement confronté à un problème, la difficulté à savoir résoudre ce simple puzzle.

Le programme informatique

Quand on voit le nombre grandissant de combinaison on a envie de crée un programme qui prendrait en entrée les cubes et nous renverrait uniquement les agencement gagnant. On le réalise donc en Python !

On commence par imaginé les cubes comme des listes de faces qu'on vas pouvoir parcourir, on met ensuite ces cubes dans une liste de cube pour généraliser notre programme et qu'il puissent prendre autant de cubes que l'on souhaite.

Quand on voit le nombre grandissant de combinaisons on a envie de crée un un programme informatique afin de toutes les essayer et de nous renvoyer uniquement les agencement de cube qui serait gagnant.

• Dans notre cas le programme marche pour n cubes n couleurs mais pour l'exemple le programme vas prendre 5 cubes et 5 couleurs en entrées.
• On commence par crée nos liste qui seront envoyée en entré :

• On crée ensuite une fonction qui génère un pattern.

• Il s'explique en se disant que le premier élément du tuple et la face devant nous si on a (0,1) cela voudra dire la face 0 est devant nous et la face 1 et au dessus. On pourra remarquer que la face 3 n'arrive jamais au dessus de la 1 et c'est logique car 3 et la face opposé de la face 1.
• On crée aussi une fonction couleur qui nous renvoie la couleur d'une face donnée.

• On a maintenant un programme qui marche et qui appelle les différente fonction qu'on a vue.

Mais les résultat ne sont bien affiché et on crée donc une dernière fonction qui elle affiche joliment les information.

• La fonction affiche

• La première ligne et la position de chaque cube come vue précédemment. Les lignes suivante sont les les couleurs sur chaque lignes. Et après toutes les combinaison nous avons le nombre d'itération et le nombre de possibilité de notre liste de cube.

NP complet

On remarque rapidement que le programme prend énormément de temps quand il y a un trop grand nombre de cube, pour 4 cube ça ne dure que quelques secondes alors que pour 6 on en a pour 1h55min.

• Si on s'intéresse à la complexité de notre algorithme.
  • On remarque qu'il est en $O(24^{n})$

• Courbe du nombre d'itérations en fonction du nombre de cube.

On vas maintenant parler de ce qu'est la NP complétude.

NP est une classe qui contient les problème facile à résoudre, Instant Insanity en fait donc parti. A l'intérieur de cette classe se trouve la classe P, qui contient les problèmes qui sont facile à résoudre et facile à vérifier. Comme par parcourir une liste ou encore trouver le plus grand élément d'une liste.

• facile à résoudre ne vas pour autant dire faisable en temps convenable, par exmple parcourir une liste de plusieurs milliards d'éléments un à un.

On diras qu'il sont faisable en temps polynomial !
Toujours à l'intérieur de NP il y a la classe des NP complet qui regroupe tout les problèmes difficiles à résoudre mais pour autant facile à vérifier c'est la que ce trouve Instant Insanity.

• Elle contient aussi SAT/Partitions ou encore le problème du sac à do ou le sudoku.

La particularité des problèmes NP complet est que chacun est plus difficile ou égal aux autres. Ce qui fait que si on a une bibliothèque python qui résout un seul des problèmes de cette classe en temps polynomial, alors on peut tous les résoudre en changeant simplement l'entrée du programme, ainsi les cubes peuvent résoudre le problème de satisfiabilité ou encore les sudoku en temps polynomial. Or personne n'a encore réussie. et la majorité des chercheur du domaine pense que ce n'est pas possible.

• Malgré la puissance et l'efficacité de certains SAT Solver en python compilé en C.

La résolution en temps polynomial d'un seul problème NP complet pourrait bouleverser une partie de la cryptographie moderne (décomposition en facteurs premiers) et changerait énormément la façon de comprendre la notions de complexité des algorithme.