agreg/Sudoku_resolus_par_algorithme_genetique.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "toc": "true"
   },
   "source": [
    "# Table of Contents\n",
    " <p><div class=\"lev1 toc-item\"><a href=\"#Bonus-d'implémentation---Agrégation-Option-Informatique\" data-toc-modified-id=\"Bonus-d'implémentation---Agrégation-Option-Informatique-1\"><span class=\"toc-item-num\">1&nbsp;&nbsp;</span>Bonus d'implémentation - Agrégation Option Informatique</a></div><div class=\"lev2 toc-item\"><a href=\"#Préparation-à-l'agrégation---ENS-de-Rennes,-2017-18\" data-toc-modified-id=\"Préparation-à-l'agrégation---ENS-de-Rennes,-2017-18-11\"><span class=\"toc-item-num\">1.1&nbsp;&nbsp;</span>Préparation à l'agrégation - ENS de Rennes, 2017-18</a></div><div class=\"lev2 toc-item\"><a href=\"#À-propos-de-ce-document\" data-toc-modified-id=\"À-propos-de-ce-document-12\"><span class=\"toc-item-num\">1.2&nbsp;&nbsp;</span>À propos de ce document</a></div><div class=\"lev2 toc-item\"><a href=\"#Vérifier-qu'un-Su-Doku-est-correct\" data-toc-modified-id=\"Vérifier-qu'un-Su-Doku-est-correct-13\"><span class=\"toc-item-num\">1.3&nbsp;&nbsp;</span>Vérifier qu'un Su Doku est correct</a></div><div class=\"lev3 toc-item\"><a href=\"#Fonctions-utilitaires\" data-toc-modified-id=\"Fonctions-utilitaires-131\"><span class=\"toc-item-num\">1.3.1&nbsp;&nbsp;</span>Fonctions utilitaires</a></div><div class=\"lev3 toc-item\"><a href=\"#Contraintes-sur-les-lignes-et-les-colonnes\" data-toc-modified-id=\"Contraintes-sur-les-lignes-et-les-colonnes-132\"><span class=\"toc-item-num\">1.3.2&nbsp;&nbsp;</span>Contraintes sur les lignes et les colonnes</a></div><div class=\"lev3 toc-item\"><a href=\"#Contraintes-sur-les-carrés\" data-toc-modified-id=\"Contraintes-sur-les-carrés-133\"><span class=\"toc-item-num\">1.3.3&nbsp;&nbsp;</span>Contraintes sur les carrés</a></div><div class=\"lev3 toc-item\"><a href=\"#Contraintes-globales\" data-toc-modified-id=\"Contraintes-globales-134\"><span class=\"toc-item-num\">1.3.4&nbsp;&nbsp;</span>Contraintes globales</a></div><div class=\"lev2 toc-item\"><a href=\"#Exemples-de-&quot;score&quot;\" data-toc-modified-id=\"Exemples-de-&quot;score&quot;-14\"><span class=\"toc-item-num\">1.4&nbsp;&nbsp;</span>Exemples de \"score\"</a></div><div class=\"lev3 toc-item\"><a href=\"#Un-exemple-de-Su-Doku-de-taille-$9-\\times-9$-au-compte-juste\" data-toc-modified-id=\"Un-exemple-de-Su-Doku-de-taille-$9-\\times-9$-au-compte-juste-141\"><span class=\"toc-item-num\">1.4.1&nbsp;&nbsp;</span>Un exemple de Su Doku de taille <span class=\"MathJax_Preview\" style=\"color: inherit;\"></span><span class=\"MathJax\" id=\"MathJax-Element-450-Frame\" tabindex=\"0\" style=\"position: relative;\" data-mathml=\"<math xmlns=&quot;http://www.w3.org/1998/Math/MathML&quot;><mn>9</mn><mo>&amp;#x00D7;</mo><mn>9</mn></math>\" role=\"presentation\"><nobr aria-hidden=\"true\"><span class=\"math\" id=\"MathJax-Span-3209\" role=\"math\" style=\"width: 2.6em; display: inline-block;\"><span style=\"display: inline-block; position: relative; width: 2.158em; height: 0px; font-size: 120%;\"><span style=\"position: absolute; clip: rect(1.742em, 1002.12em, 2.666em, -1000em); top: -2.53em; left: 0em;\"><span class=\"mrow\" id=\"MathJax-Span-3210\"><span class=\"mn\" id=\"MathJax-Span-3211\" style=\"font-family: STIXMathJax_Main;\">9</span><span class=\"mo\" id=\"MathJax-Span-3212\" style=\"font-family: STIXMathJax_Main; padding-left: 0.25em;\">×</span><span class=\"mn\" id=\"MathJax-Span-3213\" style=\"font-family: STIXMathJax_Main; padding-left: 0.25em;\">9</span></span><span style=\"display: inline-block; width: 0px; height: 2.53em;\"></span></span></span><span style=\"display: inline-block; overflow: hidden; vertical-align: -0.075em; border-left: 0px solid; width: 0px; height: 0.93em;\"></span></span></nobr><span class=\"MJX_Assistive_MathML\" role=\"presentation\"><math xmlns=\"http://www.w3.org/1998/Math/MathML\"><mn>9</mn><mo>×</mo><mn>9</mn></math></span></span><script type=\"math/tex\" id=\"MathJax-Element-450\">9 \\times 9</script> au compte juste</a></div><div class=\"lev3 toc-item\"><a href=\"#Un-exemple-de-Su-Doku-au-comte-faux\" data-toc-modified-id=\"Un-exemple-de-Su-Doku-au-comte-faux-142\"><span class=\"toc-item-num\">1.4.2&nbsp;&nbsp;</span>Un exemple de Su Doku au <em>comte</em> faux</a></div><div class=\"lev3 toc-item\"><a href=\"#Un-exemple-de-comte...-Dooku-?\" data-toc-modified-id=\"Un-exemple-de-comte...-Dooku-?-143\"><span class=\"toc-item-num\">1.4.3&nbsp;&nbsp;</span>Un exemple de comte... Dooku ?</a></div><div class=\"lev2 toc-item\"><a href=\"#Algorithme-génétique\" data-toc-modified-id=\"Algorithme-génétique-15\"><span class=\"toc-item-num\">1.5&nbsp;&nbsp;</span>Algorithme génétique</a></div><div class=\"lev3 toc-item\"><a href=\"#Configuration\" data-toc-modified-id=\"Configuration-151\"><span class=\"toc-item-num\">1.5.1&nbsp;&nbsp;</span>Configuration</a></div><div class=\"lev3 toc-item\"><a href=\"#Génération-d'individus,-mutations\" data-toc-modified-id=\"Génération-d'individus,-mutations-152\"><span class=\"toc-item-num\">1.5.2&nbsp;&nbsp;</span>Génération d'individus, mutations</a></div><div class=\"lev3 toc-item\"><a href=\"#Algorithme-génétique\" data-toc-modified-id=\"Algorithme-génétique-153\"><span class=\"toc-item-num\">1.5.3&nbsp;&nbsp;</span>Algorithme génétique</a></div><div class=\"lev3 toc-item\"><a href=\"#Essai\" data-toc-modified-id=\"Essai-154\"><span class=\"toc-item-num\">1.5.4&nbsp;&nbsp;</span>Essai</a></div><div class=\"lev2 toc-item\"><a href=\"#Conclusion\" data-toc-modified-id=\"Conclusion-16\"><span class=\"toc-item-num\">1.6&nbsp;&nbsp;</span>Conclusion</a></div>"
   ]
  },
  {
   "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 = <fun>\n"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val colonne : int -> 'a array array -> int -> 'a array = <fun>\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 = <fun>\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 = <fun>\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 = <fun>\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 = <fun>\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 = <fun>\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 = <fun>\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 = <fun>\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 = <fun>\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 = <fun>\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 = <fun>\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 = <fun>\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",
       "  <fun>\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 = <fun>\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 = <fun>\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 = <fun>\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 = <fun>\n"
      ]
     },
     "execution_count": 50,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val score : int -> int array array -> int = <fun>\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",
    "<img width=\"40%;\" alt=\"images/sudoku.png\" src=\"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 = <fun>\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 = <fun>\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
}