Déterminer si un cube mélangé est faisable
Déterminer si un cube mélangé est faisable
Bonjour tout le monde !
Comme exprimé dans le titre, je cherche une méthode permettant de savoir si un rubik's cube est faisable alors qu'il est mélangé.
Je me suis dit que peut-être il était possible d'examiner l'orientation de chaque pièce, mais comment... ?
Pour le contexte, je viens de finir la réalisation d'un robot qui résout les cubes, mais si quelqu'un inverse une arête ou un coin l'algorithme de résolution que j'ai implémenté ne fonctionnera pas. L'objectif serait donc de filtrer ce cas en amont !
Merci de m'avoir lu, à bientôt.
Comme exprimé dans le titre, je cherche une méthode permettant de savoir si un rubik's cube est faisable alors qu'il est mélangé.
Je me suis dit que peut-être il était possible d'examiner l'orientation de chaque pièce, mais comment... ?
Pour le contexte, je viens de finir la réalisation d'un robot qui résout les cubes, mais si quelqu'un inverse une arête ou un coin l'algorithme de résolution que j'ai implémenté ne fonctionnera pas. L'objectif serait donc de filtrer ce cas en amont !
Merci de m'avoir lu, à bientôt.
- Yves CREANGE
- Commence à se plaire ici
- Messages : 30
- Enregistré le : mar. nov. 14, 2017 7:41 pm
- Contact :
Re: Déterminer si un cube mélangé est faisable
Salut NvD
Si ta question suppose aucun mouvement, alors je doute que ce soit humainement possible. Quand bien même tu pourrais identifier une pièce coin mal orientée parce qu'au préalable tu l'aurais "twistée" manuellement, en résolvant ton cube, certes tu te retrouveras avec un coin mal orienté, mais ce ne sera pas nécessairement le coin que tu auras "twisté". Beaucoup trop de paramètres à considérer.
Yves
Si ta question suppose aucun mouvement, alors je doute que ce soit humainement possible. Quand bien même tu pourrais identifier une pièce coin mal orientée parce qu'au préalable tu l'aurais "twistée" manuellement, en résolvant ton cube, certes tu te retrouveras avec un coin mal orienté, mais ce ne sera pas nécessairement le coin que tu auras "twisté". Beaucoup trop de paramètres à considérer.
Yves
Re: Déterminer si un cube mélangé est faisable
Salut Yves, merci pour ta réponse !
Mon objectif n'est pas exactement de le faire "humainement", puisque j'ai la puissance de calcul de mon ordinateur pour m'aider.
D'ailleurs, j'ai trouvé hier ce site qui me donne des pistes.
Déjà, il est possible de vérifier que les orientations de coins sont complémentaires de par le système de comptage qu'il a donné (0 si le coin est bien orienté, 1 si tourné dans le sens des aiguilles d'une montre, 2 dans le sens inverse des auguilles d'une montres, total divisible par 3).
Ensuite, je cherche des moyens de vérifier l'orientation des arêtes, et de voir si des pièces ont été interverties.
Mon objectif n'est pas exactement de le faire "humainement", puisque j'ai la puissance de calcul de mon ordinateur pour m'aider.
D'ailleurs, j'ai trouvé hier ce site qui me donne des pistes.
Déjà, il est possible de vérifier que les orientations de coins sont complémentaires de par le système de comptage qu'il a donné (0 si le coin est bien orienté, 1 si tourné dans le sens des aiguilles d'une montre, 2 dans le sens inverse des auguilles d'une montres, total divisible par 3).
Ensuite, je cherche des moyens de vérifier l'orientation des arêtes, et de voir si des pièces ont été interverties.
- Spols
- Le belge du Magic
- Messages : 5469
- Enregistré le : jeu. août 18, 2005 2:44 pm
- Localisation : Sur mon clavier ou dans mon lit
- Contact :
Re: Déterminer si un cube mélangé est faisable
Salut,
J'ai un code javascript quelque part pour faire ce que tu cherche laisse moi l'occasion de retomber dessus.
J'ai un code javascript quelque part pour faire ce que tu cherche laisse moi l'occasion de retomber dessus.
Ce nouveau forum valait bien une nouvelle signature
- Spols
- Le belge du Magic
- Messages : 5469
- Enregistré le : jeu. août 18, 2005 2:44 pm
- Localisation : Sur mon clavier ou dans mon lit
- Contact :
Re: Déterminer si un cube mélangé est faisable
C'est du php pas du javascript
ce code vient d'une bibliothèque cube_lib que j'ai améliorer moi même notamment avec cette fonction.
Ma représentation d'un cube ressemble à ceci (cube résolu)
(0,1,2,3,4,5),(0,1,2,3,4,5,6,7),(0,0,0,0,0,0,0,0),(0,1,2,3,4,5,6,7,8,9,10,11),(0,0,0,0,0,0,0,0,0,0,0,0)
ou sont équivalent en tableau (d'où la fonction mask2array)
les groupes sont:
-la position des centres
-la position des coins
-l'oriuentation des coins
-la position des arètes
-l'orientation des arêtes
Pour la position j'ai défini un emplacement pour chaque pièce
centres : U R F D L B
coins: $URF, $UFL, $ULB, $UBR, $DFR, $DLF, $DBL, $DRB
arêtes: $UR, $UF, $UL, $UB, $DR, $DF, $DL, $DB, $FR, $FL, $BL, $BR
le nombre à chaque emplacement défini quelle pièce est où
Pour l'orientation les coins peuvent avoir 0, 1 ou 2 et les arête 0 ou 1
0 correspondant à une bonne orientation selon une définition de blind facette U ou D sur la face U ou D pour les coins et https://www.francocube.com/deadalnix/blindfold_step_2 pour les arêtes
La petite complexité dans le code vient du faite qu'il peut y avoir des -1 à la place des nombre lorsque lea pièce ou l'orientation n'est pas définie.
Dans mon algo je commence par définir si les orientations sont cohérente
puis je défini les taille de cycle des arêtes et des coins et déterminaer si il y a parité dans chacun des sous groupes si il n'y a pas de partité ou 2 parité le cube est faisable.
Je peux te fournir le code complet de mon cube_lib si tu veux
Code : Tout sélectionner
function checkParityMask ($mask) {
if (!is_array($mask)) mask2array($mask,null);
foreach($mask as $value) if (!$value) return $false;//renvoi false si une valeur est a false
$corner = array_count_values(array_slice($mask,14,8));
$edge = array_count_values(array_slice($mask,34,12));
if (!isset($corner[-1]) && array_sum(array_slice($mask,14,8)) % 3) return false;
if (!isset($edge[-1]) && array_sum(array_slice($mask,34,12)) % 2) return false;
$parity = false;
$corner = array_count_values(array_slice($mask,6,8));
$edge = array_count_values(array_slice($mask,22,12));
if ((isset($corner[-1]) && $corner[-1] > 1) || (isset($edge[-1]) && $edge[-1] > 1)) return true;//Si il y a au moins 2 -1 dans les positions des coins ou des arêtes, il ne peut y avoir de parité.
$cycle = '';
$i = 0;
while($i < 8) {
if ($mask[$i+6] == -1) {
$cycle = '';
break;
} elseif ($mask[$i+6] == $i) {
$i++;
continue;
} elseif (strpos($cycle,strval($mask[$i+6])) !== false) {
$cycle .= (substr($cycle,-1) == '|') ? '' : '|';
$i++;
} else {
$cycle .= $mask[$i+6];
$i = $mask[$i+6];
}
}
if (strlen($cycle) > 0) {
$cycle = (substr($cycle,-1) == '|') ? substr($cycle,0,-1) : $cycle;
$cycle = array_map('strlen',explode('|',$cycle));
foreach($cycle as $n) {
if (!($n % 2)) $parity = !$parity;
}
}
$cycle = '';
$i = 0;
while($i < 12) {
if ($mask[$i+22] == -1) {
$cycle = '';
break;
} elseif ($mask[$i+22] == $i) {
$i++;
continue;
} elseif (strpos($cycle,strval($mask[$i+22])) !== false) {
$cycle .= (substr($cycle,-1) == '|') ? '' : '|';
$i++;
} else {
$cycle .= $mask[$i+22];
$i = $mask[$i+22];
}
}
if (strlen($cycle) > 0) {
$cycle = (substr($cycle,-1) == '|') ? substr($cycle,0,-1) : $cycle;
$cycle = array_map('strlen',explode('|',$cycle));
foreach($cycle as $n) {
if (!($n % 2)) $parity = !$parity;
}
}
return !$parity;
}
Ma représentation d'un cube ressemble à ceci (cube résolu)
(0,1,2,3,4,5),(0,1,2,3,4,5,6,7),(0,0,0,0,0,0,0,0),(0,1,2,3,4,5,6,7,8,9,10,11),(0,0,0,0,0,0,0,0,0,0,0,0)
ou sont équivalent en tableau (d'où la fonction mask2array)
les groupes sont:
-la position des centres
-la position des coins
-l'oriuentation des coins
-la position des arètes
-l'orientation des arêtes
Pour la position j'ai défini un emplacement pour chaque pièce
centres : U R F D L B
coins: $URF, $UFL, $ULB, $UBR, $DFR, $DLF, $DBL, $DRB
arêtes: $UR, $UF, $UL, $UB, $DR, $DF, $DL, $DB, $FR, $FL, $BL, $BR
le nombre à chaque emplacement défini quelle pièce est où
Pour l'orientation les coins peuvent avoir 0, 1 ou 2 et les arête 0 ou 1
0 correspondant à une bonne orientation selon une définition de blind facette U ou D sur la face U ou D pour les coins et https://www.francocube.com/deadalnix/blindfold_step_2 pour les arêtes
La petite complexité dans le code vient du faite qu'il peut y avoir des -1 à la place des nombre lorsque lea pièce ou l'orientation n'est pas définie.
Dans mon algo je commence par définir si les orientations sont cohérente
puis je défini les taille de cycle des arêtes et des coins et déterminaer si il y a parité dans chacun des sous groupes si il n'y a pas de partité ou 2 parité le cube est faisable.
Je peux te fournir le code complet de mon cube_lib si tu veux
Ce nouveau forum valait bien une nouvelle signature
- cyril
- Helvète Underground
- Messages : 4098
- Enregistré le : jeu. juin 30, 2005 10:13 am
- Localisation : En Suisse
- Contact :
Re: Déterminer si un cube mélangé est faisable
Yves a écrit :Si ta question suppose aucun mouvement, alors je doute que ce soit humainement possible.
En fait, tout cubeur qui pratique une méthode de blindfold peut le faire, et en quelques secondes à peine pour les meilleurs. Le plus facile est l'orientation, comme tu le mentionnes pour les coins et par exemple en vérifiant (voir la méthode de Deadalnix sur francocube par exemeple) qu'un nombre pair d'arêtes ont la bonne orientation.
Pour savoir si deux pièces ont été interverties, par contre, c'est un peu plus difficile mais à nouveau les méthodes de blindfold te donneront la solution. Une piste est de déterminer les cycles de coins et ceux des arêtes ("qui doit aller où ?"), puis de compter la longueur de ces cycles. Bonne lecture
EDIT : grillé par Spols
Solution pour les débutants, sur francocube !
- Spols
- Le belge du Magic
- Messages : 5469
- Enregistré le : jeu. août 18, 2005 2:44 pm
- Localisation : Sur mon clavier ou dans mon lit
- Contact :
Re: Déterminer si un cube mélangé est faisable
si tu pars de photo de chaque face, il faudra aussi vérifier que chaque pièce existe (un coin blanc,jaune,rouge n'éxiste pas) et est unique.
Ce nouveau forum valait bien une nouvelle signature
Re: Déterminer si un cube mélangé est faisable
@Spols : Merci pour ta réponse et ton code, qui, si je le comprends bien, renvoie false si la somme globale de la longueur des cycles (arêtes et coins) est paire.
C'est bien ça ? Tu appliques
Je ne suis pas sûr de pouvoir tirer grand chose de ton cube_lib par contre, j'ai pas trop l'habitude de lire du PHP.
Mais je suis curieux, est-ce que ta librairie implémente un/des algorithme(s) de résolution ?
@Cyril : Merci aussi pour ta réponse !
Après vous avoir lu et effectué quelques recherches, j'en arrive à la conclusion suivante :
C'est bien ça ? Tu appliques
à chaque cycle, j'en déduis que le résultat sera le même qu'au départ (false) lorsque le nombre de cycles à la taille impaire est pair.if (!($n % 2)) $parity = !$parity;
Je ne suis pas sûr de pouvoir tirer grand chose de ton cube_lib par contre, j'ai pas trop l'habitude de lire du PHP.
Mais je suis curieux, est-ce que ta librairie implémente un/des algorithme(s) de résolution ?
@Cyril : Merci aussi pour ta réponse !
Après vous avoir lu et effectué quelques recherches, j'en arrive à la conclusion suivante :
- Pas de pièces dupliquées / impossibles.
- La somme de l'orientation des arêtes est paire.
- La somme de l'orientation des coins est divisible par trois.
- La parité du nombre de permutations d'arêtes nécessaire à la résolution du cube est égale à la parité du nombre de permutations de coins nécessaire à la résolution du cube.
- Yves CREANGE
- Commence à se plaire ici
- Messages : 30
- Enregistré le : mar. nov. 14, 2017 7:41 pm
- Contact :
Re: Déterminer si un cube mélangé est faisable
Merci Cyril, ça me plait comme réponse. Je ne me suis jamais intéressé au blindfold, mais ta réponse éveille ma curiosité. Je crois que je vais m'amuser à essayer de comprendre ça.
- Spols
- Le belge du Magic
- Messages : 5469
- Enregistré le : jeu. août 18, 2005 2:44 pm
- Localisation : Sur mon clavier ou dans mon lit
- Contact :
Re: Déterminer si un cube mélangé est faisable
Je pars d'une parité a false et j'inverse dès que le cycle est paire. Mais je retourne l'inverse a la fin de la fonction. Je remarque maintenant que le contraire serait plus logique.
Donc on aura une parité si le nombre de cycle paire est paire. Et donc imoossible de résoudre le cube dans ce cas là.
Non cube lib ne prevoit pas d'algo de resolution cela n'a jamais été son but et php n'est pas un bon language pour cela. Il sert vraiment que à modéliser un cube et le manipuler. J'y avais rajouter une couche en javascript pour l'affichage et le "dessin". Je dois surement avoir l'equivalent de ce code en javascript car j'avais prevu un affichage d'erreur ou une validation lors de la definition du cube.
Donc on aura une parité si le nombre de cycle paire est paire. Et donc imoossible de résoudre le cube dans ce cas là.
Non cube lib ne prevoit pas d'algo de resolution cela n'a jamais été son but et php n'est pas un bon language pour cela. Il sert vraiment que à modéliser un cube et le manipuler. J'y avais rajouter une couche en javascript pour l'affichage et le "dessin". Je dois surement avoir l'equivalent de ce code en javascript car j'avais prevu un affichage d'erreur ou une validation lors de la definition du cube.
Ce nouveau forum valait bien une nouvelle signature