Bien le bonjour

Bienvenue les nouveaux ! Forum pour ceux qui désirent écrire un petit mot pour se présenter. MAIS réservez les questions pour les forums spécifiques !
Le Trombinoscope !
gipsy
Discret
Messages : 5
Enregistré le : dim. avr. 23, 2017 2:23 pm

Bien le bonjour

Message par gipsy »

Bonjour,
Professeur de Sciences Physiques et d'Informatique et Sciences du numérique au lycée je vois chaque année des élèves jouer avec leur rubik's cube dans les couloirs . Je m'y suis donc un peu intéressé mais très modestement. Je résous uniquement le cube par la méthode des couches.
J'ai par ailleurs réalisé un programme en python qui génère aléatoirement le patron d'un cube et permet de faire les différentes rotations pour le résoudre.
Je viens donc sur ce forum afin de savoir s'il existe une méthode de résolution très générale en partant de n'importe quelle configuration afin de vérifier si il est bien possible de résoudre le cube sur mon programme.
Bannière atoutcubes.com
Avatar du membre
Spaghetti
Scotché au forum
Messages : 324
Enregistré le : dim. sept. 04, 2016 6:38 pm
Localisation : pas loin de Nantes
Contact :

Re: Bien le bonjour

Message par Spaghetti »

bienvenu !!!!!
Avatar du membre
Cubeur-manchot
VIP au club des 1000
Messages : 2999
Enregistré le : jeu. sept. 11, 2014 5:16 pm
Localisation : Bures-sur-Yvette (91)
Contact :

Re: Bien le bonjour

Message par Cubeur-manchot »

Bienvenue :)
gipsy a écrit : dim. avr. 23, 2017 2:31 pmJ'ai par ailleurs réalisé un programme en python qui génère aléatoirement le patron d'un cube et permet de faire les différentes rotations pour le résoudre.
Je viens donc sur ce forum afin de savoir s'il existe une méthode de résolution très générale en partant de n'importe quelle configuration afin de vérifier si il est bien possible de résoudre le cube sur mon programme.
Tu veux savoir si ton programme peut résoudre n'importe quel mélange, ou découvrir d'autres méthodes de résolution ?
Avatar du membre
smotis
VIP au club des 1000
Messages : 1456
Enregistré le : mar. déc. 30, 2014 11:01 am
Localisation : Bussy (18130)

Re: Bien le bonjour

Message par smotis »

Soit le bienvenue , tu vas en intéressé plus d'un avec ta vérification de programme . :oui:
........Single/AVG 5/AVG12/AVG50
3x3:11"66/18"31/20"09/22"21 Cube : Valk
4X4:.1'10''42/..1'26''22/...1'28''94/..1'36''88 Cube : Yuxin


Tableau de tous mes Pbs

Compétitions virtuelles ouvert a tous:
Francocubes , AVG 12 , To The Top

Venez tchater en direct sur DISCORD avec nous
gipsy
Discret
Messages : 5
Enregistré le : dim. avr. 23, 2017 2:23 pm

Re: Bien le bonjour

Message par gipsy »

Cubeur-manchot a écrit : dim. avr. 23, 2017 2:48 pm Bienvenue :)
gipsy a écrit : dim. avr. 23, 2017 2:31 pmJ'ai par ailleurs réalisé un programme en python qui génère aléatoirement le patron d'un cube et permet de faire les différentes rotations pour le résoudre.
Je viens donc sur ce forum afin de savoir s'il existe une méthode de résolution très générale en partant de n'importe quelle configuration afin de vérifier si il est bien possible de résoudre le cube sur mon programme.
Tu veux savoir si ton programme peut résoudre n'importe quel mélange, ou découvrir d'autres méthodes de résolution ?
Mon programme n'a rien d'extraordinaire je pense. J'ai juste fais ça pour m'amuser. Il génère un cube aléatoirement (mais le cube est vu à plat, on ne voit donc que le patron). Et puis différents boutons permettent au joueur d'effectuer les rotations.
Ça ressemble à ça:

Image

Le truc c'est que vu mon niveau en Rubik's cube ( je ne sais le résoudre que très classiquement avec la méthode des couches), je me demandais s'il existait, à partir de n'importe quelle situation de départ, une suite de rotations dont on est sûre qu'elles permettent de résoudre le cube.
Avatar du membre
oranjules
"Le slip de Superman !"
Messages : 2837
Enregistré le : lun. août 24, 2009 1:56 pm
Contact :

