Bonjour Philoux !

J'ai fait une modélisation mathématique de ce problème mais j'abouti à une résolution impossible !
Donc j'en conclus qu'on ne peux passer de la position A à la position B.
Mais j'ai peut-être fait une erreur en modélisant car j'éspèrais secrétement trouver une solution.
Merci d'éclairer ma lanterne car je suis en panne d'idées!

moi, j'ai tout bêtement découpé les pièces et, sauf erreur, y suis parvenu en ... coups

la réponse à la première question est donc bien : OUI

Merci de t'être penchée sur ce casse-tête...

sympa ton smiley

Philoux

>Youpi

...que vous pouvez donner à chercher à vos chères têtes blondes ...

Trop jeune encore, je pense

Philoux

Si tu trouves une tête blonde qui y arrive je veux bien me faire nonne !

très bon !

Philoux

ça y est je viens d'y arriver !! un jeu d'enfant en fait (je vais finir nonne moi)
Ma modélisation mathématique ne prenait pas en compte la géométrie spécifique des différents éléments (en bref j'ai fait n'importe quoi)
par contre je n'est pas compté le nombre de déplacements et surtout je ne sais pas si c'est bien le minimum.
donc à suivre

à 19:00, je parlais de TA "chère tête blonde"...

D'autres mathîlien(ne)s vont bien te répondre ce soir...

Philoux

Bon après décompte ma solution se fait en 78 déplacements.
Quelqu'un a-t-il mieux ?

à 19:00, je parlais de TA "chère tête blonde"

La mienne de tête blonde (qui est brune d'ailleur) est effectivement encore un peu jeune (3 mois) pour se lancer dans la résolution d'enigmes mathématiques !
Mais je vais lui soumettre sait-on jamais

Youpi, posté le 04/01/2006 à 20:31

Bon après décompte ma solution se fait en 78 déplacements.
Quelqu'un a-t-il mieux ?

Ce type d'énigme, parce que difficilement programmable ou à faire réaliser par un quelconque automate, semble ne pas rencontrer de succès...

Elle fait cependant partie d'énigmes de type olympiade, à résoudre "à la main"...

philoux

Bonjour Philoux

Vu que visiblement personne d'autre que moi ne s'est penché sur cette énigme, peux-tu me donner ta solution avec le nombre de coups minimum ?
En fait ce qui m'interresse surtout c'est de savoir comment tu justifies qu'il s'agit bien du minimum.

Bonjour
Il est déjà paru des casse-tête de ce genre dans diverses revues.
Je suis intéressé aussi bien par la modélisation mathématique que par la solution optimale.
Merci d'avance

Philoux

Bonjour
philoux, on attend...

Philoux,
ce n'est pas gentil. Tu ne m'as pas répondu.
J'ai une solution en 31 ou 54 mouvements (bien moins que 78). Ca dépend si on compte un déplacement ou 2 (ou 3) quand on déplace une pièce dans la même direction sur une ou 2 (ou 3) unité(s).  

Désolé goupi1 et Youpi

Je prépare une "correction" en images, et bien que commencée, elle a du mal à se terminer

Je vais cependant vous décevoir : je n'ai pas la compétence pour vous "démontrer" que c'est la solution à nombre minimal de déplacements...

Si d'aucuns savent le "démontrer" proprement, je suis également preneur...

La soluce en image arrive.

Philoux

Bonsoir,
un copain m'a fait la solution visuelle qu'il a programmée en flash. Il sera difficile de faire moins de coups que 31 (ou 54).

Goupi1 d'après la définition donnée par Philoux d'un déplacement :
On appelle "déplacement" la translation verticale ou horizontale d'une pièce quelconque sur une distance d'un carreau.
Sinon chapeau pour ta solution en 54 déplacements

Bonjour,

Je vous livre ce à quoi j'avais abouti qui est cependant supérieur à la soluce de goupi1.

N'hésitez pas à fournir votre soluce...

Philoux

en non animé, c'est peut-être plus facile à analyser...

Philoux

Au fait, pour le gif animé, la pièce qui doit être déplacée est bordée de gras...

Pour être sous la barre fatidique des 40 kO de l'île, j'ai du dégrader les couleurs au point que les pièces sont moins différentiables que sur le gif excel.

Philoux

Philoux, comment fais-tu ton gif animé ?

Salut goupi1

J'ai un utilitaire qui, à partir de gifs classique (snapsot d'excel), fait un animé.

