Salut godefroy ,

Voici ma proposition en 58 déplacements :

C3-B3-B2-A2-A1-B1-C1-C2
C3-C2-C1-B1-B2-B3
C3-C4-B4-B5-A5-A4-A3-B3
C3-B3-A3-A4-B4-C4
C3-D3-D4-E4-E5-D5-C5-C4
C3-C4-C5-D5-D4-D3
C3-C2-D2-D1-E1-E2-E3-D3
C3-D3-E3-E2-D2-C2
C3-C2
C3

Merci.

Sans aucune méthode donc aucune certitude ...

aller : C3-C2-C1-B1-A1 retour : A2-A3-B3-C3   nettoyage C2-C1-B1-A1
aller : C3-B3-B2-A2-A3 retour : A4-B4-C4-C3 nettoyage B3-B2-A2-A3
aller : C3-C4-B4-A4-A5 retour : B5-C5-C4-C3 nettoyage B4-A4-A5
aller : C3-C4-C5-B5-C5 retour : D5-D4-D3-C3 nettoyage C4-C5-B5
aller : C3-D3-D4-D5-E5 retour : E4-E3-D3-C3   nettoyage D3-D4-D5-E5
aller : C3-D3-D4-E4-E3 retour : D3-C3 nettoyage E3-E4
aller : C3-D3-E3-E2-E1 retour : D1-D2-D3-C3 nettoyage E2-E1
aller : C3-D3-D2-D1-D2 retour : D3-C3 nettoyage D2-D1
aller : C3-D3 retour : C3 nettoyage D3-C3

Bonjour à tous,

Sans être certain d'avoir optimisé, voici (entre parenthèse, le nombre de déplacement de chaque excursion ; un '/' = un déplacement ; deux "/" = un déplacement et le réservoir se vide) :
C3/B3/A3/A2/A1 // B1/C1/C2/C3 (8)
C3/B3/B2/B1/C1 // C2/C3 (6)
C3/C2/D2/D1/E1 // E2/E3/D3/C3 (8)
C3/D3/D2/E2/E3 // D3/C3 (6)
C3/C4/D4/E4/E5 // D5/C5/C4/C3 (8)
C3/C4/C5/D5/C5 // C4/C3 (6)
C3/C4/B4/A4/A5 // B5/C5/C4/C3 (8)
C3/C4/B4/B5/C5 // C4/C3 (6)
C3/C4/C3 (2)

Pour unt total de 58 déplacements.

Merci pour l'énigme,

Tof

Bonjour
Aucune certitude quant à l'optimalité du chemin proposé, mais voici néanmoins une solution qui marche (entendez: qui nettoie tout!)

C3 C2 C1 D1 E1 E2 E3 D3
C3 D3 D2 E2 E3 E4 D4 C4
C3 C4 D4 E4 E5 D5 C5 C4
C3 C4 C5 D5 C5 B5 B4 B3
C3 B3 B4 B5 A5 A4 A3 B3
C3 B3 A3 A4 A3 A2 B2 C2
C3 B3 B2 A2 A1 B1 B2 B3
C3 B3 B2 B1 C1 C2 C3
C3 C2 C3

merci pour la joute !

Bonjour,

Voici ma proposition en 58 déplacements :
C2 - C1 - B1 - A1 - A2 - B2 - B3 - C3
C2 - B2 - A2 - A3 - B3 - C3
B3 - B4 - A4 - A5 - B5 - C5 - C4 - C3
B3 - B4 - B5 - C5 - C4 - C3
C4 - D4 - D5 - E5 - E4 - E3 - D3 - C3
C4 - D4 - E4 - E3 - D3 - C3
C2 - C1 - D1 - E1 - E2 - D2 - D3 - C3
C2 - D2 - E2 - E3 - D3 - C3
D3 - C3

Merci pour cette jolie énigme ...

Et en image, pour faciliter la correction :

oops -- le retour à C3 ne devrait pas apparaître à la fin de l'avant-dernière ligne, puisque chaque ligne *commence* par C3 dans la solution que j'ai proposée. redondance d'une case, sans déplacement, donc.

proverbe de pêcheur: qui trop vite répond, récolte des poissons...

Bonjour;

Je compte 60 déplacements:

C3 C2 C1 B1 A1 A2 A3 B3
C3 C2 C1 D1 E1 E2 E3 D3
C3 C4 C5 B5 A5 A4 A3 B3
C3 C4 C5 D5 E5 E4 E3 D3
C3 C2 B2 A2 A3 B3
C3 C2 D2 E2 E3 D3
C3 C4 B4 A4 A3 B3
C3 C4 D4 E4 E3 D3
C3 B3 C3 D3 C3

Bonsoir,

je voudrais tout d'abord faire une remarque préliminaire. Examinons la figure 1



