Callcc/Guyslain/Teaching/ProgFonc/TP2016/TP2

Version & licenses
Creative Commons License
  1. {`author "Guyslain Naves"}
  2. {`date "Janvier 2014"}
  3. {`windowtitle "Programmation Fonctionnelle, TP2"}
  4. {`frametitle "Programmation Fonctionnelle, TP2 : Problème des n reines."}
  5. {`menu "progfonc"}


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

  15. {figure af://guyslain/images/Teaching/ProgFonc/8-queens.png {`width 400} Une solution}


  16. {section 4 Prédicat d'indépendance}

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

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

  24. Tester votre fonction sur des exemples.


  25. {section 4 Génération de la liste des positions}

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

  27. + {subframe Écrire une fonction récursive {verb {:range:}} pour définir une liste d'entiers consécutifs entre deux bornes. Par exemple :
  28. {code {`language "ocaml"} {:
  29. # let indices = range 1 8;;
  30. val indices : int list = [1; 2; 3; 4; 5; 6; 7; 8]
  31. :}}
  32. }
  33. + {subframe Écrire une fonction récursive {verb {:append:}} concaténant deux listes :
  34. {code {`language "ocaml"} {:
  35. # let res = append [3;2] [4;1;5];;
  36. val res : int list = [3; 2; 4; 1; 5]
  37. :}}
  38. }
  39. + {subframe Écrire une fonction récursive {verb {:couple:}} prenant un élément {verb {:a:}} et une liste {verb {:[b1; b2; ... bn]:}}, et qui s'évalue en la liste {verb {:[(a,b1);(a,b2);...;(a,bn)]:}}. Par exemple :
  40. {code {`language "ocaml"} {:
  41. # couple 1 indices;;
  42. - : (int * int) list =
  43. [(1, 1); (1, 2); (1, 3); (1, 4); (1, 5); (1, 6); (1, 7); (1, 8)]
  44. :}}
  45. }
  46. + {subframe Écrire une fonction récursive {verb {: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.
  47. {code {`language "ocaml"} {:
  48. # flatten [[1;2;3];[3;4;5];[1;2;3]];;
  49. - : int list = [1; 2; 3; 3; 4; 5; 1; 2; 3]
  50. :}}
  51. }
  52. + {subframe Écrire une fonction {verb {: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 {verb {:unflattened_product:}}, qui retourne une liste de listes de couples, à laquelle il suffira d'appliquer {verb {:flatten:}}.
  53. }
  54. + {subframe En déduire la liste des positions :
  55. {code {`language "ocaml"} {:
  56. # let positions = product indices indices;;
  57. val positions : (int * int) list =
  58. [(1, 1); (1, 2); (1, 3); (1, 4); (1, 5); (1, 6); (1, 7); (1, 8); (2, 1);
  59. (2, 2); (2, 3); (2, 4); (2, 5); (2, 6); (2, 7); (2, 8); (3, 1); (3, 2);
  60. (3, 3); (3, 4); (3, 5); (3, 6); (3, 7); (3, 8); (4, 1); (4, 2); (4, 3);
  61. (4, 4); (4, 5); (4, 6); (4, 7); (4, 8); (5, 1); (5, 2); (5, 3); (5, 4);
  62. (5, 5); (5, 6); (5, 7); (5, 8); (6, 1); (6, 2); (6, 3); (6, 4); (6, 5);
  63. (6, 6); (6, 7); (6, 8); (7, 1); (7, 2); (7, 3); (7, 4); (7, 5); (7, 6);
  64. (7, 7); (7, 8); (8, 1); (8, 2); (8, 3); (8, 4); (8, 5); (8, 6); (8, 7);
  65. (8, 8)]
  66. :}}
  67. }

  68. {section 4 Résolution}

  69. + Écrire une fonction {verb {:remove_dependant:}} prenant la position d'une reine et une liste de positions disponibles, et calcule la liste des positions disponibles et indépendantes de cette reine.
  70. + {subframe Nous voulons maintenant écrire la fonction de résolution. Pour cela, nous allons ajouter deux contraintes supplémentaires :
  71. - une liste de reines déjà placées,
  72. - une liste des positions encore disponibles où placer d'autres reines.

  73. Écrire une fonction récursive {verb {:solve:}} qui, prenant ces deux listes en arguments, calcule l'ensemble des solutions réalisables. Pour cela :
  74. + soit la liste des positions disponibles est vide, la liste des reines placées est une solution si elle contient 8 reines.
  75. + 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.
  76. }
  77. + Utiliser {verb {:solve:}} pour trouver la liste des solutions possibles. Vous devez en trouver 92.


  78. {section 4 Affichage}

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


  80. {code {:
  81. * . . . . . . .
  82. . . . . * . . .
  83. . . . . . . . *
  84. . . . . . * . .
  85. . . * . . . . .
  86. . . . . . . * .
  87. . * . . . . . .
  88. . . . * . . . .

  89. * . . . . . . .
  90. . . . . . * . .
  91. . . . . . . . *
  92. . . * . . . . .
  93. . . . . . . * .
  94. . . . * . . . .
  95. . * . . . . . .
  96. . . . . * . . .

  97. :}}

  98. Pour afficher avec la librairie {verb {:Graphics:}}, écrire une fonction {verb {:graphic_print_solution:}} prenant une solution en argument, et affichant cette solution, puis utiliser la définition suivante :
  99. {code {`language "ocaml"} {:
  100. let () =
  101. let print_and_wait_for_click solution =
  102. graphic_print_solution sol;
  103. ignore (Graphics.wait_next_event [Graphics.Button_Down])
  104. in
  105. List.iter print_and_wait_for_click all_solutions
  106. :}}

  107. {section 4 À vous de jouer}

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