L'objectif de ce travail est de résoudre le problème de $n$ reines : sur un échiquier de taille $n \times n$, peut-on poser $n$ reines de telle sorte qu'aucune reine ne soit menacée par une autre reine ? Connaissant les règles des échecs, il faut donc placer les $n$ reines de sorte qu'il n'y ait jamais deux reines sur la même ligne, ni sur la même colonne, ni sur une même diagonale. Le TP demandera d'écrire plusieurs fonctions récursives sur les listes. Plus tard, nous apprendrons à utiliser les fonctionnelles de listes, et nous pourrons refaire ce TP bien plus simplement.

Prédicat d'indépendance

Chaque position sera encodée sous la forme d'un couple abscisse $\times$ ordonnée. Écrire une fonction independant prenant deux positions en argument, et retournant un booléen, indiquant si deux reines sur ces positions se menacent l'une l'autre.

Le cas des diagonales est le plus compliqué. Souvenez-vous que les lignes obliques du plan ont pour équations $x+y=c$ ou $x-y=c$ avec une constante $c$.

Tester votre fonction sur des exemples.

Génération de la liste des positions

Répondre aux questions suivantes, sans oublier d'écrire des tests à chaque fois.

1. Écrire une fonction récursive range pour définir une liste d'entiers consécutifs entre deux bornes. Par exemple :

   1. # let indices = range 1 8;;
      
   2. val indices : int list = [1; 2; 3; 4; 5; 6; 7; 8]
      
2. Écrire une fonction récursive append concaténant deux listes :

   1. # let res = append [3;2] [4;1;5];;
      
   2. val res : int list = [3; 2; 4; 1; 5]
      
3. Écrire une fonction récursive couple prenant un élément a et une liste [b1; b2; ... bn], et qui s'évalue en la liste [(a,b1);(a,b2);...;(a,bn)]. Par exemple :

   1. # couple 1 indices;;
      
   2. - : (int * int) list =
      
   3. [(1, 1); (1, 2); (1, 3); (1, 4); (1, 5); (1, 6); (1, 7); (1, 8)]
      
4. Écrire une fonction récursive flatten, prenant une liste de listes d'éléments, et qui s'évalue en la liste union de tous les éléments de ces listes, dans le même ordre.

   1. # flatten [[1;2;3];[3;4;5];[1;2;3]];;
      
   2. - : int list = [1; 2; 3; 3; 4; 5; 1; 2; 3]
      
5. Écrire une fonction product, prenant deux listes, et s'évaluant en la liste des couples dont le premier terme est choisi dans la première liste, et le second terme est choisi dans la deuxième liste. On écrira d'abord une fonction unflattened_product, qui retourne une liste de listes de couples, à laquelle il suffira d'appliquer flatten.

6. En déduire la liste des positions :

   1. # let positions = product indices indices;;
      
   2. val positions : (int * int) list =
      
   3. [(1, 1); (1, 2); (1, 3); (1, 4); (1, 5); (1, 6); (1, 7); (1, 8); (2, 1);
      
   4. (2, 2); (2, 3); (2, 4); (2, 5); (2, 6); (2, 7); (2, 8); (3, 1); (3, 2);
      
   5. (3, 3); (3, 4); (3, 5); (3, 6); (3, 7); (3, 8); (4, 1); (4, 2); (4, 3);
      
   6. (4, 4); (4, 5); (4, 6); (4, 7); (4, 8); (5, 1); (5, 2); (5, 3); (5, 4);
      
   7. (5, 5); (5, 6); (5, 7); (5, 8); (6, 1); (6, 2); (6, 3); (6, 4); (6, 5);
      
   8. (6, 6); (6, 7); (6, 8); (7, 1); (7, 2); (7, 3); (7, 4); (7, 5); (7, 6);
      
   9. (7, 7); (7, 8); (8, 1); (8, 2); (8, 3); (8, 4); (8, 5); (8, 6); (8, 7);
      
   10. (8, 8)]
       

Résolution

1. Écrire une fonction remove_dependant prenant la position d'une reine et une liste de positions disponibles, et calcule la liste des positions disponibles indépendantes de cette reine.
2. Nous voulons maintenant écrire la fonction de résolution. Pour cela, nous allons ajouter deux contraintes supplémentaires :

   • une liste de reines déjà placées,
   • une liste des positions encore disponibles où placer d'autres reines.

   Écrire une fonction récursive solve qui, prenant ces deux listes en arguments, calcule l'ensemble des solutions réalisables. Pour cela :

   1. soit la liste des positions disponibles est vide, la liste des reines placées est une solution si elle contient 8 reines.
   2. soit la liste des positions disponibles contient au moins une case : on peut alors choisir d'y placer ou pas une reine (deux appels récursifs). Dans le cas où on y place une reine, il faut supprimer de la liste des positions disponibles toutes les positions menacées par cette nouvelle reine. Dans l'autre cas, on supprime simplement la case laissée vide.
3. Utiliser solve pour trouver la liste des solutions possibles. Vous devez en trouver 92 .

Affichage

Créer une fonction pour afficher vos solutions. Vous pouvez utiliser au choix Printf.printf, ou bien la librairie Graphics. Deux solutions affichées avec Printf.printf :

Pour afficher avec la librairie Graphics, écrire une fonction graphic_print_solution prenant une solution en argument, et affichant cette solution, puis utiliser la définition suivante :

À vous de jouer

Généraliser votre code pour calculer les solutions du problème des $n$-reines, pour n'importe quelle valeur de $n$.