\documentclass[10pt]{tpcaml}

% TP caml à LLG, Début Avril
% par Gabriel Scherer

\tp{5}{Parcours d'échiquier\\}
\usepackage{amsfonts}

\begin{document}

  \maketitle  


\subsection{Mouvements du cavalier}

On s'intéresse aux mouvements d'un cavalier dans un plan à deux
dimensions. Les mouvements du cavalier sont représentés par des
vecteurs \code{(int * int)}, et seuls les mouvements valides aux échecs (en ``L'') sont
autorisés.

\vspace{12pt}

\begin{question}
  Créer une liste \code{mouvements : (int * int) list} des mouvements possibles d'un cavalier.
\end{question}

\vspace{12pt}

\begin{question}
  Écrire ensuite la fonction \code{déplace : (int * int) -> (int *
    int) -> (int * int)} qui, étant donné une position de départ et un
  mouvement, renvoie les coordonnées de la position d'arrivée.  
\end{question}

\subsection{Gestion de l'échiquier}

On représente l'échiquier par une matrice de booléens \code{bool vect
  vect} : \code{echiq.(x).(y)} vaudra \code{true} si et seulement si
la case \code{(x,y)} est libre, c'est à dire que le cavalier n'y est
pas encore passé. Ce ne sera pas forcément un échiquier standard
(dimensions 8x8), ni forcément un échiquier carré. On essaiera d'avoir
un algorithme le plus performant possible, c'est à dire pouvant nous
apporter une réponse sur les plus gros échiquiers possibles (40x40 par
exemple).

\vspace{12pt}

\begin{question}
  Écrire une fonction \code{valide : (int * int) -> (int * int) ->
    bool} qui, étant donné les dimensions \code{(n,p)} d'un échiquier,
  indique si le couple \code{(x,y)} donné en deuxième paramètre est
  bien un couple d'indices valide (qui ne sort pas de la matrice)
\end{question}

\vspace{12pt}

\begin{question}
  Écrire une fonction \code{filter : ('a -> bool) -> 'a list -> 'a
    list} qui, étant donné une liste \code{li : 'a list} et un
  prédicat \code{p : ('a -> bool)}, renvoie la liste des éléments
  \code{x} de \code{li} tels que \code{p x = true}.
\end{question}

\vspace{12pt}

\begin{question}
  En déduire une fonction \code{deplacements\_valides : (int * int) ->
    (int * int) -> (int * int) list} qui, étant donné les dimensions
  de l'échiquier et un point de départ du cavalier, renvoie la liste
  des positions valides qu'il peut atteindre en un seul mouvement.

  Indice : vous pourrez utiliser la fonction \code{map}.
\end{question}

\vspace{12pt}


La case \code{(x,y)} de l'échiquier \code{echiq} est
\code{echiq.(x).(y)}. Pour les algorithmes qui vont suivre, vous êtes
encouragés à utiliser des fonctions auxiliaires pour pouvoir lire et
modifier les cases de l'échiquier sans avoir à décomposer le couple
position à chaque fois :\\
  \code{get : 'a vect vect -> (int * int) -> 'a}\\
  \code{set : 'a vect vect -> (int * int) -> 'a -> unit}

\section{Recherche}
\subsection{Existence d'une solution}

Dans un premier temps, on essaiera seulement de savoir si un solution
(un chemin qui passe une et une seule fois par chaque case de
l'échiquier) existe, sans essayer de donner le chemin correspondant :
c'est plus simple à coder.

On utilise pour cela la méthode du \emph{backtracking} (retour en
arrière) : pour trouver le bon chemin, on essaie tous les mouvements
possibles les uns après les autres et, si on se retrouve bloqué, on
revient en arrière en annulant certain mouvements pour explorer
d'autres possibilités.

On met en place un algorithme récursif : étant donné une position
libre de l'échiquier (position courante), le nombre de cases déjà
parcourues, et des informations sur les cases déjà parcourues (une
case est à \code{false} si elle a déjà été parcourue, \code{true} si
on peut encore y aller),
\begin{itemize}
\item si toutes les cases sauf une (la position courante) ont déjà été parcourues, on a gagné et on renvoie \code{true}
\item sinon
  \begin{itemize}
  \item on marque la position courante comme occupée
  \item on regarde si l'un des déplacements possibles depuis la position courante vers une case libre est une solution (appels récursifs)
  \item si aucun de ces essais n'a trouvé de solution, on revient en
    arrière : on efface le chemin emprunté (en marquant la position
    courante comme libre) et on renvoie \code{false}
  \end{itemize}
\end{itemize}

\vspace{12pt}

\begin{question}
  Trouver dans la documentation \camli une fonction qui permet de
  savoir si une liste contient au moins un élément satisfaisant la
  condition que l'on souhaite (ici, on voudra savoir si l'appel de
  notre algorithme sur une des destinations possibles du cavalier
  renvoie \code{true}, mais on veut juste une fonction générique pour
  l'instant).
  
  Si vous ne l'avez pas trouvée, codez-la vous-mêmes. Mais c'est mal !
\end{question}

\vspace{12pt}

  \begin{codesection}
    let resoudre dimensions =\\
\ \      let (n, p) = dimensions in\\
\ \      let echiquier = make\_matrix n p true in\\
\ \      let rec parcours nb\_parcourues pos =\\
\ \ \ \         ... (* votre code ici *)\\
\ \      in parcours 0 (0, 0);;
  \end{codesection}


\begin{question}
  Comprendre, puis implémenter cet algorithme.
  On pourra utiliser le squelette de code ci-contre.
\end{question}

Tester votre algorithme sur de petits échiquiers : 3x3, 4x4, 4x5, 6x6, 8x8.


\subsection{Trouver le chemin solution}

C'est très amusant de savoir que ``oui, il est possible de parcourir
un échiquier 8x8 avec un cavalier sans repasser deux fois par la même
case'', mais on aimerait bien que notre algorithme nous donne en plus
la liste des déplacements du cavalier.

On utilisera pour cela une deuxième matrice, \code{successeur : (int *
  int) vect vect}, qui stockera pour chaque case du chemin la case
suivante sur laquelle s'est rendu le cavalier. Quand on a trouvé une
solution, il suffit alors de suivre les informations de la matrice
\code{successeur} en partant de la case de départ pour reconstituer le
chemin complet du cavalier sur l'échiquier.

\vspace{12pt}

\begin{question}
  Modifier votre algorithme de parcours pour qu'à chaque fois qu'on
  essaie une case depuis la position courante, la valeur associée à la
  position courante dans \code{successeur} soit mise à jour.
\end{question}

\vspace{12pt}

\begin{question}\\
  Écrire une fonction \code{chemin : (int * int) vect vect -> (int * int) -> (int * int) list} qui, étant donné un tableau
  \code{successeur} et une position de départ, renvoie la liste des
  cases parcourues successivement.

  L'intégrer à votre fonction \code{résoudre} pour renvoyer le chemin
  solution quand il existe (et sinon par exemple la liste vide).
\end{question}

\vspace{12pt}

\begin{question}
  \paragraph{Question facultative : } écrire une fonction
  \code{affiche\_chemin} qui affiche le chemin solution d'une manière
  agréable; il faudrait que l'on puisse vérifier ``à l'oeil'' que
  c'est un chemin valide et qui remplit l'échiquier.

  On pourra prendre en paramètre les dimensions de la matrice, ou
  toute autre information facilement accessible à l'utilisateur, si on
  le souhaite.
\end{question}

\section{Heuristiques}

Comme vous le constatez sans doute, votre code marche (ou pas) mais il
est très lent. C'est normal, puisqu'on explore tous les chemins
possibles et que leur nombre croit exponentiellement avec les
dimensions de l'échiquier.

En remarquant que l'algorithme s'arrête dès qu'il trouve une solution,
au lieu de continuer à chercher toutes les solutions (vérifiez-le), on
va essayer de le modifier un peu pour que la solution soit parmis les
premiers chemins explorés. Autrement dit, on voudrait qu'au moment de
choisir les voisins de la position courante (les cases libres à un
mouvement de distance) à explorer, on essaie en premier les cases les
``meilleures'' (celles qui ont le plus de chance de faire partie du
chemin solution).

Le choix que l'on va faire ici est de choisir en premier les cases
ayant le moins de voisins libres. En quelque sorte, il vaut mieux
y passer le plus vite possible, parce qu'elles sont plus difficiles
à atteindre.

\vspace{12pt}

\begin{question}
  Modifier l'algorithme pour qu'il essaie en premier les cases
  voisines qui ont elles-mêmes le moins de voisins libres.

  Vous aurez sans doute besoin d'une fonction pour trier une liste
  selon le critère votre choix. Cherchez-la dans la documentation
  (standard libraries).
\end{question}

\vspace{12pt}

\begin{question}
  Améliorer un peu le critère de sélection : si deux cases sont
  à égalité (elles ont aussi peu de voisins libres l'une que l'autre),
  on choisit celle qui est la plus proche du bord de l'échiquier.
\end{question}

\section{Question difficile}
\begin{question}
  Écrire un \emph{quine}, un programme qui affiche exactement son propre code en sortie.
\end{question}

\end{document}
