Le Grand LivreDES JEUX
← Les 40 défis

SOLO-027 · Parcours hamiltonien

EXTRÊME

Le labyrinthe sans murs

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.

Coordonnées : lignes du haut vers le bas, colonnes de gauche à droite.
L / C123456
15678910
242322212011
332425261912
42128271813
5353629301714
6343332311615

Le raisonnement

  1. Du repère 1 au repère 17, la portion retenue est : 1 (L4C2) → 2 (L4C1) → 3 (L3C1) → 4 (L2C1) → 5 (L1C1) → 6 (L1C2) → 7 (L1C3) → 8 (L1C4) → 9 (L1C5) → 10 (L1C6) → 11 (L2C6) → 12 (L3C6) → 13 (L4C6) → 14 (L5C6) → 15 (L6C6) → 16 (L6C5) → 17 (L5C5). Vérifier chaque déplacement orthogonal, puis marquer les cases déjà consommées avant de poursuivre.
  2. Du repère 17 au repère 23, la portion retenue est : 17 (L5C5) → 18 (L4C5) → 19 (L3C5) → 20 (L2C5) → 21 (L2C4) → 22 (L2C3) → 23 (L2C2). Vérifier chaque déplacement orthogonal, puis marquer les cases déjà consommées avant de poursuivre.
  3. Du repère 23 au repère 32, la portion retenue est : 23 (L2C2) → 24 (L3C2) → 25 (L3C3) → 26 (L3C4) → 27 (L4C4) → 28 (L4C3) → 29 (L5C3) → 30 (L5C4) → 31 (L6C4) → 32 (L6C3). Vérifier chaque déplacement orthogonal, puis marquer les cases déjà consommées avant de poursuivre.
  4. Du repère 32 au repère 33, la portion retenue est : 32 (L6C3) → 33 (L6C2). Vérifier chaque déplacement orthogonal, puis marquer les cases déjà consommées avant de poursuivre.
  5. Du repère 33 au repère 36, la portion retenue est : 33 (L6C2) → 34 (L6C1) → 35 (L5C1) → 36 (L5C2). Vérifier chaque déplacement orthogonal, puis marquer les cases déjà consommées avant de poursuivre.
  6. L’exploration de toutes les continuations compatibles donne 5682 états. Elle rejette 1042 séparations des cases restantes et 856 violations de distance ou de parité. Une seule visite complète subsiste.
  7. 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

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": 5682,
  "dead_ends": 102,
  "connectivity_rejections": 1042,
  "distance_rejections": 856
}

Coordonner les intervalles entre repères, les séparations de régions et les contraintes de parité. Le solveur doit explorer 5682 préfixes ; le niveau reflète cette exploration combinée, sans assimiler automatiquement temps de calcul et difficulté humaine.

← Revenir à l’énoncé SOLO-027