SOLO-025 · Parcours hamiltonien
EXPERTLes relais muets
Numéroter toutes les cases de 1 à 36 pour former un unique parcours orthogonal sans répétition.
Corrigé — cette page contient la réponse.
La réponse exacte
Le numérotage complet ci-dessous détermine le seul parcours compatible.
| L / C | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|
| 1 | 1 | 2 | 3 | 4 | 5 | 6 |
| 2 | 12 | 11 | 10 | 9 | 8 | 7 |
| 3 | 13 | 20 | 21 | 22 | 23 | 24 |
| 4 | 14 | 19 | 28 | 27 | 26 | 25 |
| 5 | 15 | 18 | 29 | 32 | 33 | 36 |
| 6 | 16 | 17 | 30 | 31 | 34 | 35 |
Le raisonnement
- Du repère 1 au repère 8, la portion retenue est : 1 (L1C1) → 2 (L1C2) → 3 (L1C3) → 4 (L1C4) → 5 (L1C5) → 6 (L1C6) → 7 (L2C6) → 8 (L2C5). Vérifier chaque déplacement orthogonal, puis marquer les cases déjà consommées avant de poursuivre.
- Du repère 8 au repère 15, la portion retenue est : 8 (L2C5) → 9 (L2C4) → 10 (L2C3) → 11 (L2C2) → 12 (L2C1) → 13 (L3C1) → 14 (L4C1) → 15 (L5C1). Vérifier chaque déplacement orthogonal, puis marquer les cases déjà consommées avant de poursuivre.
- Du repère 15 au repère 18, la portion retenue est : 15 (L5C1) → 16 (L6C1) → 17 (L6C2) → 18 (L5C2). Vérifier chaque déplacement orthogonal, puis marquer les cases déjà consommées avant de poursuivre.
- Du repère 18 au repère 28, la portion retenue est : 18 (L5C2) → 19 (L4C2) → 20 (L3C2) → 21 (L3C3) → 22 (L3C4) → 23 (L3C5) → 24 (L3C6) → 25 (L4C6) → 26 (L4C5) → 27 (L4C4) → 28 (L4C3). Vérifier chaque déplacement orthogonal, puis marquer les cases déjà consommées avant de poursuivre.
- Du repère 28 au repère 33, la portion retenue est : 28 (L4C3) → 29 (L5C3) → 30 (L6C3) → 31 (L6C4) → 32 (L5C4) → 33 (L5C5). Vérifier chaque déplacement orthogonal, puis marquer les cases déjà consommées avant de poursuivre.
- Du repère 33 au repère 35, la portion retenue est : 33 (L5C5) → 34 (L6C5) → 35 (L6C6). Vérifier chaque déplacement orthogonal, puis marquer les cases déjà consommées avant de poursuivre.
- Du repère 35 au repère 36, la portion retenue est : 35 (L6C6) → 36 (L5C6). Vérifier chaque déplacement orthogonal, puis marquer les cases déjà consommées avant de poursuivre.
- L’exploration de toutes les continuations compatibles donne 613 états. Elle rejette 46 séparations des cases restantes et 221 violations de distance ou de parité. Une seule visite complète subsiste.
- Pour reproduire cette preuve sur papier, partir de 1, essayer chaque voisin libre dans l’ordre haut, bas, gauche, droite, et conserver une arborescence. Rejeter immédiatement un chemin qui atteint un repère au mauvais rang, isole une région non visitée ou ne peut rejoindre le prochain repère en autant de pas que requis. Le dernier chemin complet est celui affiché ; le validateur fourni réalise exactement cette exploration.
Fausses pistes et erreurs
- Une continuité locale ne suffit pas : un détour peut couper en deux les cases restant à visiter.
- Deux cases de même couleur sur un damier exigent un nombre pair de déplacements ; vérifier cette parité entre repères.
- Atteindre un repère trop tôt est aussi interdit que le manquer.
Comment cette réponse a été vérifiée
DFS exhaustive des chemins simples, avec contrôles nécessaires de connexité, repères, distance et parité ; comparaison de toutes les solutions jusqu’à deux.
{
"nodes": 613,
"dead_ends": 6,
"connectivity_rejections": 46,
"distance_rejections": 221
}Coordonner les intervalles entre repères, les séparations de régions et les contraintes de parité. Le solveur doit explorer 613 préfixes ; le niveau reflète cette exploration combinée, sans assimiler automatiquement temps de calcul et difficulté humaine.