SOLO-026 · Parcours hamiltonien
EXPERTLa traversée sans retour
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 | 29 | 30 | 31 | 32 | 33 | 36 |
| 2 | 28 | 27 | 26 | 25 | 34 | 35 |
| 3 | 21 | 22 | 23 | 24 | 1 | 2 |
| 4 | 20 | 19 | 18 | 17 | 16 | 3 |
| 5 | 11 | 12 | 13 | 14 | 15 | 4 |
| 6 | 10 | 9 | 8 | 7 | 6 | 5 |
Le raisonnement
- Du repère 1 au repère 4, la portion retenue est : 1 (L3C5) → 2 (L3C6) → 3 (L4C6) → 4 (L5C6). Vérifier chaque déplacement orthogonal, puis marquer les cases déjà consommées avant de poursuivre.
- Du repère 4 au repère 6, la portion retenue est : 4 (L5C6) → 5 (L6C6) → 6 (L6C5). Vérifier chaque déplacement orthogonal, puis marquer les cases déjà consommées avant de poursuivre.
- Du repère 6 au repère 9, la portion retenue est : 6 (L6C5) → 7 (L6C4) → 8 (L6C3) → 9 (L6C2). Vérifier chaque déplacement orthogonal, puis marquer les cases déjà consommées avant de poursuivre.
- Du repère 9 au repère 12, la portion retenue est : 9 (L6C2) → 10 (L6C1) → 11 (L5C1) → 12 (L5C2). Vérifier chaque déplacement orthogonal, puis marquer les cases déjà consommées avant de poursuivre.
- Du repère 12 au repère 21, la portion retenue est : 12 (L5C2) → 13 (L5C3) → 14 (L5C4) → 15 (L5C5) → 16 (L4C5) → 17 (L4C4) → 18 (L4C3) → 19 (L4C2) → 20 (L4C1) → 21 (L3C1). Vérifier chaque déplacement orthogonal, puis marquer les cases déjà consommées avant de poursuivre.
- Du repère 21 au repère 28, la portion retenue est : 21 (L3C1) → 22 (L3C2) → 23 (L3C3) → 24 (L3C4) → 25 (L2C4) → 26 (L2C3) → 27 (L2C2) → 28 (L2C1). Vérifier chaque déplacement orthogonal, puis marquer les cases déjà consommées avant de poursuivre.
- Du repère 28 au repère 36, la portion retenue est : 28 (L2C1) → 29 (L1C1) → 30 (L1C2) → 31 (L1C3) → 32 (L1C4) → 33 (L1C5) → 34 (L2C5) → 35 (L2C6) → 36 (L1C6). 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 423 états. Elle rejette 93 séparations des cases restantes et 83 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": 423,
"dead_ends": 17,
"connectivity_rejections": 93,
"distance_rejections": 83
}Coordonner les intervalles entre repères, les séparations de régions et les contraintes de parité. Le solveur doit explorer 423 préfixes ; le niveau reflète cette exploration combinée, sans assimiler automatiquement temps de calcul et difficulté humaine.