Bonjour tout le monde,
voici l'histoire d'une drôle d'aventure arrivée un éleveur de moutons ...
Dans une zone de sa bergerie, un éleveur dispose de sept cages alignés dans lesquelles on peut y mettre un mouton par cage.
Un soir, il avait enfermé six moutons comme le montre la figure ci-dessous : rien dans la 1ère cage, puis un mouton dans chaque cage suivante.
Chaque mouton étant différent et reconnaissable, on les numérote de 1 à 6.
Le lendemain matin, voilà la situation devant laquelle l'éleveur s'est retrouvé : toujours aucun mouton dans la 1ère cage, mais ensuite les moutons étaient dans l'ordre inverse, de 6 à 1 !!
Chaque mouton peut sauter dans une cage voisine si elle est vide, ou sauter au dessus d'un autre mouton pour se retrouver dans une cage vide.
Par exemple, pour débuter, le mouton 1 peut sauter dans la 1ère cage, ou le 2 au dessus du 1, etc ...
Question : donner la suite de sauts la plus courte pour que les moutons se retrouvent dans l'ordre inverse, la 1ère cage se retrouvant vide à la fin.
Pour la réponse, il suffit de donner la liste des moutons par leurs numéros, sans indiquer dans quelle cage ils vont puisque la possibilité est à chaque fois unique.
Par exemple, on peut commencer par : 1-3-2-4 ce qui conduit à l'arrangement "1-3-4-2-X-5-6".
S'il existe plusieurs solutions, vous n'en donnerez qu'une seule.
Si vous pensez que ce n'est pas possible, vous répondrez "problème impossible".
Bonne recherche !
Bonjour jamo,
Je propose :
2-4-6-5-3-1-2-4-6-5-3-1-2-4-6-5-3-1-2-4-6.
Merci encore pour toutes ces énigmes...
Dans 10 énigmes, on en sera à 1000 énigmes sur le site !!!
Bonjour Jamo.
123456 5646362616 12345 45352515 1234 342414 123 2313 2 123456
explication
1 2 3 4 5 6 décale les moutons vers la gauche; 123456X
5 6 4 6 3 6 2 6 1 6 les moutons dégagent l'un après l'autre le chemin pour le 6; 6x12345
1 2 3 4 5 même problème et même procédé, mais avec un mouton et une case de moins; 612345x
4 5 3 5 2 5 1 5; 65X1234
1 2 3 4; 651234X
3 4 2 4 1 4; 654x123
1 2 3; 654123x
2 3 1 3; 6543x12
2 tous les moutons sont bien ordonnés : 654321x; il suffit de les faire décaler vers la droite
123456
terminé en cinquante-trois coups !
Salut jamo,
2-1-3-1-4-1-5-1-6-1-6-5-4-3-2-3-2-4-2-5-2-6-2-6-5-4-3-4-3-5-3-6-3-6-5-4-5-4-6-4-5
cela fait 41 sauts
Bonne journée
Salut:
1-3-4-2 donne 1-3-X-4-2-5-6.
/
/
/
V
4-3-1-4 donne 4-1-X-3-2-5-6.
/
/
/
V
3-2-5-2 donne 4-1-3-X-5-2-6.
/
/
/
V
5-3-1-5 donne 4-5-1-X-3-2-6.
/
/
/
V
1-3-1-2 donne 4-5-3-2-1-X-6.
/
/
/
V
1-6-1-2 donne 4-5-3-X-6-2-1.
/
/
/
V
3-6-3-5 donne 4-X-6-5-3-2-1.
/
/
/
V
4-6-4-5 donne 6-5-4-X-3-2-1.
Enfin: 4-5-6 --> X-6-5-4-3-2-1. Et un de +.
Merci pour l'énigme, jamo!
Bonjour
J'ai mis 0 pour la case vide
départ 0123456
2103456
2143056
2143650
2143605
2140635
2146035
2106435
2016435
2610435
2601435
2641035
2641530
2641503
2640513
2604513
0624513
6024513
6420513
6425013
6405213
6450213
6452013
6452310
6452301
6450321
6054321
et
0654321
Bonjour/Bonsoir,
J'ai trouvé 21 coups avec la séquence 246531246531246531246
L'algorithme est particulièrement simple quand le nombre de moutons est pair :
1) déplacer tous les moutons pairs dans l'ordre croissant
2) déplacer tous les moutons impairs dans l'ordre décroissant
3) recommencer en 1) jusqu'à obtenir la position visée
pour un total de n*(n+1)/2 coups.
Ce qui donne avec 6 moutons :
_ _123456 : 0
2 21_3456 : 1
4 2143_56 : 2
6 214365_ : 3
5 21436_5 : 4
3 214_635 : 5
1 2_41635 : 6
2 _241635 : 7
4 42_1635 : 8
6 4261_35 : 9
5 426153_ : 10
3 42615_3 : 11
1 426_513 : 12
2 4_62513 : 13
4 _462513 : 14
6 64_2513 : 15
5 6452_13 : 16
3 645231_ : 17
1 64523_1 : 18
2 645_321 : 19
4 6_54321 : 20
6 _654321 : 21
et pour 8 moutons, 36 coups avec 246875312468753124687531246875312468
Merci pour vos énigmes.
Je propose une solution en 21 coups :
2-4-6-5-3-1 2-4-6-5-3-1 2-4-6-5-3-1 2-4-6
Je pense cette solution minimale, car elle correspond à 15 déplacements de type "permutation" (ce qui est le minimum requis pour inverser l'ordre des moutons), auxquels s'ajoutent 6 déplacements de "translation" (ce qui est le nombre de moutons).
Par ailleurs, le cycle 2-4-6-5-3-1 se répète, ainsi que le cycle des cases où sont situés les moutons à déplacer, qui se répète selon un cycle de 7 cases : 3-5-7-6-4-2-1, répété trois fois à l'identique (cases numérotées de 1 à 7 de gauche à droite, voir schéma...).
Merci pour cette énigme pleine de rebondissements .
Je ne trouve pas mieux que 23 coups...mais c'est sans certitude que je réponds :
2-1-3-4-1-2-3-4-5-6-1-2-3-4-5-6-2-3-4-5-6-4-5
Bonsoir,
voici en image les mouvements des moutons.
J'ai trouvé une solution en 21 coups avec la séquence 1-3-5-6-4-2-1-3-5-6-4-2-1-3-5-6-4-2-1-3-5
Bonjour à tous !
J'ai trouvé un minimum de 21 étapes en incluant la phase finale (X-6-5-4-3-2-1 ; X étant le vide)
Voici ces étapes :
X-1-2-3-4-5-6 (départ)
2-1-X-3-4-5-6
2-1-4-3-X-5-6
2-1-4-3-6-5-X
2-1-4-3-6-X-5
2-1-4-X-6-3-5
2-X-4-1-6-3-5
X-2-4-1-6-3-5
4-2-X-1-6-3-5
4-2-6-1-X-3-5
4-2-6-1-5-3-X
4-2-6-1-5-X-3
4-2-6-X-5-1-3
4-X-6-2-5-1-3
X-4-6-2-5-1-3
6-4-X-2-5-1-3
6-4-5-2-X-1-3
6-4-5-2-3-1-X
6-4-5-2-3-X-1
6-4-5-X-3-2-1
6-X-5-4-3-2-1
X-6-5-4-3-2-1
Et voilà ! Si je ne me suis pas trompé, on trouve 21 étapes. Je ne sais pas si c'est la solution optimale mais c'est le mini que j'ai trouvé...
Sur ce, merci pour l'énigmo !
Bonjour,
n'ayant pas bien compris l'exemple pour donner la réponse,je crains fortement le poisson...
j'ai écrit toutes les étapes (décalages de moutons compris pour laisser la bonne case vide). J'ai trouvé ainsi 23 étapes en comptant la position de départ et celle d'arrivée.
X 1 2 3 4 5 6 position de départ
1 X 2 3 4 5 6
1 3 2 X 4 5 6
1 3 2 5 4 X 6
X 1 3 2 5 4 6
3 1 X 2 5 4 6
3 1 5 2 X 4 6
3 1 5 2 6 4 X
3 X 1 5 2 6 4
3 5 1 X 2 6 4
3 5 1 6 2 X 4
X 3 5 1 6 2 4
5 3 X 1 6 2 4
5 3 6 1 X 2 4
5 3 6 1 4 2 X
5 X 3 6 1 4 2
5 6 3 X 1 4 2
5 6 3 4 1 X 2
X 5 6 3 4 1 3
6 5 X 3 4 1 2
6 5 4 3 X 1 2
6 5 4 3 2 1 X
X 6 5 4 3 2 1 le lendemain ...
merci pour cette énigme fermière ...
Bonjour.
J'ai trouvé qu'il est possible de faire 21 déplacements.
Voici comment procéder :
2-4-6-5-3-1-2-4-6-5-3-1-2-4-6-5-3-1-2-4-6.
Excusez-moi si ce n'est pas la solution, mais merci quand même pour l'énigme.
Bonjour Jamo,
sauf erreur(s) de programmation, voici une solution à 21 sauts:
2-1-3-5-6-4-1-2-3-5-6-4-1-2-3-5-6-4-2-3-5
Merci pour l'énigmo.
1_23456
132_456
13254_6
132546_
1325_64
13_5264
_315264
3_15264
351_264
35162_4
351624_
3516_42
35_6142
_536142
653_142
65341_2
653412_
6534_21
65_4321
6_54321
_654321
Bonjour,
Voici ma meilleure proposition à ce stade (sans garantie que ce soit l'optimum, mais je ne trouve pas mieux):
2-4-6-5-3-1-2-4-6-5-3-1-2-4-6-5-3-1-2-4-6
soit 21 sauts de moutons au total.
pas mieux...
Bonjour, alors voici ma proposition:
2-4-6-5-3-1-4-6-5-3-1-4-6-2-6-4-2-5-3-1-2-4-6
A moins qu'il existe une suite inférieure à celle-ci, il faudrait donc au minimum 23 sauts pour que les nombre s'inversent !
Re-bonjour Jamo
Je ne sais pas s'il s'agit de la solution optimale, mais pour faire vite, j'ai sorti les anneaux de mes tours de Hanoï
Ma séquence est la suivante 2-1-3-1-4-1-5-1-6-1-5-6-4-6-3-6-2-6-3-2-4-2-5-2-5-3-4-5-3-4-6
Bonjour Jamo,
Je ne crois pas pouvoir trouver plus court que 21 sauts : 2-4-6 - 5-3-1 - 2-4-6 - 5-3-1 - 2-4-6 - 5-3-1 - 2-4-6
séquence qui, comme chacun peut le remarquer, ne manque pas de structure !
Je me demande bien si c'est ça, ça me parais vraiment très long, désolée pour le dérangement mais je suis une novice en enigme
2-1-3-1-2-3-2-1-5-4-6-4-5-1-6-1-5-1-4-1-4-5-2-6-5-4-2-5-6-3-6-5-3-5-4-3-4-5-6
au départ
X123456
déplacements 1-3-5-6
132546X
déplacements 4-2-1
X315264
déplacements 3-5-6-4
351624X
déplacements 2-1-3
X536142
déplacements 5-6-4-2
563412X
déplacements 1-3-5
X654321
Je pense que cette solution apporte un déplacement minimal, vu comment les nombres 1,2,5, et 6 sont déplacés rapidement vers leur position idéale.
A part la "beauté" de l'apparition de la solution à la dernière série de 7, et l'obligation de faire passer la case vide d'un côté puis de l'autre rapidement, je n'ai pas d'argument mathématique qui permette d'assurer que c'est bien la plus rapide en nombre de déplacements.
Bonjour jamo
Je propose la série de 21 mouvements suivante :
2-4-6-5-3-1-2-4-6-5-3-1-2-4-6-5-3-1-2-4-6
Merci pour l'enigmo.
Il n'y avait donc pas d'erreur de programmations:
1 ère oartie:
DECLARE SUB Tri ()
DECLARE SUB Save ()
DECLARE FUNCTION net$ (n AS LONG, x AS INTEGER)
DECLARE SUB Init ()
DECLARE SUB See ()
DECLARE SUB AddItem ()
DECLARE SUB Visit (k AS INTEGER)
CONST n = 7
TYPE rec
s AS STRING * n
d AS STRING * 2
END TYPE
OPTION BASE 0
' $DYNAMIC
DIM SHARED per(0) AS STRING * n
'$STATIC
DIM SHARED donnee(n) AS INTEGER, nb AS LONG, nbrec AS LONG, level AS INTEGER, dir AS STRING
dir = "c:\_enigmo\238\p" + LTRIM$(STR$(n))
CLS
CALL Init
REDIM per(nbrec) AS STRING * n
CALL Visit(0)
CALL Tri
CALL Save
END
SUB Init
SHARED donnee() AS INTEGER, level AS INTEGER, nb AS LONG, nbrec AS LONG
DIM i AS INTEGER
level = -1
nb = 0
nbrec = 1
FOR i = 0 TO n - 1
nbrec = nbrec * (i + 1)
donnee(i) = 0
NEXT i
END SUB
FUNCTION net$ (p AS LONG, x AS INTEGER)
DIM st AS STRING
st = RIGHT$(SPACE$(x) + LTRIM$(STR$(p)), x)
net$ = st
END FUNCTION
SUB Save
SHARED per() AS STRING * n, dir AS STRING, nbrec AS LONG
DIM f AS STRING, del AS STRING * 2, buf1 AS rec, i AS LONG
del = CHR$(10) + CHR$(13)
f = dir + ".txt"
OPEN f FOR BINARY AS #1 LEN = LEN(rec)
buf1.s = net$(nbrec, n)
buf1.d = del
PUT #1, 1, buf1
FOR i = 1 TO nbrec
buf1.s = per(i)
buf1.d = del
PUT #1, 1 + i * LEN(buf1), buf1
NEXT i
buf1.s = "------"
buf1.d = CHR$(26)
PUT #1, 1 + (nbrec + 1) * LEN(buf1), buf1
CLOSE #1
END SUB
SUB See
SHARED per() AS STRING * n, nb AS LONG
DIM i AS INTEGER, st AS STRING
st = ""
FOR i = 0 TO n - 1
st = st + LTRIM$(STR$(donnee(i) - 1))
NEXT i
nb = nb + 1
per(nb) = st
END SUB
SUB Tri
SHARED per() AS STRING * n, nbrec AS LONG
DIM i AS LONG, j AS LONG
PRINT "tri en cours"
FOR i = 1 TO nbrec - 1
LOCATE 3, 1: PRINT i;
FOR j = i + 1 TO nbrec
LOCATE 3, 10: PRINT j;
IF per(i) > per(j) THEN
SWAP per(i), per(j)
END IF
NEXT j
NEXT i
END SUB
SUB Visit (k AS INTEGER)
SHARED level AS INTEGER, donnee() AS INTEGER
DIM i AS INTEGER
level = level + 1
donnee(k) = level
IF (level = n) THEN
CALL See
ELSE
FOR i = 0 TO n - 1
IF (donnee(i) = 0) THEN
CALL Visit(i)
END IF
NEXT i
END IF
level = level - 1
donnee(k) = 0
END SUB
2 ème partie:
DECLARE SUB Init ()
DECLARE FUNCTION IsIn& (p AS STRING)
DECLARE SUB Pause ()
DECLARE SUB MoveC (p AS STRING, way AS STRING)
DECLARE SUB Saute (p AS STRING, way AS STRING)
DECLARE SUB MoveA (p AS STRING, way AS STRING)
DECLARE SUB moveB (p AS STRING, way AS STRING)
DECLARE SUB MoveD (p AS STRING, way AS STRING)
DECLARE FUNCTION Dicho& (p AS STRING)
DECLARE SUB MoinsUn (way AS STRING)
DECLARE SUB IncPile ()
CONST Faux = (0 = 1)
CONST Vrai = NOT (Faux)
CONST n = 7
CONST deb = "0123456"
CONST fin = "0654321"
CONST MaxPile = 200
CONST MaxWay = 22
TYPE rec
s AS STRING * n
D AS STRING * 2
END TYPE
CLEAR , , 20000
'$DYNAMIC
DIM SHARED per(0) AS STRING * n, uper(0) AS INTEGER
'$STATIC
DIM SHARED Pile(MaxPile) AS LONG, nbPile AS INTEGER
DIM SHARED nb AS LONG, dir AS STRING
DIM SHARED min AS STRING
min = STRING$(500, 65)
nbPile = 0
dir = "c:\_enigmo\238\p" + LTRIM$(STR$(n))
DIM f AS STRING
f = dir + ".sol"
CLS
CALL Init
OPEN f FOR OUTPUT AS #2
CALL Saute(deb, "")
CLOSE #2
END
FUNCTION Dicho& (p AS STRING)
SHARED nb AS LONG, per() AS STRING * n
DIM rep AS LONG, a AS LONG, b AS LONG, m AS LONG
rep = Faux
a = 1
b = nb
DO WHILE (b - a) > 1
CALL Pause
m = INT((a + b) / 2)
SELECT CASE p
CASE IS = per(m)
rep = m
EXIT DO
CASE IS < per(m)
b = m
CASE ELSE
a = m
END SELECT
LOOP
Dicho& = rep
END FUNCTION
SUB Enter
INPUT y$
END SUB
SUB IncPile
SHARED nbPile AS INTEGER
nbPile = nbPile + 1
IF nbPile > MaxPile THEN
PRINT "Pile satur‚e"
END
END IF
END SUB
SUB Init
SHARED per() AS STRING * n, uper() AS INTEGER, nb AS LONG, dir AS STRING
DIM buf1 AS rec, i AS LONG, f AS STRING
f = dir + ".txt"
OPEN f FOR BINARY AS #1 LEN = LEN(buf1)
GET #1, 1, buf1
nb = VAL(buf1.s)
REDIM per(nb) AS STRING * n
REDIM uper(nb) AS INTEGER
FOR i = 1 TO nb
GET #1, 1 + LEN(buf1) * i, buf1
per(i) = buf1.s
uper(i) = Faux
NEXT i
CLOSE #1
END SUB
FUNCTION IsIn& (p AS STRING)
SHARED uper() AS INTEGER
DIM rep AS LONG, x AS LONG
rep = Faux
x = Dicho&(p)
IF x > 0 THEN
IF uper(x) THEN
rep = -x
ELSE
rep = x
END IF
END IF
IsIn& = rep
END FUNCTION
SUB MoinsUn (way AS STRING)
SHARED Pile() AS LONG, nbPile AS INTEGER, uper() AS INTEGER
DIM ch AS STRING: ch = RIGHT$(way, 1)
'PRINT "monsUn"; ch, nbPile, Pile(nbPile), up4(Pile(nbPile))
uper(Pile(nbPile)) = Faux
nbPile = nbPile - 1
END SUB
SUB MoveA (p AS STRING, way AS STRING)
SHARED Pile() AS LONG, nbPile AS INTEGER, uper() AS INTEGER
DIM a AS INTEGER, ch AS STRING * 1
DIM cle AS LONG, s AS STRING * n, w AS STRING
IF LEN(way) < MaxWay THEN
w = way
IF RIGHT$(w, 1) <> "B" THEN
s = p
a = INSTR(s, "0")
IF a < n THEN
ch = MID$(s, a + 1, 1)
MID$(s, a, 1) = ch
MID$(s, a + 1, 1) = "0"
cle = IsIn&(s)
IF cle > 0 THEN
CALL IncPile
Pile(nbPile) = cle
uper(cle) = Vrai
w = w + "A"
CALL Saute(s, w)
END IF
END IF
END IF
END IF
END SUB
SUB moveB (p AS STRING, way AS STRING)
SHARED Pile() AS LONG, nbPile AS INTEGER, uper() AS INTEGER
DIM a AS INTEGER, ch AS STRING * 1, s AS STRING * n, w AS STRING, cle AS LONG
IF LEN(way) < MaxWay THEN
w = way
IF RIGHT$(w, 1) <> "A" THEN
s = p
a = INSTR(s, "0")
IF a > 1 THEN
ch = MID$(s, a - 1, 1)
MID$(s, a, 1) = ch
MID$(s, a - 1, 1) = "0"
cle = IsIn&(s)
IF cle > 0 THEN
CALL IncPile
Pile(nbPile) = cle
uper(cle) = Vrai
w = w + "B"
CALL Saute(s, w)
END IF
END IF
END IF
END IF
END SUB
SUB MoveC (p AS STRING, way AS STRING)
SHARED Pile() AS LONG, nbPile AS INTEGER, uper() AS INTEGER
DIM a AS INTEGER, ch AS STRING * 1, s AS STRING * n, w AS STRING, cle AS LONG
IF LEN(way) < MaxWay THEN
w = way
IF RIGHT$(w, 1) <> "D" THEN
s = p
a = INSTR(s, "0")
IF a < n - 2 THEN
ch = MID$(s, a + 2, 1)
MID$(s, a, 1) = ch
MID$(s, a + 2, 1) = "0"
cle = IsIn&(s)
IF cle > 0 THEN
CALL IncPile
Pile(nbPile) = cle
uper(cle) = Vrai
w = w + "C"
CALL Saute(s, w)
END IF
END IF
END IF
END IF
END SUB
SUB MoveD (p AS STRING, way AS STRING)
SHARED Pile() AS LONG, nbPile AS INTEGER, uper() AS INTEGER
DIM a AS INTEGER, ch AS STRING * 1, s AS STRING * n, w AS STRING, cle AS LONG
IF LEN(way) < MaxWay THEN
w = way
IF RIGHT$(w, 1) <> "C" THEN
s = p
a = INSTR(s, "0")
IF a > 2 THEN
ch = MID$(s, a - 2, 1)
MID$(s, a, 1) = ch
MID$(s, a - 2, 1) = "0"
cle = IsIn&(s)
IF cle > 0 THEN
CALL IncPile
Pile(nbPile) = cle
uper(cle) = Vrai
w = w + "D"
CALL Saute(s, w)
END IF
END IF
END IF
END IF
END SUB
SUB Pause
y$ = INKEY$
IF y$ = CHR$(27) THEN END
END SUB
SUB Saute (p AS STRING, way AS STRING)
SHARED nbPile AS INTEGER, min AS STRING
DIM f AS STRING
LOCATE 1, 1: PRINT p; " "; way;
CALL Pause
IF LEN(way) > 200 THEN
PRINT "limite de way "; LEN(way)
END
END IF
IF p = fin THEN
LOCATE 5, 1: PRINT SPACE$(MaxWay + 10)
LOCATE 5, 1: PRINT way; "<"; LEN(way); ">";
IF LEN(way) < LEN(min) THEN
f = "<" + way + ">(" + STR$(LEN(way)) + ")"
min = way
LOCATE 3, 1: PRINT SPACE$(MaxWay + 10)
LOCATE 3, 1: PRINT min; "<"; LEN(min); ">";
PRINT #2, f
END IF
END IF
CALL MoveA(p, way)
CALL moveB(p, way)
CALL MoveC(p, way)
CALL MoveD(p, way)
CALL MoinsUn(way)
END SUB
Solution:
<CBCCADDDACCADDDACCBDD>( 21)
Je pensais avoir répondu à cette énigme, mais j'ai dû oublier (pas grave : j'aurai eu faux de toute façon : j'ai mal compris l'énoncé)
Mais c'est pas possible , il faut que j'apprenne à lire ! Je n'ai pas cherché la chaine la plus courte ! Je me disais bien que c'était trop facile.
Bravo à tous ceux qui ont trouvé
Cette fois j'ai un tout petit poisson (6 coups de trop)
Et comme Lousa j'admire le courage de caylus
Vous devez être membre accéder à ce service...
Pas encore inscrit ?
1 compte par personne, multi-compte interdit !
Ou identifiez-vous :