Re: Bien le bonjour

Message par oranjules »

Il n'y a pas de suite de rotations qui marche à tous les coups (sinon, on n'aurait pas inventé de méthode :p).
Comment generes tu le cube ? Il y a effectivement quelques contraintes à respecter pour qu'il soit possible de le résoudre (je suis sur téléphone donc je les citerais pas, c'est un peu long, mais elles sont trouvables sur le site et sur le forum)
Odder: Bruno, Oka and I?
Odder: we are all pretty god damn fast when we are not messing around :p and you are... just fucking retarded fast in comps >;.<'
Avatar du membre
Antò
Passe sa journée ici. Et dort ici, aussi
Messages : 775
Enregistré le : lun. nov. 07, 2016 7:40 pm
Localisation : Aix en Provence

Re: Bien le bonjour

Message par Antò »

Il y a peut être le fameux algorithme du diable qui faisait dans les 10^15 mouvements si je dis pas n'importe quoi :P

Bienvenue !
single/mo3/ao5/ao12/ao50/ao100
3*3*3 : 8.02 !!!/11.48/12.37/13.65/14.30/14.69
X2019 en stage à Blois
Avatar du membre
Cubeur-manchot
VIP au club des 1000
Messages : 2999
Enregistré le : jeu. sept. 11, 2014 5:16 pm
Localisation : Bures-sur-Yvette (91)
Contact :

Re: Bien le bonjour

Message par Cubeur-manchot »

Antò a écrit : dim. avr. 23, 2017 10:55 pm Il y a peut être le fameux algorithme du diable qui faisait dans les 10^15 mouvements si je dis pas n'importe quoi :P
Je dirais même que sa longueur c'est à peu près 43 252 003 274 489 855 999, car c'est bêtement un chemin hamiltonien entre tous les états du cube.

Je vais essayer de rédiger ça proprement :
- il n'existe pas de séquence de mouvements qui, lorsqu'on l'exécute entièrement et à partir de n'importe quel état, donne l'état résolu (sinon en appliquant l'inverse de cette séquence sur l'état résolu on peut obtenir plusieurs configurations différentes, ce qui est impossible parce que les mouvements du cube sont déterministes)
- il existe plusieurs séquences de mouvements qui passent, au cours de leur exécution, par tous les états du cube. Ce sont donc des chemins hamiltoniens dans les états du cube. Ainsi, en appliquant cette séquence sur n'importe quel état du cube, au cours de l'exécution de la séquence on va rencontrer l'état résolu (une seule fois). Cette séquence est très grande, aussi grande que le nombre d'états possibles du cube, c'est à dire 43*10^18 et des poussières, et est donc impossible à stocker (il faut plusieurs dizaines d'exaoctets pour stocker ces mouvements).

Et pour reformuler la question d'Oranjules : pour générer tes patrons, est-ce que tu appliques aléatoirement des mouvements comme si tu utilisais tes boutons à droite, ou est-ce que tu choisis des orientations et permutations indépendantes les unes des autres ?
Si tu génères tes patrons à l'aide de mouvements du cube, tu n'auras pas de problèmes pour résoudre chaque cas.
Si tu appliques une permutation aléatoire pour les coins, une permutation aléatoire pour les arêtes, une orientation aléatoire pour les coins et une orientation aléatoire pour les arêtes, chacune choisie au hasard, ton cube sera résoluble une fois sur 12 en moyenne, car :
- l'orientation de 7 des 8 coins définit l'orientation du 8ème coin. Si tu le prends au pif, tu as deux chances sur 3 que ça ne corresponde pas, et donc que le cube ne soit pas résoluble.
- même chose pour l'orientation de la 12ème arête, avec une chance sur 2.
- les signatures des permutations des coins et des arêtes sont les mêmes : sigma(permutation_coins) = sigma(permutation_arêtes). (c'est-à-dire : [le nombre de cycles pairs de coins] + [le nombre de cycles pairs d'arêtes] = 0 mod 2)
Modifié en dernier par Cubeur-manchot le mar. avr. 25, 2017 1:04 pm, modifié 1 fois.
Avatar du membre
biocube
Traîne ici, comme d'hab'
Messages : 242
Enregistré le : ven. juil. 22, 2016 11:03 am

Re: Bien le bonjour

Message par biocube »