Je suis chez des amis, là, et ne saurais te donner le nom illico (y'a un "lead" dans le nom).

Philoux

Bonsoir,

peut être avec ceci

Salut

Fonctionne sous XP aussi

et voilà je me mêle de ce qui ne me regarde pas et tombe à coté

Salut dad

En effet, J-P m'avait conseillé ce freeware mais ça ne m'avait pas convaincu (peu convivial)

Mais je l'ai vu poster des gif animés très sympas...

Philoux

et voilà je me mêle de ce qui ne me regarde pas et tombe à coté

pourquoi dis-tu celà ?

Philoux

re,

goupi1 s'adressait à toi et je me permet de supposer que tu as peut être utilisé ... par conséquent j'étais nécessairement mal placé pour répondre à goupi1 à ta place c'est tout

Salut

>goupi1

En retour, peux-tu nous faire partager ta solution ?

Merci

Philoux

Jolie solution Philoux ça a dû te prendre un peu de temps de la réaliser ...
Personnelement j'aurais pas eu le courage !

Merci Youpi

Et encore, dommage que l'île limite à 40 kO car sinon, le gif animé aurait été plus sexy...

Philoux

Alors maintenant c'est goupi1 qui a la pression pour nous donner ça soluce !
Il se sent obligé de faire aussi le coup du gif animé ... J'attend avec impatience !

T'as le droit, Youpi, de donner ta soluce itou...sans gif animé

Philoux

Non avec 78 déplacements j'ai vraiment trop la honte pour montrer ma solution !
I'm too ridiculous !!

En revanche, peux-tu exposer, dans les grandes lignes, l'algo que tu as utilisé/programmé ?

Philoux

Bah non plus parce que comme je l'ai déja dit mon algo il marché pas car ma modélisation ne prenait pas en compte tous les éléments ... donc là aussi trop la honte.

Pour finir j'ai fais comme toi j'ai découpé les bouts de papier et j'ai essayé a la main.

ah oui

Philoux

il fallait lire :j'ai fait

En fait j'avais modélisé le problème comme un jeu ou il faut reconstitué une figure en déplacant des carrés avec toujours une case vide (je ne sais plus le nom de ce jeu).
Mais ça ne prenais pas en compte le fait qu'il pouvait y avoir des imbrication particulières entre certaines pièce.
Donc il n'y avait pas de solution possible avec cette modélisation (et pour cause)

...une figure en déplacant des carrés avec toujours une case vide (je ne sais plus le nom de ce jeu)....

Jeu de taquin, je crois

Ici, c'était plutôt le jeu de l'"Ane Rouge"

Philoux

En tous cas il me paraît difficile de faire une modélisation mathématique de ce problème à la main.
Eventuellement avec un programme informatique bien ficelé mais là c'est pas trop mon domaine.

Salut,

En lisant la discussion j'allais poster un message pour dire que ca ressemblait a l'ane rouge et Bing c'est dit dans l'avant dernier message. Je confirme en passant le nom du Taquin dont l'original avait ete propose par Sam Loyd avec le 14 et le 15 inverses. Il avait propose 1000 dollars de recompense a celui qui reussissait a remettre le 14 et le 15 dans l'ordre. Il savait que c'etait impossible. La demonstration de  cette impossibilite a un lien avec la theorie de Galois.

Et l'ane rouge Philoux tu l'as ou pas ? C'est un beau jeu en bois que j'ai achete  il y a 1 an ou 2 mais les pieces ne sont pas les memes que le tien. Je crois qu'on le trouve aussi sur internet. Le probleme avec ce jeu c'est que si tu ne notes pas tous tes coups tu ne sais plus comment tu as fait quand tu as reussi.

minkus

Salut minkus

Il existe, je crois, plusieurs versions de jeux de type l'"âne rouge".

J'avais rédigé, à une époque, un .doc avec les déplacements pour sa résolution.

Je le rechercherai...

Philoux

La solution arrive avec ou sans Gif dès que je peux..

J'appelle HG, HD, BG et BD les pièces en haut à gauche, en h à droite, en bas à g, en bas à dr. J'appelle h,b,d et g les directions haute, bas, droite et gauche.

HD  d   1   1
BD  d   2   2
HG  g   3   3
C   h   4   4
BG  d   5   5
HG  bb  6   7
C   gg  7   9
BG  hh  8  11
BG  d   9  12
BD  ggg 10 15
BG  bb  11 17
C   dd  12 19
HG  hh  13 21
BD  g   14 22
BG  d   15 23
C   bb  16 25
HD  gg  17 27
BG  hh  18 29
C   dd  19 31
BD  dd  20 33
HG  bb  21 35
HD  gg  22 37
BG  gg  23 39
C   hh  24 41
BD  dd  25 43
BG  bb  26 45
HD  dd  27 47
HG  hh  28 49
BG  gg  29 51
BD  gg  30 53
C   b   31 54

Bonjour,

Comme promis, la soluce de goupi1 en image animée.

Pour ceux que ça intéresse, le gif animé fait 69 kO, en étant composé de 34 images.

En désirant faire un "fondu enchaîné" entre deux images, l'introduction d'une seule image génère (même avec optimisation) pas moins de 9 k0 par image : j'ai donc laissé les seules 34 images pour ne pas surcharger...

Nombre en rouge : nombre de déplacements de pièces de 1 ou plusieurs cases horizontales ou vertcales

Nombre en noir : nombre de déplacements de pièces sur 1 seule case.

L'âne rouge, difficilement programmable (smiley provocation ) semble n'intéresser que peu de monde...

Philoux