Rubik’s cube - Complexité du problème

Rubik’s cube  - Complexité du problème

Rubik’s cube  - Mécanisme interne du cube

Rubik’s cube  - Complexité du problème

Le nombre de positions différentes est de 8! × 3⁷ × 12! × 2¹⁰ = 11 × 7² × 5³ × 3¹⁴ × 2²⁷ = 43 252 003 274 489 856 000 (c’est-à-dire plus de 43 milliards de milliards de combinaisons), dont 1 seule correspond au cube fini. Pour donner une idée du nombre de combinaisons, en passant en revue 1 milliard de combinaisons différentes par seconde, cela prendrait plus de 1 200 ans pour les épuiser toutes!

Cela se calcule comme suit :

1. Chaque arête peut prendre deux orientations possibles. Étant donné qu’on ne peut pas changer l’orientation d’une arête seule, l’orientation de toutes les arêtes fixe l’orientation de la dernière. Cela nous donne 2¹¹ possibilités d’orientation des arêtes.
2. Chaque coin a trois orientations possibles. De même, on ne peut pas retourner un coin seul, l’orientation du dernier coin est donc fixée par les autres. Cela nous donne 3⁷ possibilités d’orientation de coins.
3. Les arêtes peuvent s’interchanger entre elles, ce qui nous donne 12! possibilités de positionnements pour les arêtes.
4. Les coins peuvent s’interchanger entre eux. Cela fait 8! possibilités.
5. Mais il existe un problème dit de parité : on ne peut échanger juste deux coins ou deux arêtes (mais on peut interchanger deux coins ET deux arêtes). La position des arêtes et des premiers coins fixe donc la position des 2 derniers coins et il faut donc diviser le résultat par deux.

Ce qui donne bien : 8! × 3⁷ × 12! × 2¹⁰ = 43 252 003 274 489 856 000

Les centres ne sont pas considérés dans ce calcul, car ce sont eux qui nous servent de points de repère.

Des versions modifiées du cube original, par exemple avec un motif imprimé sur ses surfaces, nécessitent, elles, une position spécifique de ces carrés centraux qui nous oblige à considérer l’orientation des centres. Chaque centre a quatre orientations possibles, l’orientation du dernier est comme d’habitude fixée par celle des précédents (à un demi-tour près) et il faut donc multiplier le nombre de positions du Rubik’s cube par 2*4⁵ = 2048.

Rubik’s cube  - Méthodes de résolution

On peut tenter de chercher la solution au hasard, mais étant donnée l’espérance de vie humaine, ce n’est pas une solution viable. Il a donc fallu inventer des méthodes pour résoudre le cube. La légende veut qu’Ernő Rubik lui-même y ait passé un mois.

On peut manipuler le cube méthodiquement, selon des séquences de mouvements prédéfinies qui permettent de remonter le cube progressivement, c’est-à-dire de déplacer et d’orienter les petits cubes par étapes, sans perdre les fruits de son travail préalable.

Rubik’s cube  - Complexité du problème - Mécanisme interne du cube

voir aussi  CATEGORIES FRANCOTHAI