Parcours de cavalier (ou presque)

[Ben314]

Salut,
On vient de me poser cette énigme du type "parcours du cavalier" sur un échiquier :

On considère un pion placé sur un quadrillage qui, partant de la case de coordonnées peut se déplacer sur l'une des 8 cases de coordonnées , ou (sans sortir du quadrillage !!!)

1) Peut-on trouver un lacet (i.e. un chemin circulaire) passant une fois et une seule sur chaque case d'un quadrillage 10x10 ?

2) Même question (avec éventuellement un chemin non circulaire) avec un quadrillage .

P.S. : Je signale que (pour le moment) je n'y est absolument pas réfléchi et je n'ai pas regardé si c'était "connu" ou pas...

P.S.2 : La personne m'ayant posé l'énigme étant assez mignone, des réponses assez rapides serait fortement appréciées...

[beagle]

http://pagesperso-orange.fr/jb.guinot/pages/construction.html

pas vu si c'était circulaire.
Je regarderai plus tard.

[beagle]

cela ne semble pas aller jusqu'à 100,
et c'est pas circulaire.

Mais la construction des carrés latins d'ordre paire est pénble par rapport à la facilité des ordres impairs.

[Ben314]

cela ne semble pas aller jusqu'à 100,
et c'est pas circulaire.

Et c'est des déplacement de type "cavalier aux echecs" alors que ceux de l'énigme sont légèrement différents (ou alors il y a un lien entre les deux problèmes que je n'ai pas compris....)

Pour le moment, je pense avoir la "plus petite soluce possible" (circulaire) sur un 5x4 :
_0__7__4__1_18
10_13_16__9_12
_5__2_19__6__3
15__8_11_14_17

Et je regarde si il est possible de recoller des soluces par exemple pour faire un 8x5 ou un 4x10....

[beagle]

scuse moi Ben,
c'est journée migraine aujourd'hui, cela augmente ma capacité à raconter n'importe quoi.
j'ai cru que c'était cavalier aux échecs et dérivés.
Ceci étant j'avais tout faux car pour les impairs cela ne sort pas du carré si on projette le carré sur un tore, m'a gourré encore.

[Ben314]

...si on projette le carré sur un tore...

En plus, si je débarque vers la minette avec des arguments du type :
"En fait, je me place sur un quadrillage sur le tore parceque ça marche mieux et tout ça et tout ça..."
je sais pas si je marque vachement des points...
(je réserve plutôt ce type d'argument au forum... :zen:)

[scelerat]

P.S. : Je signale que (pour le moment) je n'y est absolument pas réfléchi et je n'ai pas regardé si c'était "connu" ou pas...

Ca semble s'appeler le parcours du kangourou.

P.S.2 : La personne m'ayant posé l'énigme étant assez mignone, des réponses assez rapides serait fortement appréciées...

C'est dans la poche, he he. :we:

[fatal_error]

salut,

tu pourras au pire lui dire que rien ne résiste à la brute force!

Voilà des sources, bien sûr, vers une grid taille 8 ca commence a devenir chaud.
Toujours est-il qu'on peut voir pas mal de possibilité pour les grid 5, 6, pe que ca pourra t'inspirer.

On peut parametrer lexe pour que la grille soit axb, avec a la largeur et b la hauteur, le maximum de passage par case, et le longueur du grand saut de cheval et du petit saut.

Pour lancer lexe (sous unix) dans le shell :

Code: Tout sélectionner

$: make rbAll && ./echiquier 5 4

Pour une grille 5x4

les sources

[scelerat]

Ca semble s'appeler le parcours du kangourou.

Frog, en anglais.
http://www.ktn.freeuk.com/9a.htm

[Ben314]

Merci pour tout...
- La "brute force" je sais pas si ca marque vachement des points... (ce qui ne m'empèce pas d'utiliser le programme pour voir les soluces puis une fois bien réfléchi, d'affirmer "tu vois, c'est façile..." :zen: )
- Sur le "kangourou", je suis tombés sur quelques sites avec des soluces (en particulier le 10x10 à l'aide de 5x5...)
- Attention, remarque trés importante !!!!! Le frog est un {1,1} + {0,3} ; le {2,2} + {0,3} est un des trois autres "small amphibian"...

Conclusion : le kangourou est un "small amphibian", mais ATTENTION, pas une grenouille, c'est un des trois autres !!! :zen: