Enigme 4 cavaliers sur un morceau d'échiquier @ Prise2Tete

Oups! · #1

bonjour,

je n'ai pas trouvé cette énigme sur le forum mais peut-être me trompé-je...

Il s'agit de permuter la position des cavaliers noirs ("C" noirs) avec celle des cavaliers blancs ("C" blancs).

En combien de coups minimum pouvez-vous le faire ?

JJ

Klimrod · #2

Faisons le graphe des mouvements possibles :

Code:

                    / a3 fin
d2 - b3 - a1 - c2 <
                    \ b4 -a2 - c3 - a4 - b2 fin

Positionnons ensuite les chevaux sous ce graphe :

Code:

                      CB
                    / a3 fin
d2 - b3 - a1 - c2 <
CN   CN   CB        \ b4 -a2 - c3 - a4 - b2 fin

Le problème se résume à un jeu de locomotives sur une voie de garage. La voie de garage est la case a3 et il faut permuter les deux locomotives d2 et b3 avec les deux locomotives a1 et a3.

Les mouvements :
CB : a1 - c2 - b4 - a2 - c3
CN : b3 - a1 - c2 - b4 - a2
CN : d2 - b3 - a1 - c2 - b4
CB : a3 - c2 - a1 - b3 - d2 -> Ok pour le 1er CB
CN : b4 - c2 - a1 - b3
CN : a2 - b4 - c2 - a1
CB : c3 - a2 - b4 - c2 - a3
CN : a1 - c2 - b4 - a2
CN : b3 - a1 - c2 - b4
CB : a3 - c2 - a1 - b3 -> Ok pour le 2ème CB
CN : b4 - c2 - a1 - b3 -> Ok pour le 1er CN
CN : a2 - b4 - c2 - a1 -> Ok pour le 2ème CN

En tout, je fais 41 mouvements.... Peut-on faire mieux ?

Klim.

[Edit] Ooops ! Ta remarque ci-dessous est absolument exacte, je suis bête...
On reprend les mouvements :

CB : a1 - c2 - b4 - a2 - c3
CN : b3 - a1 - c2 - b4 - a2
CN : d2 - b3 - a1 - c2 - b4
CB : a3 - c2 - a1 - b3 - d2 -> Ok pour le 1er CB
CN : b4 - c2 - a1 - b3
CN : a2 - b4 - c2 - a1
CB : c3 - a2 - b4 - c2 - a3
CN : a1 - c2 - b4 - a2
CN : b3 - a1 - c2 - b4
CB : a3 - c2 - a1 - b3 -> Ok pour le 2ème CB
CN : b4 - c2 - a1 -> Ok pour le 1er CN
CN : a2 - b4 - c2 - a3 -> Ok pour le 2ème CN

Ainsi je fais 40 mouvements.... J'espère que c'est correct, maintenant...

En tout cas, bravo pour cette superbe idée d'énigme.
Klim.

gasole · #3

~~ça serait pas impossible par le plus grand des hasards ?~~