Bienvenue ami "Professor" :smt023:
Avatar du membre
Antò
Passe sa journée ici. Et dort ici, aussi
Messages : 775
Enregistré le : lun. nov. 07, 2016 7:40 pm
Localisation : Aix en Provence

Re: Bien le bonjour

Message par Antò »

Cubeur-manchot a écrit : lun. avr. 24, 2017 4:02 pm 43 252 003 274 489 855 999
bouarf j'étais pas très loin :lol:

Si on part du principe que la formule doit être exécutée en entier en effet il serait absurde que ça marche à tous les coups

Tu sais toi aussi tu ferais un bon prof je pense :P
single/mo3/ao5/ao12/ao50/ao100
3*3*3 : 8.02 !!!/11.48/12.37/13.65/14.30/14.69
X2019 en stage à Blois
Avatar du membre
Greg74
Scotché au forum
Messages : 260
Enregistré le : jeu. mars 31, 2016 12:00 pm
Localisation : Vous voyer le cube ? Je suis à 5cm de lui...
Contact :

Re: Bien le bonjour

Message par Greg74 »

Bienvenue sur le fofo !
Tu dois bien aimé le 5x5 donc ! (je sais pas si vous comprendrez...)
Avatar du membre
Antò
Passe sa journée ici. Et dort ici, aussi
Messages : 775
Enregistré le : lun. nov. 07, 2016 7:40 pm
Localisation : Aix en Provence

Re: Bien le bonjour

Message par Antò »

Greg74 a écrit : lun. avr. 24, 2017 10:21 pm Bienvenue sur le fofo !
Tu dois bien aimé le 5x5 donc ! (je sais pas si vous comprendrez...)
fuis
single/mo3/ao5/ao12/ao50/ao100
3*3*3 : 8.02 !!!/11.48/12.37/13.65/14.30/14.69
X2019 en stage à Blois
gipsy
Discret
Messages : 5
Enregistré le : dim. avr. 23, 2017 2:23 pm

Re: Bien le bonjour

Message par gipsy »

Pour générer le cube, j'ai créé une liste des 12 arêtes possibles. Chaque arête étant elle-même une liste de deux couleurs.
J'ai crée une liste des 8 coins possibles. Chaque coin étant une liste de 3 couleurs
Le programme :
-place les centres toujours au même endroit
-choisit aléatoirement une arête dans la liste puis la place sur les deux cases correspondant à une arêtes. Puis l'arête est supprimée de la liste afin de ne pas être tirée deux fois. L'opération est répétée pour toutes les arêtes .
-choisit un coin aléatoirement dans la liste puis le place sur les trois cases correspondant à un coin. Le coin est ensuite supprimé de la liste et on répète l'opération pour tous les coins restants.

Du coup si je comprends bien Cubeur-Manchot, avec ce procédé ce n'est pas toujours résoluble.
Nameless
Passe sa journée ici. Et dort ici, aussi
Messages : 832
Enregistré le : mar. janv. 19, 2016 7:06 am
Contact :

Re: Bien le bonjour

Message par Nameless »

En effet, et dans ce cas précis, non seulement ce n'est pas résoluble, mais même en démontant ton cube tu ne peux pas arriver à ce stade !
Un exemple parmi d'autres : le coin jaune-bleu-orange ne pourra jamais être bien orienté. Si le coin est à sa place et le sticker jaune sur la face jaune, alors le sticker bleu sera sur la face orange et inversement.
Image
Avatar du membre
Cubeur-manchot
VIP au club des 1000
Messages : 2999
Enregistré le : jeu. sept. 11, 2014 5:16 pm
Localisation : Bures-sur-Yvette (91)
Contact :

Re: Bien le bonjour

Message par Cubeur-manchot »

En effet, il faut respecter l'ordre des couleurs. Les coins sont définis comme ça, en tournant dans le sens horaire :
- blanc-orange-bleu
- blanc-bleu-rouge
- blanc-rouge-vert
- blanc-vert-orange
- jaune-orange-vert
- jaune-vert-rouge
- jaune-rouge-bleu
- jaune-bleu-orange
S'ils ne sont pas définis comme ça, ils ne peuvent pas être résolus. Et s'ils sont définis comme ça, les seuls problèmes qu'on peut avoir sont les 3 que j'ai indiqués plus haut (orientation des coins, orientation des arêtes, signature des permutations) :oui:
Répondre