Corrigé X-ENS 2025 Informatique B MP-PC-PSI — Partie II (Q5 à Q7) : Recherche exhaustive récursive

Q5. Ordonnons les cases par l'ordre lexicographique : $(i,j)\prec (i^{\prime },j^{\prime })$ si $i<i^{\prime }$, ou $i=i^{\prime }$ et $j<j^{\prime }$. La condition () dit exactement que $(i+\delta i,j+\delta j)\succ (i,j)$ : chaque saut fait passer à une case strictement plus grande. Les cases d'un chemin forment donc une suite strictement croissante* pour $\prec$ ; elles sont deux à deux distinctes, il y en a au plus $N^2$, et le chemin fait au plus $N^2-1$ sauts. D'où

$$L=N^2-1\text{ sauts, soit un chemin d’au plus }{N}^2\text{ cases.}$$

La borne est atteinte avec les sauts par défaut $\text{sauts}=[(0,1),(1,1-N)]$ et aucun bonus : le saut $(1,1-N)$ vérifie (*) puisque $\delta i=1>0$. Depuis une case $(i,j)$ avec $j<N-1$, seul le saut $(0,1)$ reste dans la grille ; depuis $(i,N-1)$ avec $i<N-1$, seul $(1,1-N)$ y reste et mène à $(i+1,0)$. Le seul chemin parcourt la grille ligne par ligne, visite les $N^2$ cases et fait $N^2-1$ sauts (pour $N=4$ : 15 sauts). Vérifié en exécutant Q6 avec ces sauts pour $N=1,\dots ,5$ : le chemin trouvé a bien $N^2-1$ sauts.

Ce que le correcteur attend : le rapport souligne que très peu de candidats ont pensé à un saut dépendant de $N$. Il est pourtant inévitable : un chemin de $N^2$ cases les visite toutes dans l'ordre $\prec$, donc passe de $(0,N-1)$ à $(1,0)$ par le saut $(1,1-N)$ ; pour $N⩾3$, des sauts à coordonnées dans $\{-1,0,1\}$ ne réalisent jamais $L$. La valeur $L$ compte des sauts, puisque l'horizon sauts_max borne la longueur de la liste sauts_min. Si l'on compte les cases, la réponse est $N^2$.

Q6. Convention. Le chemin exploré depuis $(i,j)$ s'arrête dans deux cas seulement : il atteint l'arrivée $(N-1,N-1)$, ou il a épuisé l'horizon. Une branche bloquée avant (aucun saut ne reste dans la grille) ne fournit aucun chemin, et la fonction renvoie alors (INFINI, []). C'est la seule lecture compatible avec la suite du sujet. Si l'on pouvait s'arrêter n'importe où, l'appel avec l'horizon $L$ choisirait volontiers un chemin qui s'arrête sur une case négative, ici $(3,2)$, au lieu de payer le $7$ de l'arrivée (le minimum serait $-14$ et non $-7$). Accepter seulement les arrêts sur une case sans issue n'est pas mieux : une impasse de poids négatif serait préférée à l'arrivée, et l'appel avec l'horizon $L$ ne donnerait plus « la recherche exhaustive d'un chemin optimal » annoncée par le sujet. La partie III, de son côté, a besoin d'un cas d'échec (« ne trouve pas de suite locale »).