on constate que chaque case du damier peut être atteinte d'une façon individuelle par un chemin aller-retour d'un certain nombre de cases.
Il y 4 cases dans les coins qui imposent un trajet minimum de 8 cases.
Si l'on considère que la machine lave immédiatement lorsqu'elle a quitté la case C3 (voir trajet bleu) elle ne peut atteindre dans le coin supérieur droit du carré qu'une case 8 et une case 6. L'autre case 6 en E2 doit faire l'objet d'un autre trajet. Cette situation se reproduit quatre fois: on a donc un trajet minimum de 4 x 8 cases + 4 x 6 cases = 56 cases . Il faut également laver la dernière case de sortie du trajet de 6 cases et la case C3, soit 2 cases. On a donc une solution de minimum 58 cases ou déplacements.
On arrive à la solution 1.
solution 1
On considère, comme le dit l'énoncé que "la machine ne commence son lavage proprement dit que lorsqu'elle a quitté la dalle C3". Elle lave immédiatement la dalle voisine de C3 ( voir figure 2)


En bleu on voit les dalles lavées,dans les cercles blancs les dalles de retour.
On a 9 trajets débutant en C3:
trajet 1  C2-C1-D1-E1-E2-D2-D3-C3
trajet 2  D3-E3-E2-D2-C2-C3
trajet 3  D3-E3-E4-E5-D5-D4-C4-C3
trajet 4  D3-D4-D5-C5-C4-C3
trajet 5  C4-C5-B5-A5-A4-B4-B3-C3
trajet 6  C4-B4-A4-A3-B3-C3
trajet 7  B3-A3-A2-A1-B1-B2-C2-C3
trajet 8  B3-B2-B1-C1-C2-C3
trajet 9  C2-C3
Il y a donc  58 déplacements

la solution 2considère un point qui n'est pas évoqué dans l'énoncé: on a dit "la machine ne commence son lavage proprement dit que lorsqu'elle a quitté la dalle C3". On n'a pas dit qu'elle devait commencer à laver immédiatement la case voisine de C3.
Elle pourrait donc de déplacer d'abord d'un certain nombre de dalles avant de démarrer le lavage.
On voit une solution donnée par la figure 2 ci-dessous qui  comporte 46 déplacements


On a 7 trajets débutant en C3:

trajet 1  C2-C1-D1-E1-E2-E3-D3-C3
trajet 2  D3-E3-E4-E5-D5-C5-C4-C3
trajet 3  C4-C5-B5-A5-A4-B4-B3-C3
trajet 4  B3-A3-A2-A1-B1-B2-C2-C3
trajet 5  C2-D2-D3-D4-C4-C3
trajet 6  C4-B4-B3-B2-C2-C3
trajet 7  C2-C3

Bien à vous

Bonjour tout le monde
Je propose ceci:
C3 C2 B2 A2 B2 C2 C3
C3 C4 B4 A4 B4 C4 C3
C3 C2 C1 B1 A1 A2 B2 C2 C3
C3 C4 C5 B5 A5 A4 B4 C4 C3
C3 C2 D2 E2 D2 C2 C3
C3 C4 D4 E4 D4 C4 C3
C3 C2 C1 D1 E1 E2 D2 C2 C3
C3 C4 C5 D5 E5 E4 D4 C4 C3
C3 D3 E3 D3 C3
C3 B3 A3 B3 C3
- C'est à dire 10 rotations et 64 cases traversées.

Bonjour,

Après avoir tourné en rond..

Je n'arrive pas à faire mieux que 58 mouvements

Les 4 angles 4X8
boucher les "trous" 4x6
finir au milieu 2

Bonjour Godefroy,

Après beaucoup d'hésitation...je prends le risque du poisson !!!

Je propose (en 58 mouvements):

B3 A3 A2 A1 B1 C1 C2 C3
C2 B2 B1 C1 C2 C3
C2 C1 D1 E1 E2 E3 D3 C3
D3 D2 E2 E3 D3 C3
D3 E3 E4 E5 D5 C5 C4 C3
C4 D4 D5 C5 C4 C3
C4 C5 B5 A5 A4 B4 C4 C3
B3 B4 A4 A3 B3 C3
B3 C3

Merci pour ce casse-tête...pour lequel le faible nombre de participants plaide en faveur d'un 3 étoiles..

A+

Bonjour Godefroy,

Le lundi n'est pas le jour du poisson, mais...

