Résolution du cube 2x2

Remarques

On peut remarquer que tourner la face droite du cube est equivalent à tourner celle de gauche dans l'autre sens. De même pour toutes les faces.

On peut alors restreindre l'ensemble des actions à trois faces (disons : Droite, Bas et Derrière) avec pour chacune :

1. Sens horaire
2. Demi-tour
3. Sens anti-horaire

On peut alors remarquer que le cube de devant, en haut à gauche est constament fixe (ce qui élimine une variable pour notre problème).

Notations

Les étapes

On note $t_{max}$ le nombre d'étapes pour résoudre le Rubik's Cube

On note $T = {0, ..., t{max}}$ et $T^* = {1, ..., t{max}}$

Les actions

On note $a_{f, d}(t)$ l'action de tourner la face $f \in F = {Right, Bottom, Back}$ dans la direction $d \in D = {Clockwise, Halfturn, Counterclockwise}$ à l'étape $t \in T^*$

Le cube

Le Rubik's Cube est representé par un ensemble de cube ayant un $id \in C = {1, ..., 7}$ et une orientation $o \in O = {0, 1, 2}$ (l'orientation $o = 0$ étant celle lorsque le Rubik's Cube est fini)

On note $x{c, id}(t)$ la variable booléenne indiquant si le cube ayant l'identifiant $id \in C$ est sur la position $c \in C$ à l'étape $t \in T$ (le cube étant à la bonne place ssi $x{id, id}(t)$)

Et $\theta_{c, o}(t)$ la variable booléenne indiquant si le cube à la position $c \in C$ est dans l'orientation $o \in O$ à l'étape $t \in T$

Fonctions rotation

On note : $r_x : F \times D \times C \rightarrow C$, la fonction qui à chaque position associe la position après la rotation

On note : $r_\theta : F \times D \times C \times O \rightarrow O$, la fonction qui à chaque couple de position orientation associe l'orientation après la rotation

Autres

Par abus de notation, on notera $c' = rx(f, d, c)$ et $o' = r\theta(f, d, c, o)$

Pour chaque face $f \in F$, on notera $C_f$ l'esemble des cube affecté par la rotation

On notera la permutation entre $i$ et $j$ $$s_{i, j} : \begin{cases} O \rightarrow O \ o \mapsto \begin{cases} i & \text{si} \quad o = j \ j & \text{si} \quad o = i \ o & \text{sinon} \end{cases} \end{cases}$$

On notera $cx$, $cy$ et $c_z$ les coordonnées du cube $c$

Enfin, on notera $g$ la fonction permettant d'obtenir les coordonnées du cube $c$ : $g(c) = cx, cy, cz$. Et son inverse $g^{-1}(cx, cy, cz) = c$

Soient $c \in C$ et $o \in O$.

Positions

• Rotation de la face droite :

$$ rx(\text{Right}, \text{Clockwise}, c) = \begin{cases} g^{-1}(cx, cz, 1 - cy) & \text{si } c \in C_{\text{Right}} \ c & \text{sinon} \end{cases} $$

• Rotation de la face du bas :

$$ rx(\text{Bottom}, \text{Clockwise}, c) = \begin{cases} g^{-1}(1 - cz, cy, cx) & \text{si } c \in C_{\text{Bottom}} \ c & \text{sinon} \end{cases} $$

• Rotation de la face arrière :

$$ rx(\text{Back}, \text{Clockwise}, c) = \begin{cases} g^{-1}(cy, 1 - cx, cz) & \text{si } c \in C_{\text{Back}} \ c & \text{sinon} \end{cases} $$

Les autres directions se déduisent :

$$ rx(f, \text{Halfturn}, c) = rx(f, \text{Clockwise}, r_x(f, \text{Clockwise}, c)) $$

$$ rx(f, \text{Counterclockwise}, c) = rx(f, \text{Clockwise}, rx(f, \text{Clockwise}, rx(f, \text{Clockwise}, c))) $$

Orientations

Pour toute face $f$ :

$$ r_\theta(f, \text{Halfturn}, c, o) = o $$

• Rotation de la face droite :

$$ r\theta(\text{Right}, d, c, o) = \begin{cases} s{0, 2}(o) & \text{si } c \in C_{\text{Right}} \ o & \text{sinon} \end{cases} $$

• Rotation de la face du bas :

$$ r\theta(\text{Bottom}, d, c, o) = \begin{cases} s{0, 1}(o) & \text{si } c \in C_{\text{Bottom}} \ o & \text{sinon} \end{cases} $$

• Rotation de la face arrière :

$$ r\theta(\text{Back}, d, c, o) = \begin{cases} s{1, 2}(o) & \text{si } c \in C_{\text{Back}} \ o & \text{sinon} \end{cases} $$

Conditions d'arrêt

Position finale

Le cube est correctement placé si :

$$ \forall id \in C : \quad x{id, id}(t{\text{max}}) $$

Orientation finale

Et correctement orienté si :

$$ \forall c \in C : \quad \theta{c, 0}(t{\text{max}}) $$

Transitions

Les transitions changent à la fois la position et l'orientation des cubes affectés.

Pour tout $t \in T^*$ :

Position :

$$ a{f, d}(t) \Rightarrow \left( x{rx(f,d,c), id}(t) = x{c, id}(t-1) \right) $$

Formulé en CNF :

• $(x{c', id}(t) \lor \lnot x{c, id}(t - 1) \lor \lnot a_{f, d}(t))$
• $(\lnot x{c', id}(t) \lor x{c, id}(t - 1) \lor \lnot a_{f, d}(t))$

Orientation :

$$ a{f, d}(t) \Rightarrow \left( \theta{rx(f,d,c), r\theta(f,d,c,o)}(t) = \theta_{c, o}(t-1) \right) $$

Formulé en CNF :

• $(\theta{c', o'}(t) \lor \lnot \theta{c, o}(t - 1) \lor \lnot a_{f,d}(t))$
• $(\lnot \theta{c', o'}(t) \lor \theta{c, o}(t - 1) \lor \lnot a_{f,d}(t))$

Contraintes

1. Une seule action à la fois

$$ \forall t \in T^* : \bigwedge{\substack{(f, d), (f', d') \in F \times D \ (f, d) <{\text{lex}} (f', d')}} \left( \lnot a{f, d}(t) \lor \lnot a{f', d'}(t) \right) $$

2. Toujours effectuer une action

$$ \forall t \in T^* : \bigvee{(f, d) \in F \times D} a{f, d}(t) $$