Déterminer si un cube mélangé est faisable

Vos questions / remarques sur le cube classique 3x3x3
Les méthodes principales du 3x3x3 et leurs variantes
Les visiteurs peuvent poster des messages dans cette partie
NvD
Discret
Messages : 3
Enregistré le : sam. févr. 15, 2020 7:57 pm

Déterminer si un cube mélangé est faisable

Message par NvD »

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.

Avatar du membre
Yves CREANGE
Commence à se plaire ici
Messages : 29
Enregistré le : mar. nov. 14, 2017 7:41 pm

Re: Déterminer si un cube mélangé est faisable

Message par Yves CREANGE »

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

NvD
Discret
Messages : 3
Enregistré le : sam. févr. 15, 2020 7:57 pm

Re: Déterminer si un cube mélangé est faisable

Message par NvD »

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.

Avatar du membre
Spols
Le belge du Magic
Messages : 5240
Enregistré le : jeu. août 18, 2005 2:44 pm
Localisation : Sur mon clavier ou dans mon lit

Re: Déterminer si un cube mélangé est faisable

Message par Spols »

Salut,

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

Avatar du membre
Spols
Le belge du Magic
Messages : 5240
Enregistré le : jeu. août 18, 2005 2:44 pm
Localisation : Sur mon clavier ou dans mon lit

Re: Déterminer si un cube mélangé est faisable

Message par Spols »

C'est du php pas du javascript

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;
} 
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
Ce nouveau forum valait bien une nouvelle signature

Avatar du membre
cyril
Helvète Underground
Messages : 3958
Enregistré le : jeu. juin 30, 2005 10:13 am
Localisation : En Suisse

Re: Déterminer si un cube mélangé est faisable

Message par cyril »

Yves a écrit :Si ta question suppose aucun mouvement, alors je doute que ce soit humainement possible.
NvD a écrit :
dim. févr. 16, 2020 8:07 pm
Ensuite, je cherche des moyens de vérifier l'orientation des arêtes, et de voir si des pièces ont été interverties.
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 :wink:

EDIT : grillé par Spols :lol:
Francocube, tout plein de méthodes pour tous !

Avatar du membre
Spols
Le belge du Magic
Messages : 5240
Enregistré le : jeu. août 18, 2005 2:44 pm
Localisation : Sur mon clavier ou dans mon lit

Re: Déterminer si un cube mélangé est faisable

Message par Spols »

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

NvD
Discret
Messages : 3
Enregistré le : sam. févr. 15, 2020 7:57 pm

Re: Déterminer si un cube mélangé est faisable

Message par NvD »

@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
if (!($n % 2)) $parity = !$parity;
à 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.

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. :-D

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.
Au final, cette idée de parité de nombre de permutation prend sens lorsqu'on réfléchit à un mélange comme une succession de PPL T par exemple.

Avatar du membre
Yves CREANGE
Commence à se plaire ici
Messages : 29
Enregistré le : mar. nov. 14, 2017 7:41 pm

Re: Déterminer si un cube mélangé est faisable

Message par Yves CREANGE »

cyril a écrit :
lun. févr. 17, 2020 8:20 am
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
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.

Avatar du membre
Spols
Le belge du Magic
Messages : 5240
Enregistré le : jeu. août 18, 2005 2:44 pm
Localisation : Sur mon clavier ou dans mon lit

Re: Déterminer si un cube mélangé est faisable

Message par Spols »

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.
Ce nouveau forum valait bien une nouvelle signature