1: C3 B3 A3 A4 A5 B5 C5 C4 C3 : 8 déplacements.
2: C3 B3 B4 B5 C5 C4 C3       : 6
3: C3 C4 D4 D5 E5 E4 E3 D3 C3 : 8
4: C3 C4 D4 E4 E3 D3 C3       : 6
5: C3 D3 E3 E2 E1 D1 C1 C2 C3 : 8
6: C3 B3 A3 A2 A1 B1 C1 C2 C3 : 8
7: C3 D3 D2 D1 C1 C2 C3       : 6
8: C3 C2 C1 B1 B2 B3 C3       :6
9: C3 B3 C3                   :2 donc C3 est nettoyé.

4*8+4*6+2=32+24+2=58.

Il y a peut-être mieux mais je ne vois pas.(j'avais cette réponse le 14/09/2011 à 18h17 mais par peur du ridicule...)
Merci pour la joute.

Les coins étant éloignés de 4 déplacement, ils doivent être tentés en premier
et minimiser les retours effaçants.
Mix entre solitaire, combat naval et jeu de taquin/tetris

1 - C3, B3, A3, A2, A1, B1, C1, C2
2 - C3, C2, B2, B1, C1, D1, D2, D3
3 - C3, C4, B4, A4, A5, B5, C5, C4
4 - C3, D3, D2, D1, E1, E2, E3, D3
5 - C3, D3, E3, E2, E3, D3
6 - C3, C4, D4, E4, E5, D5, C5, C4
7 - C3, C4, C5, B5, C5, C4
8 - C3, C4, C5, D5, C5, C4, C3
9 - C3, C4, C3

Total 60 mouvements pour 25 cases
Aucune certitude que c'est un optimum

Salut Godefroy,

Je propose 58 déplacements, qui sont les suivants :

C3 C2 C1 B1 A1 A2 B2 B3
C3 C2 C1 D1 E1 E2 D2 D3
C3 B3 B2 A2 A3 B3
C3 D3 D2 E2 E3 D3
C3 B3 A3 A4 A5 B5 C5 C4
C3 D3 E3 E4 E5 D5 C5 C4
C3 B3 B4 B5 C5 C4
C3 D3 D4 D5 C5 C4
C3 C4
C3

Merci.

Bonjour,

Je propose :

C3 > C2 > B2 > B1 > A1 > A2 > A3 > B3 > C3

C3 > B3 > A3 > A2 > A3 > B3 > C3

C3 > B3 > B4 > A4 > A5 > B5 > C5 > C4 > C3

C3 > C4 > C5 > B5 > C5 > C4 > C3

C3 > C4 > D4 > D5 > E5 > E4 > E3 > D3 > C3

C3 > D3 > E3 > E4 > E3 > D3 > C3

C3 > D3 > D2 > E2 > E1 > D1 > C1 > C2 > C3

C3 > C2 > C1 > D1 > C1 > C2 > C3

C3 > C2 > C3

Soit 58 Déplacements

Clôture de l'énigme :

La recherche de l'optimum semble avoir fait reculer certains. Pourtant, elle n'était pas si difficile que ça.

Bonjour à tous,

Je suis vivement intéressé par un algorithme résolvant ce problème.
Peu importe le langage de programmation.
Merci d'avance.

Bonjour Godefroy,

J'ai contrôlé et contrôlé, mais mon parcours fait également 58 déplacements et laisse C3 nettoyé !!!

Pour chaque ligne je démarre de C3

Aurais-je omis quelque chose ?

Merci de contrôler

A+

Bonjour Rumbafan,

J'ai contrôlé une fois de plus (j'avais déjà vérifié 2 fois avant de mettre le poisson).
Il te manque la case C4 qui se resalit au cours du retour du 7ème passage.

Sur le dessin ci-dessous, les chiffres correspondent au numéro du passage.



Vraiment désolé

Re-salut

C4 reste sale...

Je n'avais pas 100%

B3 B4 A4 A3 B3 C3
était
B3 B4 A4 A3 C4 C3

Erreur de recopiage

Mea culpa



A+

Bonjour Caylus,

Je pense que personne n'a tenté de résoudre le problème par programmation.

D'abord parce qu'une telle résolution ne semble pas simple à réaliser.
Et ensuite, parce qu'elle conduirait probablement à une combinatoire explosive...
... sauf à introduire des règles de parcours qui limitent "intelligemment" le robot.

Mais pour déterminer ces règles "intelligentes" (comme par exemple, renoncer à tout cycle supérieur à 8 déplacements...) il faut d'abord faire une analyse mathématique du problème (à l'image de ce qu'a présenté très justement Castoriginal). Et en faisant cette analyse, on voit assez vite que 58 est le minimum théorique. Et comme en cherchant un peu, on trouve pas mal de solutions en 58... il n'est plus nécessaire de programmer.

Conclusion : la programmation ne semble pas adaptée pour trouver une solution plus rapidement qu'à la main...
Et le simple fait de réfléchir à une solution programmée "viable", nous met pratiquement sur la voie d'une solution manuelle...