{ "cells": [ { "cell_type": "markdown", "metadata": { "toc": "true" }, "source": [ "# Table of Contents\n", "

1  Bonus d'implémentation - Agrégation Option Informatique
1.1  Préparation à l'agrégation - ENS de Rennes, 2017-18
1.2  À propos de ce document
1.3  Vérifier qu'un Su Doku est correct
1.3.1  Fonctions utilitaires
1.3.2  Contraintes sur les lignes et les colonnes
1.3.3  Contraintes sur les carrés
1.3.4  Contraintes globales
1.4  Exemples de \"score\"
1.4.1  Un exemple de Su Doku de taille 9×9\" role=\"presentation\">9×99×9 au compte juste
1.4.2  Un exemple de Su Doku au comte faux
1.4.3  Un exemple de comte... Dooku ?
1.5  Algorithme génétique
1.5.1  Configuration
1.5.2  Génération d'individus, mutations
1.5.3  Algorithme génétique
1.5.4  Essai
1.6  Conclusion
" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# Bonus d'implémentation - Agrégation Option Informatique\n", "## Préparation à l'agrégation - ENS de Rennes, 2017-18\n", "- *Date* : 20 février 2018\n", "- *Auteur* : [Lilian Besson](https://GitHub.com/Naereen/notebooks/)\n", "- *Texte*: Annale 2006, \"Sudoku\"" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## À propos de ce document\n", "- Ceci est une *proposition* d'un bonus d'implémentation, pour un [texte d'annale de l'agrégation de mathématiques, option informatique](http://Agreg.org/Textes/).\n", "- Ce document est un [notebook Jupyter](https://www.Jupyter.org/), et [est open-source sous Licence MIT sur GitHub](https://github.com/Naereen/notebooks/tree/master/agreg/), comme les autres solutions de textes de modélisation que [j](https://GitHub.com/Naereen)'ai écrite cette année.\n", "- L'implémentation sera faite en OCaml, version 4+ :" ] }, { "cell_type": "code", "execution_count": 1, "metadata": { "scrolled": true }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "The OCaml toplevel, version 4.04.2\n" ] }, { "data": { "text/plain": [ "- : int = 0\n" ] }, "execution_count": 1, "metadata": {}, "output_type": "execute_result" } ], "source": [ "Sys.command \"ocaml -version\";;" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "---\n", "## Vérifier qu'un Su Doku est correct\n", "- On va implémenter rapidement la vérification des contraintes d'un Su Doku.\n", "- En plus de répondre binairement si le Su Doku est correct, en comptant le nombre de contraintes satisfaites, on a une mesure numérique qu'on doit faire augmenter pour résoudre le Su Doku." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Fonctions utilitaires" ] }, { "cell_type": "code", "execution_count": 14, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "val ligne : int -> 'a array array -> int -> 'a array = \n" ] }, "execution_count": 14, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "val colonne : int -> 'a array array -> int -> 'a array = \n" ] }, "execution_count": 14, "metadata": {}, "output_type": "execute_result" } ], "source": [ "let ligne p t i = Array.init p (fun j -> t.(i).(j)) ;;\n", "(* t.(i) marche aussi bien ! *)\n", "\n", "let colonne p t j = Array.init p (fun i -> t.(i).(j)) ;;" ] }, { "cell_type": "code", "execution_count": 15, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "val tousVrai : bool array -> bool = \n" ] }, "execution_count": 15, "metadata": {}, "output_type": "execute_result" } ], "source": [ "let tousVrai = Array.for_all (fun x -> x);;" ] }, { "cell_type": "code", "execution_count": 16, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "val estNp : int -> int array -> bool = \n" ] }, "execution_count": 16, "metadata": {}, "output_type": "execute_result" } ], "source": [ "let estNp p tab =\n", " if tousVrai (Array.map (fun x -> (1 <= x) && (x <= p)) tab) then begin \n", " let estLa = Array.make p false in\n", " for i = 0 to p - 1 do\n", " estLa.(tab.(i) - 1) <- true\n", " done;\n", " tousVrai estLa\n", " end\n", " else\n", " false\n", ";;" ] }, { "cell_type": "code", "execution_count": 24, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "val sum_array : int array -> int = \n" ] }, "execution_count": 24, "metadata": {}, "output_type": "execute_result" } ], "source": [ "let sum_array = Array.fold_left (+) 0;;" ] }, { "cell_type": "code", "execution_count": 25, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "val estNp_compte : int -> int array -> int = \n" ] }, "execution_count": 25, "metadata": {}, "output_type": "execute_result" } ], "source": [ "let estNp_compte p tab =\n", " if tousVrai (Array.map (fun x -> (1 <= x) && (x <= p)) tab) then begin \n", " let estLa = Array.make p 0 in\n", " for i = 0 to p - 1 do\n", " estLa.(tab.(i) - 1) <- 1\n", " done;\n", " sum_array estLa\n", " end\n", " else\n", " 0\n", ";;" ] }, { "cell_type": "code", "execution_count": 26, "metadata": { "scrolled": true }, "outputs": [ { "data": { "text/plain": [ "val racine_carree : int -> int = \n" ] }, "execution_count": 26, "metadata": {}, "output_type": "execute_result" } ], "source": [ "let racine_carree i = int_of_float (sqrt (float_of_int i));;" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Contraintes sur les lignes et les colonnes" ] }, { "cell_type": "code", "execution_count": 18, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "val contraintes_lignes : int -> int array array -> bool = \n" ] }, "execution_count": 18, "metadata": {}, "output_type": "execute_result" } ], "source": [ "let contraintes_lignes p t =\n", " tousVrai (Array.init p (fun i ->\n", " estNp p (ligne p t i)\n", " ))\n", ";;" ] }, { "cell_type": "code", "execution_count": 27, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "val contraintes_lignes_compte : int -> int array array -> int = \n" ] }, "execution_count": 27, "metadata": {}, "output_type": "execute_result" } ], "source": [ "let contraintes_lignes_compte p t =\n", " sum_array (Array.init p (fun i ->\n", " estNp_compte p (ligne p t i)\n", " ))\n", ";;" ] }, { "cell_type": "code", "execution_count": 19, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "val contraintes_colonnes : int -> int array array -> bool = \n" ] }, "execution_count": 19, "metadata": {}, "output_type": "execute_result" } ], "source": [ "let contraintes_colonnes p t =\n", " tousVrai (Array.init p (fun j ->\n", " estNp p (colonne p t j)\n", " ))\n", ";;" ] }, { "cell_type": "code", "execution_count": 28, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "val contraintes_colonnes_compte : int -> int array array -> int = \n" ] }, "execution_count": 28, "metadata": {}, "output_type": "execute_result" } ], "source": [ "let contraintes_colonnes_compte p t =\n", " sum_array (Array.init p (fun j ->\n", " estNp_compte p (colonne p t j)\n", " ))\n", ";;" ] }, { "cell_type": "code", "execution_count": 20, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "val carre_latin : int -> int array array -> bool = \n" ] }, "execution_count": 20, "metadata": {}, "output_type": "execute_result" } ], "source": [ "let carre_latin p t =\n", " (contraintes_lignes p t) && (contraintes_colonnes p t)\n", ";;" ] }, { "cell_type": "code", "execution_count": 29, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "val carre_latin_compte : int -> int array array -> int = \n" ] }, "execution_count": 29, "metadata": {}, "output_type": "execute_result" } ], "source": [ "let carre_latin_compte p t =\n", " (contraintes_lignes_compte p t) + (contraintes_colonnes_compte p t)\n", ";;" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Contraintes sur les carrés" ] }, { "cell_type": "code", "execution_count": 21, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "val petit_carre : int -> int -> 'a array array -> int -> int -> 'a array =\n", " \n" ] }, "execution_count": 21, "metadata": {}, "output_type": "execute_result" } ], "source": [ "let petit_carre p n t i j =\n", " Array.init p (fun k ->\n", " t.(n*i + (k / n)).(n*j + (k mod n))\n", " )\n", ";;" ] }, { "cell_type": "code", "execution_count": 22, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "val petits_carres_sont_latins : int -> int array array -> bool = \n" ] }, "execution_count": 22, "metadata": {}, "output_type": "execute_result" } ], "source": [ "let petits_carres_sont_latins p t =\n", " let n = racine_carree p in\n", " (* Par flemme, on créé le tableau entier, qu'on vérifie après *)\n", " let contraintes_petits_carres =\n", " Array.init p (fun i ->\n", " estNp p (petit_carre p n t (i / n) (i mod n) )\n", " )\n", " in\n", " (* Mais on peut mieux faire, avec une boucle while par exemple, on sort dès qu'une contrainte est fausse *)\n", " tousVrai contraintes_petits_carres\n", ";;" ] }, { "cell_type": "code", "execution_count": 31, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "val petits_carres_sont_latins_compte : int -> int array array -> int = \n" ] }, "execution_count": 31, "metadata": {}, "output_type": "execute_result" } ], "source": [ "let petits_carres_sont_latins_compte p t =\n", " let n = racine_carree p in\n", " let contraintes_petits_carres =\n", " Array.init p (fun i ->\n", " estNp_compte p (petit_carre p n t (i / n) (i mod n) )\n", " )\n", " in\n", " sum_array contraintes_petits_carres\n", ";;" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Contraintes globales" ] }, { "cell_type": "code", "execution_count": 32, "metadata": { "scrolled": true }, "outputs": [ { "data": { "text/plain": [ "val est_resolu : int -> int array array -> bool = \n" ] }, "execution_count": 32, "metadata": {}, "output_type": "execute_result" } ], "source": [ "let est_resolu p t =\n", " (carre_latin p t) && (petits_carres_sont_latins p t)\n", ";;" ] }, { "cell_type": "code", "execution_count": 50, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "val nb_contraintes_resolues : int -> int array array -> int = \n" ] }, "execution_count": 50, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "val score : int -> int array array -> int = \n" ] }, "execution_count": 50, "metadata": {}, "output_type": "execute_result" } ], "source": [ "let nb_contraintes_resolues p t =\n", " (carre_latin_compte p t) + (petits_carres_sont_latins_compte p t)\n", ";;\n", "\n", "let score = nb_contraintes_resolues;;" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "---\n", "## Exemples de \"score\"" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Un exemple de Su Doku de taille $9 \\times 9$ au compte juste\n", "\n", "Avec $p = n^2 = 9$, on reprend l'exemple du texte :\n", "\"images/sudoku.png\"\n", "\n", "Ça va être long un peu à écrire, mais au moins on vérifiera notre fonction sur un vrai exemple." ] }, { "cell_type": "code", "execution_count": 49, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "val p : int = 9\n" ] }, "execution_count": 49, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "val t : int array array =\n", " [|[|1; 2; 7; 4; 6; 3; 9; 8; 5|]; [|3; 4; 9; 8; 7; 5; 2; 6; 1|];\n", " [|5; 8; 6; 2; 9; 1; 4; 3; 7|]; [|7; 6; 5; 9; 4; 2; 3; 1; 8|];\n", " [|8; 3; 4; 7; 1; 6; 5; 2; 9|]; [|9; 1; 2; 5; 3; 8; 7; 4; 6|];\n", " [|2; 7; 8; 6; 5; 4; 1; 9; 3|]; [|4; 5; 3; 1; 8; 9; 6; 7; 2|];\n", " [|6; 9; 1; 3; 2; 7; 8; 5; 4|]|]\n" ] }, "execution_count": 49, "metadata": {}, "output_type": "execute_result" } ], "source": [ "let p = 9 ;;\n", "let t = [|\n", " [| 1; 2; 7; 4; 6; 3; 9; 8; 5 |];\n", " [| 3; 4; 9; 8; 7; 5; 2; 6; 1 |];\n", " [| 5; 8; 6; 2; 9; 1; 4; 3; 7 |];\n", " [| 7; 6; 5; 9; 4; 2; 3; 1; 8 |];\n", " [| 8; 3; 4; 7; 1; 6; 5; 2; 9 |];\n", " [| 9; 1; 2; 5; 3; 8; 7; 4; 6 |];\n", " [| 2; 7; 8; 6; 5; 4; 1; 9; 3 |];\n", " [| 4; 5; 3; 1; 8; 9; 6; 7; 2 |];\n", " [| 6; 9; 1; 3; 2; 7; 8; 5; 4 |];\n", "|];" ] }, { "cell_type": "code", "execution_count": 55, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "val score_max : int = 243\n" ] }, "execution_count": 55, "metadata": {}, "output_type": "execute_result" } ], "source": [ "let score_max = 3 * 9 * 9;;" ] }, { "cell_type": "code", "execution_count": 56, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "- : int = 243\n" ] }, "execution_count": 56, "metadata": {}, "output_type": "execute_result" } ], "source": [ "score p t;;" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Un exemple de Su Doku au *comte* faux\n", "\n", "Avec $p = n^2 = 9$, en modifiant seulement une case du tableau $T$ précédent." ] }, { "cell_type": "code", "execution_count": 57, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "val p : int = 9\n" ] }, "execution_count": 57, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "val t : int array array =\n", " [|[|1; 2; 7; 4; 6; 3; 9; 8; 5|]; [|3; 4; 9; 8; 7; 5; 2; 6; 1|];\n", " [|5; 8; 6; 2; 9; 1; 4; 3; 7|]; [|7; 6; 5; 9; 4; 2; 3; 1; 8|];\n", " [|8; 2; 4; 7; 1; 6; 5; 2; 9|]; [|9; 1; 2; 5; 3; 8; 7; 4; 6|];\n", " [|2; 7; 8; 6; 5; 4; 1; 9; 3|]; [|4; 5; 3; 1; 8; 9; 6; 7; 2|];\n", " [|6; 9; 1; 3; 2; 7; 8; 5; 4|]|]\n" ] }, "execution_count": 57, "metadata": {}, "output_type": "execute_result" } ], "source": [ "let p = 9 ;;\n", "let t = [|\n", " [| 1; 2; 7; 4; 6; 3; 9; 8; 5 |];\n", " [| 3; 4; 9; 8; 7; 5; 2; 6; 1 |];\n", " [| 5; 8; 6; 2; 9; 1; 4; 3; 7 |];\n", " [| 7; 6; 5; 9; 4; 2; 3; 1; 8 |];\n", " [| 8; 2; 4; 7; 1; 6; 5; 2; 9 |]; (* Ligne non valable, 2 est là deux fois !*)\n", " [| 9; 1; 2; 5; 3; 8; 7; 4; 6 |];\n", " [| 2; 7; 8; 6; 5; 4; 1; 9; 3 |];\n", " [| 4; 5; 3; 1; 8; 9; 6; 7; 2 |];\n", " [| 6; 9; 1; 3; 2; 7; 8; 5; 4 |];\n", "|];" ] }, { "cell_type": "code", "execution_count": 60, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "- : int = 240\n" ] }, "execution_count": 60, "metadata": {}, "output_type": "execute_result" } ], "source": [ "score p t;;" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "On voit que 3 contraintes ne sont pas vérifiées." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Un exemple de comte... Dooku ?\n", "\n", "[![http://fr.starwars.wikia.com/wiki/Dooku ?](images/dooku.jpg)](http://fr.starwars.wikia.com/wiki/Dooku)\n", "\n", "> *Nan, je déconne*.\n", "> ... Bien-sûr, évitez les blagues pourries le jour de l'oral !\n", "> Mais une bonne blague peut être bien reçue..." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "----\n", "## Algorithme génétique\n", "- Maintenant qu'on peut mesurer à quelle \"distance\" on est d'un Su Doku complètement résolu (on appelera ça un *score* - ou \"fitness\" en anglais), on peut essayer de compléter aléatoirement la grille par [algorithme génétique](https://fr.wikipedia.org/wiki/Algorithme_génétique).\n", "- Rappel de l'idée :\n", " 1. on commence avec la grille, on fait N (= 100) fois un petit changement pour avoir une population initiale de solutions,\n", " 2. pour G générations, on garde N1 (= 45) individus, inchangés, on efface N2 (= 10) individus qu'on retirera aléatoirement à partir de la grille initiale, et on fait \"muter\" (N3 = 45) individus, en ajoutant un seul chiffre aléatoirement.\n", " 3. En pratique, pour améliorer la convergence de l'algorithme, on va effacer les N2 individus ayant le plus petit score, et faire muter la moitié des N-N2 (= 90) individus restant." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Configuration" ] }, { "cell_type": "code", "execution_count": 34, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "val population : int = 100\n", "val mutes : int = 45\n", "val effaces : int = 10\n" ] }, "execution_count": 34, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "val conserves : int = 45\n" ] }, "execution_count": 34, "metadata": {}, "output_type": "execute_result" } ], "source": [ "let population = 100\n", "and mutes = 45\n", "and effaces = 10;;\n", "let conserves = population - mutes - effaces;;" ] }, { "cell_type": "code", "execution_count": 36, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "- : unit = ()\n" ] }, "execution_count": 36, "metadata": {}, "output_type": "execute_result" } ], "source": [ "Random.self_init();;" ] }, { "cell_type": "code", "execution_count": 62, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "- : int -> int = \n" ] }, "execution_count": 62, "metadata": {}, "output_type": "execute_result" } ], "source": [ "Random.int;;" ] }, { "cell_type": "code", "execution_count": 63, "metadata": {}, "outputs": [ { "ename": "error", "evalue": "compile_error", "output_type": "error", "traceback": [ "\u001b[32mFile \"[63]\", line 1, characters 0-13:\n\u001b[31mError: Unbound value Random.choice\n\u001b[36m 1: \u001b[30m\u001b[4mRandom.choice\u001b[0m\u001b[30m;;\u001b[0m\n" ] } ], "source": [ "let choix_sans_remise tab k =\n", " let n = Array.length tab in\n", " assert 0 <= k <= n;\n", " let reponse = Array.make k (-1) in\n", " for i = 0 to k-1 do\n", " \n", " done;\n", " reponse\n", ";;" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Génération d'individus, mutations" ] }, { "cell_type": "code", "execution_count": 41, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "val copie : int -> 'a array array -> 'a array array = \n" ] }, "execution_count": 41, "metadata": {}, "output_type": "execute_result" } ], "source": [ "let copie n t =\n", " Array.init n (fun i -> (Array.copy t.(i)))\n", ";;" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "let individu_initial n grille_initiale =\n", " Array.init \n", ";;" ] }, { "cell_type": "code", "execution_count": 61, "metadata": {}, "outputs": [ { "ename": "error", "evalue": "compile_error", "output_type": "error", "traceback": [ "\u001b[32mFile \"[61]\", line 2, characters 4-7:\n\u001b[31mError: Unbound constructor XXX\n\u001b[36m 1: \u001b[30mlet mutation n grille_initiale individu =\n\u001b[36m 2: \u001b[30m \u001b[4mXXX\u001b[0m\u001b[30m\n\u001b[36m 3: \u001b[30m;;\u001b[0m\n" ] } ], "source": [ "let mutation n grille_initiale individu =\n", " XXX\n", ";;" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Algorithme génétique" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "let algorithme_genetique nb1 nb2 nb3 ii m generation =\n", " let n = nb1 + nb2 + nb3 in\n", " let population = List.init (fun i -> ii ()) in\n", " \n", " " ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "let resolution_genetique_sudoku n grille_initiale =\n", " let ii = fun () -> individu_initial n grille_initiale in\n", " let m = fun individu -> mutation n grille_initiale individu in\n", " " ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Essai" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "----\n", "## Conclusion\n", "\n", "Voilà pour une proposition de bonus d'implémentation.\n", "\n", "> Bien-sûr, ce petit notebook ne se prétend pas être une solution optimale, ni exhaustive." ] } ], "metadata": { "kernelspec": { "display_name": "OCaml 4.04.2", "language": "OCaml", "name": "ocaml-jupyter" }, "language_info": { "codemirror_mode": "text/x-ocaml", "file_extension": ".ml", "mimetype": "text/x-ocaml", "name": "OCaml", "nbconverter_exporter": null, "pygments_lexer": "OCaml", "version": "4.04.2" }, "toc": { "colors": { "hover_highlight": "#DAA520", "running_highlight": "#FF0000", "selected_highlight": "#FFD700" }, "moveMenuLeft": true, "nav_menu": { "height": "289px", "width": "252px" }, "navigate_menu": true, "number_sections": true, "sideBar": true, "threshold": 4, "toc_cell": true, "toc_position": { "height": "704px", "left": "0px", "right": "1223px", "top": "124px", "width": "249px" }, "toc_section_display": "block", "toc_window_display": true }, "varInspector": { "cols": { "lenName": 16, "lenType": 16, "lenVar": 40 }, "kernels_config": { "python": { "delete_cmd_postfix": "", "delete_cmd_prefix": "del ", "library": "var_list.py", "varRefreshCmd": "print(var_dic_list())" }, "r": { "delete_cmd_postfix": ") ", "delete_cmd_prefix": "rm(", "library": "var_list.r", "varRefreshCmd": "cat(var_dic_list()) " } }, "types_to_exclude": [ "module", "function", "builtin_function_or_method", "instance", "_Feature" ], "window_display": false } }, "nbformat": 4, "nbformat_minor": 2 }