Enigme : Le plus court chemin de la fortune

[invite06fcc10b]

$********$
**********
**********
X*********
**********
**********
**********
**********
$********$
$********$

Question simple :
On dispose d'un tableau de 10 fois 10 cases.
En partant de X, et en se déplaçant horizontalement ou verticalement mais pas en diagonal et de 1 case à la fois, combien de déplacements faut-il faire au minimum pour passer sur toutes les cases marquées avec un $.

NB : Il n'y a pas de piège, l'énoncé est limpide ... mais il faut quand même réfléchir un peu pour trouver la solution optimale.
-----

[matthias]

Il y a déjà une solution évidente en 31, donc j'imagine que c'est moins.

[gabychef]

Mouais, 31 aussi ..

[matthias]

Oui je ne pense pas qu'on puisse faire moins en fait.

[A voir en vidéo sur Futura]

[inviteba0a4d6e]

Y a-t-il une formule mathématique permettant de trouver la solution ?

Là, c'est 'humainement' vérifiable, mais avec un tableau de 10¹⁰ cases, c'est déjà plus compliqué et cela demanderait une incroyable patience...

[invite06fcc10b]

Il y a déjà une solution évidente en 31, donc j'imagine que c'est moins.

Peut-être bien que oui ... sinon j'aurais pas posé la question ?

[invite06fcc10b]

Y a-t-il une formule mathématique permettant de trouver la solution ?

Là, c'est 'humainement' vérifiable, mais avec un tableau de 10¹⁰ cases, c'est déjà plus compliqué et cela demanderait une incroyable patience...

En fait, j'ai programmé l'algorithme A* de recherche du plus court chemin et c'est en visualisant la solution qui ne correspondait pas à ma première intuition que je me suis dis : "ben mince alors, on se fout dedans à tous les coups, faut que je le pose dans Futura !"

[invite06fcc10b]

Oui je ne pense pas qu'on puisse faire moins en fait.

Allons, allons, faut pas se laisser aller.
Est-ce que je suis du genre à poser des énigmes trop faciles ?
Allez, un petit indice (tout petit) :
il ne faut pas croire ses yeux, il faut croire les vraies valeurs !

[subichan]

j'aurai aussi dis 31 mais avec ton dernier message je dirai.............. 9 ?


EDIT : je voulais dire 8 et non 9... m'enfin quoiqu'il en soit c'est faux ^^;;;

[juudku]

Si je raisonne comme un ordi, j'ai le droit de passer de la case la plus basse à celle tout en haut en un mouvement ? Et vice et versa ? Ca ferait 8 si on inclue les passages gauche-droite aussi

[invite06fcc10b]

En fait, je rigole d'avance, car le problème est simple, la solution est (relativement) simple, et vous allez vous en mordre les doigts !

