Programmation Fonctionnelle, TP2

Version & licenses
Creative Commons License

Programmation Fonctionnelle, TP2 : Problème des n reines.

Guyslain Naves

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.

Une solution

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.

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]
  1. É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)]
  1. É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]
  1. É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 unflatten_product, qui retourne une liste de liste de couple, à laquelle on appliquera flatten.
  2. 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 is_valid prenant une liste de reines déjà placées, et une position, et s'évaluant en true si cette position est indépendante avec toutes les reines placées, en false sinon.
  2. En déduire une fonction filter_independant_positions qui prend la position d'une reine, et une liste de positions vides, et calcule la liste des positions vides qui ne sont pas menacées par cette reine.
  3. Écrire une fonction choose_queen_and_filter, prenant une liste de reines déjà placées, et une liste de positions vides et indépendantes vis-à-vis des reines. Pour chacune de ces positions, elle calcule une solution partielle, constituée de la liste des reines auquelle est ajoutée cette nouvelle position, et de la liste des cases encore vides et non menacée par la nouvelle reine. Les solutions partielles sont données sous forme d'une liste.
  4. Finalement écrire une fonction solve calculant toutes les solutions du problème des $8$-reines (vous devriez en trouver 92). La fonction solve prend en argument une liste de solutions partielles :
    • Si la première solution partielle n'a plus de case vide disponible, on compte le nombre de reines pour savoir si c'est une solution, et on calcule récursivement pour les autres solutions partielles de la liste
    • Si la première solution a encore des cases vides, on utilise choose_queen_and_filter pour calculer de nouvelles solutions partielles, qu'on ajoute au reste de la liste,
    • Si la liste de solutions partielles est vide, il n'y a plus de solutions à trouver.
  5. Évaluer la liste des solutions (si votre code est correct, cela devrait être presque instantané) :
  1. let all_solutions = solve [([],positions)]

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 :

  1. * . . . . . . .
  2. . . . . * . . .
  3. . . . . . . . *
  4. . . . . . * . .
  5. . . * . . . . .
  6. . . . . . . * .
  7. . * . . . . . .
  8. . . . * . . . .

  10. * . . . . . . .
  11. . . . . . * . .
  12. . . . . . . . *
  13. . . * . . . . .
  14. . . . . . . * .
  15. . . . * . . . .
  16. . * . . . . . .
  17. . . . . * . . .

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

  1. let _ =
  2. List.iter (fun sol -> graphic_print_solution sol; ignore (Graphics.wait_next_event [Graphics.Button_down]))
  3. all_solutions

À 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$.