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 cube entièrement d'une couleur ou alors un cube composé de chaque couleur.

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çons en le faisant pivoter.

Comme on peut choisir, n'importe quelle des 6 faces de chaque cube pour être devant et qu'on peut ensuite la faire pivoter de quatre façons pour choisir les faces du haut/bas on arrive à 24 agencements diffèrent par cube.

• Prenons pour exemple ce cube, la face de devant est bleu et est fixe mais on peut encore mettre 4 faces sur la faces du dessus avant de fixer ce cube (par exemple la face jaune que l'on voit sur la droite peut être mis au dessus sans changer la face de devant).

• La ligne jaune doit contenir toutes les couleurs et la bleu aussi sang bouger les cubes et pareille pour derrières.

Cela ne parait pas comme ça, mais avec nos 4 cubes nous sommes déjà rendu à 331 000 combinaisons possibles. (Il peut évidemment avoir plusieurs combinaisons gagnantes.).

• Pour 5 cubes il y a donc 7,9 millions de combinaisons possibles.(dans le cas où on rajouterait autant de couleurs que de cube)

• Pour 10 cubes, on passe à 69 miles milliards de combinaisons.

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 agencements gagnants.

On le réalise donc en Python !

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

Quand on voit le nombre grandissant de combinaisons, on a envie de crée un programme informatique afin de toutes les essayer et de nous renvoyer uniquement les agencements de cubes qui seraient 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érentes fonction qu'on a vue.

Mais les résultats ne sont bien pas affichés et on crée donc une dernière fonction qui elle affiche joliment les informations.

• La fonction affiche

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

NP complet

On remarque rapidement que le programme prend énormément de temps quand il y a un trop grand nombre de cubes, pour 4 cubes ç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 va maintenant parler de ce qu'est la NP complétude.

NP est une classe qui contient les problèmes faciles à résoudre, Instant Insanity en fait donc parti. À l'intérieur de cette classe, se trouve la classe P, qui contient les problèmes qui sont faciles à 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 dira qu'ils sont faisables en temps polynomial !

Toujours à l'intérieur de NP, il y a la classe des NP complets qui regroupe tous les problèmes difficiles à résoudre, mais pour autant facile à vérifier, c'est là que se 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 sudokus en temps polynomial.

Or personne n'a encore réussi. Et la majorité des chercheurs 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 notion de complexité des algorithmes.