(pardon, j'ai effacé mon propre message. Je disais donc aussi que non, il n'est pas permis d'aller de gauche à droite ou de haut en bas, il n'y a aucune astuce d'interprétation de l'énoncé comme c'était le cas dans l'énigme de l'avion).

[juudku]

Je cherche pas d'embrouilles j'cherche une réponse!
Et j'en arrive à 30 allez, encore une demi-heure et je trouve le chemin optimal !

[invite06fcc10b]

Je cherche pas d'embrouilles j'cherche une réponse!
Et j'en arrive à 30 allez, encore une demi-heure et je trouve le chemin optimal !

Pour être sûr que tu as trouvé la solution, dis-moi donc quelles sont les coordonnées de la 25ème case visitée (entre 1 et 10 pour x, idem pour y).
Et les autres auront un très bon indice pour trouver !

[inviteba0a4d6e]

Si je raisonne comme un ordi, j'ai le droit de passer de la case la plus basse à celle tout en haut en un mouvement ? Et vice et versa ? Ca ferait 8 si on inclue les passages gauche-droite aussi

Argyre a précisé : En partant de X, et en se déplaçant horizontalement ou verticalement mais pas en diagonal et de 1 case à la fois...

[subichan]

tout dépent de se que tu veux dire par "déplacements" ^^
sinon je dis 5 "déplacements"

[invite06fcc10b]

Argyre a précisé : En partant de X, et en se déplaçant horizontalement ou verticalement mais pas en diagonal et de 1 case à la fois...

Non, non, cherche pas compliqué. Je me suis peut-être mal exprimé, mais il n'y a pas d'entourloupe dans l'énoncé.

[Bételgeuse]

Tiens, je trouve 30, moi, pas 31 ! (Bon d'accord, je n'ai pas pris un chemin très direct, mais j'ai beau recompter, je trouve toujours 30... Enfin, vu l'heure... )
Ma 25ème case, c'est 6ème ligne, 10ème colonne.

[invite06fcc10b]

tout dépent de se que tu veux dire par "déplacements" ^^
sinon je dis 5 "déplacements"

Non, interdit, mouvement d'1 case voisine à distance 1 = 1 déplacement.

[invite06fcc10b]

Tiens, je trouve 30, moi, pas 31 ! (Bon d'accord, je n'ai pas pris un chemin très direct, mais j'ai beau recompter, je trouve toujours 30... Enfin, vu l'heure... )

5ème ligne, 10ème colonne ?

Hum, c'est la 26ème ça, mais c'est tout bon.

[juudku]

Pour être sûr que tu as trouvé la solution, dis-moi donc quelles sont les coordonnées de la 25ème case visitée (entre 1 et 10 pour x, idem pour y).
Et les autres auront un très bon indice pour trouver !

Tu doutes de moi ? Ca me fait beaucoup de peine... m'enfin au 25^e mouvement j'arrive à la 6^e ligne à la dernière colonne.

[Bételgeuse]

Je viens de modifier mon post d'avant pour te donner ma réponse ! (j'ai corrigé, c'était 6ème ligne, 10ème colonne. Je crois que je vais aller me coucher !)

[invite06fcc10b]

Tu doutes de moi ? Ca me fait beaucoup de peine... m'enfin au 25^e mouvement j'arrive à la 6^e ligne à la dernière colonne.

Ok, tu as été le premier, mes félicitations.
Les autres ont-ils trouvé ce fameux chemin optimal ?

[juudku]

Ca va, ça va, j'aurai le triomphe modeste...


J'oubliais:

[invite06fcc10b]

En fait, je me marre autant que vous, c'est ça qu'est bien, car le problème a l'air d'une simplicité enfantine, on peut même le poser à un enfant de 5 ans.
Mais malgré ça, il a tenu près de 3/4 d'heure !
En y regardant de plus près, l'erreur (humaine) qui est faite de façon quasi-systématique, c'est de vouloir aller chercher le $ sur la droite quand on est en haut. Or, les lignes sont plus hautes que les colonnes sont larges, ce qui fait qu'on a l'impression que ce qui est à droite est beaucoup plus proche que ce qui est en dessous et qu'il faut donc passer prendre le dollar de droite avant de descendre pour ne pas avoir à revenir plus tard vers le haut.
En fait, visuellement et donc intuitivement, la solution à 31 est plus courte (en centimètres), mais c'est la solution à 30 qui minimise vraiment les déplacements, c'est pour ça que j'ai dit qu'il ne fallait pas croire ses yeux !

[subichan]

haaa oui... j'ai du te relire 3 fois avant de comprendre ! mais c'est vrai, c'est logique...
bravo

[inviteba0a4d6e]

Bon, pour résumer, c'est quoi le chemin optimal en partant de X ?

[juudku]

Optimalistiquement il faut partir vers le haut et, arrivé au premier $, repartir vers le bas et NON vers la droite. Car aucune règle n'interdit de passer deux fois par la même case.

[matthias]

D'aller en haut, puis en bas en revenant sur ses pas, à doite, en haut.
Une fois que tu es en haut à gauche, et que tu te mets bien dans la tête que tu es dans un carré, ça devient presque évident.
Tellement évident que j'avais pas trouvé d'ailleurs
Vraiment sympa cette énigme.
Et bravo à juudku

[inviteba0a4d6e]

Ca me rappelle cette énigme (facile) : dessiner cette 'maison' sans lever une seule fois le crayon, et sans repasser deux fois sur le même trait...

[inviteba0a4d6e]

Ca me rappelle cette énigme (facile) : dessiner cette 'maison' sans lever une seule fois le crayon, et sans repasser deux fois sur le même trait...

Mon "casse-tête" n'inspire personne ?