Le plus simple est de tracer le graphe des déplacements possibles d'un cavalier sur ce morceau d'échiquier puis de rendre le graphe planaire, car on y voit beaucoup mieux (j'ai utilisé Yed-Graph Editor pour faire ça).

Voici ce que ça donne (les cases bleues sont les points de départ des 2 cavaliers blancs et les grises celles des cavaliers noirs).

On voit très bien (après rappel à l'ordre) qu'il y a une solution en 42 mouvements

sur ce graphe qu'il est impossible en suivant les arêtes du graphe de permuter leur position, la case 3a servirait de voie de garage pour laisser passer les autres mais elle ne peut en stocker qu'un seul.

Mais il y a plus simple si l'on permet de poser deux cavaliers sur la même case, ce qui n'est pas explicitement interdit ma foi.

Ça me fait penser que j'en connais un autre du genre, je le ressortirai bientôt...

L00ping007 · #4

40 mouvements !

1. A1 => C2
2. C2 => B4
3. B4 => A2
4. A2 => C3
5. B3 => A1
6. D2 => B3
7. A1 => C2
8. B3 => A1
9. C2 => B4
10. A3 => C2
11. B4 => A2
12. C2 => B4
13. A1 => C2
14. C2 => A3
15. B4 => C2
16. C2 => A1
17. A1 => B3
18. B3 => D2
19. A2 => B4
20. C3 => A2
21. B4 => C2
22. A2 => B4
23. C2 => A1
24. B4 => C2
25. A1 => B3
26. C2 => A1
27. A3 => C2
28. C2 => B4
29. A1 => C2
30. B4 => A2
31. C2 => B4
32. B3 => A1
33. A1 => C2
34. C2 => A3
35. B4 => C2
36. C2 => A1
37. A1 => B3
38. A2 => B4
39. B4 => C2
40. C2 => A1

Ouf ! Y a mieux ? Je suis pas sûr ...

LeSingeMalicieux · #5

En dessinant un graphe qui montre les déplacements possibles, le problème devient beaucoup plus simple.
Par exemple, sur ce graphe, on voit clairement que depuis D2 on ne peux aller qu'en B3, puis seulement en A1, etc :

Le but est d'"empiler" les deux cavaliers blancs tout à gauche du graphe.
La solution la plus rapide est la suivante :

12 coups sont nécessaires pour permettre au cavalier blanc en A3 d'être "empilé" à gauche :

Puis 4 coups pour déplacer ce cavalier tout à gauche :

Ensuite 10 coups pour placer le second cavalier blanc en A3 :

6 coups pour déplacer les deux cavaliers noirs et libérer le passage pour le blanc :

3 coups pour "empiler" le second cavalier blanc à gauche :

Et enfin 5 coups pour arriver à la position finale demandée :

Ainsi, au total, il aura fallu 40 coups !

Excellente énigme

Oups! · #6

Klimrod : je te mets seulement bien car oui on peut faire mieux, il suffit de ne pas être étourdi !
Regarde les derniers mouvement du premier cavalier noir, (avant-dernière lignes des mouvements dans ta réponse).

gazole tu me dézole

L00ping007 très bien. D'autant mieux si la forme de ta réponse reflète ton raisonnement.

LeSingeMalicieux : très bien, illustration claire et concise.
================================================

En tout cas vous vous êtes bien appliqués. C'eut été moi, je n'aurais écrit que le nombre de mouvements (et encore).

Tant mieux, je n'aurais pas besoin de me farcir une réponse détaillée, vous l'avez fait pour moi. Merci beaucoup.

JJ

L00ping007 · #7

J'avoue que j'ai écrit un petit prog pour me donner une idée du résultat
Je poste quelque chose des que j'ai un raisonnement plus personnel !

Bon je dois me rendre à l'évidence, c'est trop compliqué pour moi
Je remarque bien qu'on commence d'abord par amener un cavalier en D2, en 18 mouvements, et qu'ensuite on s'occupe des 3 autres.
Mais rédiger un raisonnement sur les 40 coups ... Je n'ai pas d'échiquier sous la main, ça aide pas aussi, faut dire

gasole · #8

Oups! a écrit:
gazole tu me dézole

J'en suis ravi !

Et fais gaffe, je suis allergique aux ""

Oups! · #9

@gasole : la solution existe bien et beau. Ce qui me désole c'est que je considère que tu as donner la solution (enfin l'essentiel pour moi), le reste n'est que formalité... paperasse, scribouillis et autres tâches rébarbatives.

JJ

gasole · #10

lol chuis c*n, j'étais au bureau, j'ai fait un peu vite, ça m'apprendra à dire des trucs comme "on voit très bien"

Mea culpa, en plus (sur le graphe planaire) c'est super simple pfff :

J'ai consulté le Yi-King, on va dire 42 mouvements au pif

Oups! · #11

à gazole : pas loin ! On peut faire un peu mieux. (note : tu n'était pas obligé d'édité ton premier post pour supprimer la dernière ligne )

à Klimrod : on ne peut pas faire mieux...

gasole · #12

Moins que 42 ? Dommage, ça tombait bien, 42 étant la réponse à tout...

Ca prouve que le Yi-King n'est pas infaillible, et que je suis un flemmard , mais je vais m'en contenter je pense.

Bon, allez, 40 mais c'est mon dernier prix !

thedoums · #13

c'est surement pas le plus court, mais suisdéjà content d'avoir fini!
Je le fais en 50 coups...

Oups! · #14

@thedoums : je pense que tu as du voir qu'il existait une simplificiation maintenant...

Il fallait effectivement faire une représentation des chemins possibles des cavaliers et "dérouler" ce chemin en ligne pour plus de visualisation.
Ensuite il "suffisait" de résoudre un problème de train avec une voie de d'échappement, comme l'a dit Klimrod.

JJ

Oups! a écrit:
... Tant mieux, je n'aurais pas besoin de me farcir une réponse détaillée, vous l'avez fait pour moi. Merci beaucoup.

Bon, je me suis quand même farci une animation du résultat, pour le plaisir !

NOTE : la case parking est en A3.

L00ping007 · #15

Excellent, l'astuce !
Je n'y aurais jamais pensé, bravo.
J'adore l'explication du Singe

thedoums · #16

Maintenant oui, en regardant les solutions. Mais j'avoue que je n'ai pas plus chercher ne sachant pas ou je me situais... Un peu de suivi de l'énigme ne m'aurait pas fait de mal! Dommage que tu ne m'ais pas répondu plus tot...
Sinon sympa!

Oups! · #17

Oui, désolé pour le suivi. J'avais bien pensé à mettre un indice pour aiguiller vers l'astuce mais je m'y suis pris trop tard.

Tu as du t'amuser à trouver la solution sans la simplification...

thedoums · #18

Oui éffectivement me suis bien amusé!
N'ayant pas d'échiquier et de damier chez moi je te laisses imaginer comment j'ais fait... (post-it(s) sur la table et petite tasse sur les post-it(s))

Forum dédié aux énigmes et à toutes formes de jeux de logique.	Déconnexion
Tu n'es pas identifié sur Prise2tete : s'identifier. Accueil Forum	[+]

#1 - 15-03-2011 10:33:01

4 cavaliers sur un morrceau d'échiquier

#0 Pub

#2 - 15-03-2011 14:46:33

4 cavlaiers sur un morceau d'échiquier

Code:

Code:

#3 - 15-03-2011 15:31:47

4 cavaliers sur un morceau d'échisuier

#4 - 15-03-2011 16:46:18

4 cavaliers sur un morcrau d'échiquier

#5 - 15-03-2011 17:00:01

4 cavaliers sur un morceau d'échiquir

#6 - 15-03-2011 22:28:12

4 cavaliers sur un morceau s'échiquier

#7 - 15-03-2011 23:33:10

4 cavaliers sur un morceau d'échiqier

#8 - 15-03-2011 23:34:01

4 cavaliers sur un mocreau d'échiquier

Oups! a écrit:

#9 - 16-03-2011 00:05:54

4 cavaliers dur un morceau d'échiquier

#10 - 16-03-2011 01:01:19

4 cavaliers sur un mocreau d'échiquier

#11 - 16-03-2011 01:04:27

4 acvaliers sur un morceau d'échiquier

#12 - 16-03-2011 01:18:22

4 caavliers sur un morceau d'échiquier

#13 - 16-03-2011 12:15:18

4 cavaliers sur un morceau d'échiquizr

#14 - 18-03-2011 13:54:23

4 cavamiers sur un morceau d'échiquier

Oups! a écrit:

#15 - 18-03-2011 14:00:50

4 cavaliers su un morceau d'échiquier

#16 - 18-03-2011 14:06:42

4 cavaliers sur un morczau d'échiquier

#17 - 18-03-2011 16:04:31

4 cavaliers sur un morceau d'échiquiee

#18 - 18-03-2011 16:32:36

4 cavalieers sur un morceau d'échiquier

Réponse rapide

Sujets similaires

Mots clés des moteurs de recherche

Pied de page des forums