test_input_ocaml.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "toc": "true"
   },
   "source": [
    "# Table of Contents\n",
    " <p><div class=\"lev1 toc-item\"><a href=\"#Texte-d'oral-de-modélisation---Agrégation-Option-Informatique\" data-toc-modified-id=\"Texte-d'oral-de-modélisation---Agrégation-Option-Informatique-1\"><span class=\"toc-item-num\">1&nbsp;&nbsp;</span>Texte d'oral de modélisation - Agrégation Option Informatique</a></div><div class=\"lev2 toc-item\"><a href=\"#Préparation-à-l'agrégation---ENS-de-Rennes,-2016-17\" data-toc-modified-id=\"Préparation-à-l'agrégation---ENS-de-Rennes,-2016-17-11\"><span class=\"toc-item-num\">1.1&nbsp;&nbsp;</span>Préparation à l'agrégation - ENS de Rennes, 2016-17</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=\"#Question-de-programmation\" data-toc-modified-id=\"Question-de-programmation-13\"><span class=\"toc-item-num\">1.3&nbsp;&nbsp;</span>Question de programmation</a></div><div class=\"lev2 toc-item\"><a href=\"#Réponse-à-l'exercice-requis\" data-toc-modified-id=\"Réponse-à-l'exercice-requis-14\"><span class=\"toc-item-num\">1.4&nbsp;&nbsp;</span>Réponse à l'exercice requis</a></div><div class=\"lev3 toc-item\"><a href=\"#Une-autre-approche\" data-toc-modified-id=\"Une-autre-approche-141\"><span class=\"toc-item-num\">1.4.1&nbsp;&nbsp;</span>Une autre approche</a></div><div class=\"lev3 toc-item\"><a href=\"#Un-mauvais-exemple\" data-toc-modified-id=\"Un-mauvais-exemple-142\"><span class=\"toc-item-num\">1.4.2&nbsp;&nbsp;</span>Un mauvais exemple</a></div><div class=\"lev3 toc-item\"><a href=\"#Un-bon-exemple\" data-toc-modified-id=\"Un-bon-exemple-143\"><span class=\"toc-item-num\">1.4.3&nbsp;&nbsp;</span>Un bon exemple</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-144\"><span class=\"toc-item-num\">1.4.4&nbsp;&nbsp;</span>Un exemple de Su Doku de taille $9 \\times 9$ 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-145\"><span class=\"toc-item-num\">1.4.5&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-?-146\"><span class=\"toc-item-num\">1.4.6&nbsp;&nbsp;</span>Un exemple de comte... Dooku ?</a></div><div class=\"lev2 toc-item\"><a href=\"#Vérifier-les-autres-contraintes\" data-toc-modified-id=\"Vérifier-les-autres-contraintes-15\"><span class=\"toc-item-num\">1.5&nbsp;&nbsp;</span>Vérifier les autres contraintes</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": [
    "# Texte d'oral de modélisation - Agrégation Option Informatique\n",
    "## Préparation à l'agrégation - ENS de Rennes, 2016-17\n",
    "- *Date* : 3 avril 2017\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* de correction, partielle et probablement non-optimale, pour la partie implémentation d'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.02.3\n"
     ]
    },
    {
     "data": {
      "text/html": [
       "<pre style=\"color:slategray;max-height:100px;overflow:hidden\" \n",
       "onclick=\"\n",
       "if (this.style.maxHeight === 'none') \n",
       "    this.style.maxHeight = '100px';\n",
       "else\n",
       "    this.style.maxHeight = 'none'; \n",
       "\">- : int = 0\n",
       "</pre>"
      ]
     },
     "execution_count": 1,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Sys.command \"ocaml -version\";;"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "----\n",
    "## Question de programmation\n",
    "La question de programmation pour ce texte était donnée au tout début, en page 2 :\n",
    "\n",
    "> « Écrire une fonction prenant pour paramètres un entier, $p \\geq 1$, et un tableau carré de côté $p$ (donc de taille $p^2$) d'entiers, $T$, et renvoyant un booléen disant si ce tableau est un carré latin, c'est-à-dire contenant dans chaque ligne et chaque colonne une et une seule fois chaque entier de $1$ à $p$.\n",
    "\n",
    "Mathématiquement, si $N_p := \\{1,\\dots,p\\}$, cela donne un prédicat $\\mathrm{estCarreLatin}_p(T)$ sur un tableau $T$ :\n",
    "$$\n",
    "\\mathrm{estCarreLatin}_p(T) \\Longleftrightarrow\n",
    "\\forall i \\in N_p, \\left\\{ T_{i,j} : j \\in N_p \\right\\} = N_p\n",
    "\\;\\text{and}\\;\n",
    "\\forall j \\in N_p, \\left\\{ T_{i,j} : i \\in N_p \\right\\} = N_p\n",
    "$$\n",
    "\n",
    "> « En prenant $p = n^2$ on obtient une partie des contraintes d'admissibilité d'une grille complète de Su Doku, mais il reste encore à vérifier la contrainte sur les petits carrés. »\n",
    "\n",
    "Pour l'annecdote historique, cette idée de carré latin date vraiment de l'époque romaine antique. On a trouvé à Pompeï des carrés latins de taille $4$ ou $5$ !"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "----\n",
    "## Réponse à l'exercice requis\n",
    "C'est assez rapide :\n",
    "\n",
    "1. On écrit une fonction qui permet d'extraire une ligne ou une colonne d'un tableau $T$,\n",
    "2. On écrit ensuite une fonction qui permet de vérifier si un tableau de $p$ entiers contient exactement $N_p = \\{1, \\dots, p\\}$,\n",
    "3. Enfin, on vérifie toutes les contraintes."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> *Remarque:* On suppose que tous les tableaux considérés sont :\n",
    "> - **non vides**\n",
    "> - et **carrés**\n",
    "> On ne vérifie pas ces deux points."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<pre style=\"color:slategray;max-height:100px;overflow:hidden\" \n",
       "onclick=\"\n",
       "if (this.style.maxHeight === 'none') \n",
       "    this.style.maxHeight = '100px';\n",
       "else\n",
       "    this.style.maxHeight = 'none'; \n",
       "\">val ligne : int -&gt; 'a array array -&gt; int -&gt; 'a array = &lt;fun&gt;\n",
       "</pre>"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/html": [
       "<pre style=\"color:slategray;max-height:100px;overflow:hidden\" \n",
       "onclick=\"\n",
       "if (this.style.maxHeight === 'none') \n",
       "    this.style.maxHeight = '100px';\n",
       "else\n",
       "    this.style.maxHeight = 'none'; \n",
       "\">val colonne : int -&gt; 'a array array -&gt; int -&gt; 'a array = &lt;fun&gt;\n",
       "</pre>"
      ]
     },
     "execution_count": 2,
     "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": "markdown",
   "metadata": {},
   "source": [
    "On a besoin de savoir si un tableau de booléens sont tous vrais ou pas.\n",
    "On peut utiliser la fonction déjà existante, `Array.for_all`, ou bien un `Array.fold_left`, ou une implémentation manuelle."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<pre style=\"color:slategray;max-height:100px;overflow:hidden\" \n",
       "onclick=\"\n",
       "if (this.style.maxHeight === 'none') \n",
       "    this.style.maxHeight = '100px';\n",
       "else\n",
       "    this.style.maxHeight = 'none'; \n",
       "\">val tousVrai : bool array -&gt; bool = &lt;fun&gt;\n",
       "</pre>"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "let tousVrai tab =\n",
    "    let res = ref true in\n",
    "    for i = 0 to (Array.length tab) - 1 do\n",
    "        res := !res && tab.(i)\n",
    "    done;\n",
    "    !res\n",
    ";;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<pre style=\"color:slategray;max-height:100px;overflow:hidden\" \n",
       "onclick=\"\n",
       "if (this.style.maxHeight === 'none') \n",
       "    this.style.maxHeight = '100px';\n",
       "else\n",
       "    this.style.maxHeight = 'none'; \n",
       "\">val tousVrai : bool array -&gt; bool = &lt;fun&gt;\n",
       "</pre>"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "let tousVrai = Array.fold_left (&&) true;;\n",
    "(* Array.for_all marche aussi bien ! *)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Ca permet de facilement vérifier si un tableau `tab` de taille $p$ est exactement $N_p = \\{1,\\dots,p\\}$, en temps linéaire (c'est optimal) en $p$.\n",
    "\n",
    "1. On ajoute un test que tous les entiers soient bien entre $1$ et $p$,\n",
    "2. puis on fait ce test en $\\mathcal{O}(\\# tab)$, en créant est un tableau `estLa` de taille $p$, remplis de `false`. En bouclant sur $t$, on remplit $\\texttt{tab}[i]$ à `true` dans `estLa` (en fait, `tab(i) - 1` car les indices sont entre $0$ et $p-1$). A la fin, si le tableau `estLa` est rempli de `true`, alors on a vu tous les entiers de $N_p$ une et une seule fois."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<pre style=\"color:slategray;max-height:100px;overflow:hidden\" \n",
       "onclick=\"\n",
       "if (this.style.maxHeight === 'none') \n",
       "    this.style.maxHeight = '100px';\n",
       "else\n",
       "    this.style.maxHeight = 'none'; \n",
       "\">val estNp : int -&gt; int array -&gt; bool = &lt;fun&gt;\n",
       "</pre>"
      ]
     },
     "execution_count": 5,
     "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": "markdown",
   "metadata": {},
   "source": [
    "On va adopter une méthode naïve mais simple à écrire :\n",
    "\n",
    "- on construit deux tableaux de $p$ booléens,\n",
    "- on les remplit des contraintes pour les $p$ lignes et les $p$ colonnes,\n",
    "- et on les vérifie avec `tousVrai`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<pre style=\"color:slategray;max-height:100px;overflow:hidden\" \n",
       "onclick=\"\n",
       "if (this.style.maxHeight === 'none') \n",
       "    this.style.maxHeight = '100px';\n",
       "else\n",
       "    this.style.maxHeight = 'none'; \n",
       "\">val contraintes_lignes : int -&gt; int array array -&gt; bool = &lt;fun&gt;\n",
       "</pre>"
      ]
     },
     "execution_count": 32,
     "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": 31,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<pre style=\"color:slategray;max-height:100px;overflow:hidden\" \n",
       "onclick=\"\n",
       "if (this.style.maxHeight === 'none') \n",
       "    this.style.maxHeight = '100px';\n",
       "else\n",
       "    this.style.maxHeight = 'none'; \n",
       "\">val contraintes_colonnes : int -&gt; int array array -&gt; bool = &lt;fun&gt;\n",
       "</pre>"
      ]
     },
     "execution_count": 31,
     "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": 7,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<pre style=\"color:slategray;max-height:100px;overflow:hidden\" \n",
       "onclick=\"\n",
       "if (this.style.maxHeight === 'none') \n",
       "    this.style.maxHeight = '100px';\n",
       "else\n",
       "    this.style.maxHeight = 'none'; \n",
       "\">val carre_latin : int -&gt; int array array -&gt; bool = &lt;fun&gt;\n",
       "</pre>"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "let carre_latin p t =\n",
    "    (contraintes_lignes p t) && (contraintes_colonnes p t)\n",
    ";;"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Une autre approche\n",
    "Plutôt que d'écrire une fonction pour extraire une colonne, et deux fonction qui vérifies les contraintes sur les lignes et les colonnes, on remarque le fait suivant :\n",
    "\n",
    "> « Les colonnes de $t$ sont les lignes de $t^T$, la matrice transposée de $t$ ».\n",
    "\n",
    "Donc pas besoin de savoir extraire les colonnes, dès qu'on a écrit `contraintes_lignes`, on peut avoir les contraintes sur les colonnes facilement.\n",
    "\n",
    "Pour calculer la transposée, une approche simple utilise deux boucles `for` :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<pre style=\"color:slategray;max-height:100px;overflow:hidden\" \n",
       "onclick=\"\n",
       "if (this.style.maxHeight === 'none') \n",
       "    this.style.maxHeight = '100px';\n",
       "else\n",
       "    this.style.maxHeight = 'none'; \n",
       "\">val transpose_for : int -&gt; int array array -&gt; int array array = &lt;fun&gt;\n",
       "</pre>"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "let transpose_for p tab =\n",
    "    let tab2 = Array.make_matrix p p 0 in\n",
    "    for i = 0 to p - 1 do\n",
    "        for j = 0 to p - 1 do\n",
    "            tab2.(i).(j) <- tab.(j).(i);\n",
    "        done;\n",
    "    done;\n",
    "    tab2\n",
    ";;"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "On peut rapidement vérifier sur un exemple,\n",
    "$$ \\begin{bmatrix} 1 & 2 \\\\ 3 & 4 \\end{bmatrix}^{T} = \\begin{bmatrix} 1 & 3 \\\\ 2 & 4 \\end{bmatrix}. $$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<pre style=\"color:slategray;max-height:100px;overflow:hidden\" \n",
       "onclick=\"\n",
       "if (this.style.maxHeight === 'none') \n",
       "    this.style.maxHeight = '100px';\n",
       "else\n",
       "    this.style.maxHeight = 'none'; \n",
       "\">- : int array array = [|[|1; 3|]; [|2; 4|]|]\n",
       "</pre>"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "transpose_for 2 [| [|1; 2|]; [|3; 4|] |];;"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Notez qu'on peut faire mieux, sans boucles `for`, avec deux `Array.init` imbriqués :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<pre style=\"color:slategray;max-height:100px;overflow:hidden\" \n",
       "onclick=\"\n",
       "if (this.style.maxHeight === 'none') \n",
       "    this.style.maxHeight = '100px';\n",
       "else\n",
       "    this.style.maxHeight = 'none'; \n",
       "\">val transpose : int -&gt; 'a array array -&gt; 'a array array = &lt;fun&gt;\n",
       "</pre>"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "let transpose p tab =\n",
    "    Array.init p (fun i -> (Array.init p (fun j -> tab.(j).(i))));;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<pre style=\"color:slategray;max-height:100px;overflow:hidden\" \n",
       "onclick=\"\n",
       "if (this.style.maxHeight === 'none') \n",
       "    this.style.maxHeight = '100px';\n",
       "else\n",
       "    this.style.maxHeight = 'none'; \n",
       "\">- : int array array = [|[|1; 3|]; [|2; 4|]|]\n",
       "</pre>"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "transpose 2 [| [|1; 2|]; [|3; 4|] |];;"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Et donc :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<pre style=\"color:slategray;max-height:100px;overflow:hidden\" \n",
       "onclick=\"\n",
       "if (this.style.maxHeight === 'none') \n",
       "    this.style.maxHeight = '100px';\n",
       "else\n",
       "    this.style.maxHeight = 'none'; \n",
       "\">val carre_latin2 : int -&gt; int array array -&gt; bool = &lt;fun&gt;\n",
       "</pre>"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "let carre_latin2 p t =\n",
    "    (contraintes_lignes p t) && (contraintes_lignes p (transpose p t))\n",
    ";;"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Un mauvais exemple\n",
    "On va prendre le premier carré de taille $p = 3$ dans le problème de Su Doku donné en figure 1 de l'énoncé.\n",
    "\n",
    "<img width=\"40%;\" alt=\"images/sudoku.png\" src=\"images/sudoku.png\" >"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<pre style=\"color:slategray;max-height:100px;overflow:hidden\" \n",
       "onclick=\"\n",
       "if (this.style.maxHeight === 'none') \n",
       "    this.style.maxHeight = '100px';\n",
       "else\n",
       "    this.style.maxHeight = 'none'; \n",
       "\">val p1 : int = 3\n",
       "</pre>"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/html": [
       "<pre style=\"color:slategray;max-height:100px;overflow:hidden\" \n",
       "onclick=\"\n",
       "if (this.style.maxHeight === 'none') \n",
       "    this.style.maxHeight = '100px';\n",
       "else\n",
       "    this.style.maxHeight = 'none'; \n",
       "\">val t1 : int array array = [|[|1; 2; 7|]; [|3; 4; 9|]; [|5; 8; 6|]|]\n",
       "</pre>"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "let p1 = 3;;\n",
    "let t1 = [|\n",
    "    [| 1; 2; 7; |];\n",
    "    [| 3; 4; 9; |];\n",
    "    [| 5; 8; 6; |];\n",
    "|];;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<pre style=\"color:slategray;max-height:100px;overflow:hidden\" \n",
       "onclick=\"\n",
       "if (this.style.maxHeight === 'none') \n",
       "    this.style.maxHeight = '100px';\n",
       "else\n",
       "    this.style.maxHeight = 'none'; \n",
       "\">- : bool = false\n",
       "</pre>"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "carre_latin p1 t1;;"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$\\implies$ Ce sous-carré de taille $p = 3$ n'est évidemment pas un \"carré latin\" : il contient des chiffres hors de $\\{ 1, 2, 3 \\}$ !"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Un bon exemple"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "On peut prendre un vrai exemple de taille $p = 3$, qui sera un carré latin."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<pre style=\"color:slategray;max-height:100px;overflow:hidden\" \n",
       "onclick=\"\n",
       "if (this.style.maxHeight === 'none') \n",
       "    this.style.maxHeight = '100px';\n",
       "else\n",
       "    this.style.maxHeight = 'none'; \n",
       "\">val p2 : int = 3\n",
       "</pre>"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/html": [
       "<pre style=\"color:slategray;max-height:100px;overflow:hidden\" \n",
       "onclick=\"\n",
       "if (this.style.maxHeight === 'none') \n",
       "    this.style.maxHeight = '100px';\n",
       "else\n",
       "    this.style.maxHeight = 'none'; \n",
       "\">val t2 : int array array = [|[|1; 2; 3|]; [|2; 3; 1|]; [|3; 1; 2|]|]\n",
       "</pre>"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "let p2 = 3;;\n",
    "let t2 = [|\n",
    "    [| 1; 2; 3 |];\n",
    "    [| 2; 3; 1 |];\n",
    "    [| 3; 1; 2 |];\n",
    "|];;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<pre style=\"color:slategray;max-height:100px;overflow:hidden\" \n",
       "onclick=\"\n",
       "if (this.style.maxHeight === 'none') \n",
       "    this.style.maxHeight = '100px';\n",
       "else\n",
       "    this.style.maxHeight = 'none'; \n",
       "\">- : bool = true\n",
       "</pre>"
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "carre_latin p2 t2;;"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Les deux implémentations, la 1ère à base d'extraction de colonnes, la 2ème à base de transposée, donnent bien-sûr le même résultat !"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<pre style=\"color:slategray;max-height:100px;overflow:hidden\" \n",
       "onclick=\"\n",
       "if (this.style.maxHeight === 'none') \n",
       "    this.style.maxHeight = '100px';\n",
       "else\n",
       "    this.style.maxHeight = 'none'; \n",
       "\">- : bool = true\n",
       "</pre>"
      ]
     },
     "execution_count": 17,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "carre_latin2 p2 t2;;"
   ]
  },
  {
   "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": 18,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<pre style=\"color:slategray;max-height:100px;overflow:hidden\" \n",
       "onclick=\"\n",
       "if (this.style.maxHeight === 'none') \n",
       "    this.style.maxHeight = '100px';\n",
       "else\n",
       "    this.style.maxHeight = 'none'; \n",
       "\">val p3 : int = 9\n",
       "</pre>"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/html": [
       "<pre style=\"color:slategray;max-height:100px;overflow:hidden\" \n",
       "onclick=\"\n",
       "if (this.style.maxHeight === 'none') \n",
       "    this.style.maxHeight = '100px';\n",
       "else\n",
       "    this.style.maxHeight = 'none'; \n",
       "\">val t3 : 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",
       "</pre>"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "let p3 = 9 ;;\n",
    "let t3 = [|\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": 19,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<pre style=\"color:slategray;max-height:100px;overflow:hidden\" \n",
       "onclick=\"\n",
       "if (this.style.maxHeight === 'none') \n",
       "    this.style.maxHeight = '100px';\n",
       "else\n",
       "    this.style.maxHeight = 'none'; \n",
       "\">- : bool = true\n",
       "</pre>"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "carre_latin p3 t3;;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<pre style=\"color:slategray;max-height:100px;overflow:hidden\" \n",
       "onclick=\"\n",
       "if (this.style.maxHeight === 'none') \n",
       "    this.style.maxHeight = '100px';\n",
       "else\n",
       "    this.style.maxHeight = 'none'; \n",
       "\">- : bool = true\n",
       "</pre>"
      ]
     },
     "execution_count": 20,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "carre_latin2 p3 t3;;"
   ]
  },
  {
   "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": 21,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<pre style=\"color:slategray;max-height:100px;overflow:hidden\" \n",
       "onclick=\"\n",
       "if (this.style.maxHeight === 'none') \n",
       "    this.style.maxHeight = '100px';\n",
       "else\n",
       "    this.style.maxHeight = 'none'; \n",
       "\">val p4 : int = 9\n",
       "</pre>"
      ]
     },
     "execution_count": 21,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/html": [
       "<pre style=\"color:slategray;max-height:100px;overflow:hidden\" \n",
       "onclick=\"\n",
       "if (this.style.maxHeight === 'none') \n",
       "    this.style.maxHeight = '100px';\n",
       "else\n",
       "    this.style.maxHeight = 'none'; \n",
       "\">val t4 : 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",
       "</pre>"
      ]
     },
     "execution_count": 21,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "let p4 = 9 ;;\n",
    "let t4 = [|\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": 22,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<pre style=\"color:slategray;max-height:100px;overflow:hidden\" \n",
       "onclick=\"\n",
       "if (this.style.maxHeight === 'none') \n",
       "    this.style.maxHeight = '100px';\n",
       "else\n",
       "    this.style.maxHeight = 'none'; \n",
       "\">- : bool = false\n",
       "</pre>"
      ]
     },
     "execution_count": 22,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "carre_latin p4 t4;;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<pre style=\"color:slategray;max-height:100px;overflow:hidden\" \n",
       "onclick=\"\n",
       "if (this.style.maxHeight === 'none') \n",
       "    this.style.maxHeight = '100px';\n",
       "else\n",
       "    this.style.maxHeight = 'none'; \n",
       "\">- : bool = false\n",
       "</pre>"
      ]
     },
     "execution_count": 23,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "carre_latin2 p4 t4;;"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$\\implies$ Notre fonction `carre_latin` semble bien marcher."
   ]
  },
  {
   "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": [
    "## Vérifier les autres contraintes\n",
    "En bonus, on peut écrire une fonction qui vérifie les contraintes sur les petits carrés en plus des contraintes sur les lignes et les colonnes.\n",
    "\n",
    "On a déjà tout ce qu'il faut, il suffit d'écrire une fonction qui extraie un petit carré de taille $n \\times n$ ($n = \\sqrt{p}$)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<pre style=\"color:slategray;max-height:100px;overflow:hidden\" \n",
       "onclick=\"\n",
       "if (this.style.maxHeight === 'none') \n",
       "    this.style.maxHeight = '100px';\n",
       "else\n",
       "    this.style.maxHeight = 'none'; \n",
       "\">val racine_carree : int -&gt; int = &lt;fun&gt;\n",
       "</pre>"
      ]
     },
     "execution_count": 24,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "let racine_carree i = int_of_float (sqrt (float_of_int i));;"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "C'est moins facile à écrire, mais on peut extraire un \"petit carré\" de taille $n \\times n$, pour $t$ de taille $p \\times p$, si $p = n^2$.\n",
    "Ici, on extraie le $i$ème petit carré en ligne, et le $j$ème petit carré en colonne,\n",
    "- en jouant avec des modulos et des divisions entières sur $k$ qui sera de $0$ à $p-1$ (`k / n` et `k mod n` font parcourir $0 \\dots n-1$),\n",
    "- et en jouant avec des multiplications sur `i` et `j`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<pre style=\"color:slategray;max-height:100px;overflow:hidden\" \n",
       "onclick=\"\n",
       "if (this.style.maxHeight === 'none') \n",
       "    this.style.maxHeight = '100px';\n",
       "else\n",
       "    this.style.maxHeight = 'none'; \n",
       "\">val petit_carre : int -&gt; int -&gt; 'a array array -&gt; int -&gt; int -&gt; 'a array =\n",
       "  &lt;fun&gt;\n",
       "</pre>"
      ]
     },
     "execution_count": 25,
     "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": "markdown",
   "metadata": {},
   "source": [
    "> Bien-sûr, `p` et `n` pourraient ne pas être donnés à la fonction, mais autant se simplifier la vie !"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Par exemple, avec le tableau `t3` défini plus haut, et $p = 9 = n^2$ pour $n = 3$, on vérifie que les $9$ petits carrés arrivent dans l'ordre :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<pre style=\"color:slategray;max-height:100px;overflow:hidden\" \n",
       "onclick=\"\n",
       "if (this.style.maxHeight === 'none') \n",
       "    this.style.maxHeight = '100px';\n",
       "else\n",
       "    this.style.maxHeight = 'none'; \n",
       "\">val n3 : int = 3\n",
       "</pre>"
      ]
     },
     "execution_count": 26,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "let n3 = racine_carree p3;;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<pre style=\"color:slategray;max-height:100px;overflow:hidden\" \n",
       "onclick=\"\n",
       "if (this.style.maxHeight === 'none') \n",
       "    this.style.maxHeight = '100px';\n",
       "else\n",
       "    this.style.maxHeight = 'none'; \n",
       "\">- : int array = [|1; 2; 7; 3; 4; 9; 5; 8; 6|]\n",
       "</pre>"
      ]
     },
     "execution_count": 27,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/html": [
       "<pre style=\"color:slategray;max-height:100px;overflow:hidden\" \n",
       "onclick=\"\n",
       "if (this.style.maxHeight === 'none') \n",
       "    this.style.maxHeight = '100px';\n",
       "else\n",
       "    this.style.maxHeight = 'none'; \n",
       "\">- : int array = [|4; 6; 3; 8; 7; 5; 2; 9; 1|]\n",
       "</pre>"
      ]
     },
     "execution_count": 27,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/html": [
       "<pre style=\"color:slategray;max-height:100px;overflow:hidden\" \n",
       "onclick=\"\n",
       "if (this.style.maxHeight === 'none') \n",
       "    this.style.maxHeight = '100px';\n",
       "else\n",
       "    this.style.maxHeight = 'none'; \n",
       "\">- : int array = [|9; 8; 5; 2; 6; 1; 4; 3; 7|]\n",
       "</pre>"
      ]
     },
     "execution_count": 27,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/html": [
       "<pre style=\"color:slategray;max-height:100px;overflow:hidden\" \n",
       "onclick=\"\n",
       "if (this.style.maxHeight === 'none') \n",
       "    this.style.maxHeight = '100px';\n",
       "else\n",
       "    this.style.maxHeight = 'none'; \n",
       "\">- : int array = [|7; 6; 5; 8; 3; 4; 9; 1; 2|]\n",
       "</pre>"
      ]
     },
     "execution_count": 27,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/html": [
       "<pre style=\"color:slategray;max-height:100px;overflow:hidden\" \n",
       "onclick=\"\n",
       "if (this.style.maxHeight === 'none') \n",
       "    this.style.maxHeight = '100px';\n",
       "else\n",
       "    this.style.maxHeight = 'none'; \n",
       "\">- : int array = [|9; 4; 2; 7; 1; 6; 5; 3; 8|]\n",
       "</pre>"
      ]
     },
     "execution_count": 27,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/html": [
       "<pre style=\"color:slategray;max-height:100px;overflow:hidden\" \n",
       "onclick=\"\n",
       "if (this.style.maxHeight === 'none') \n",
       "    this.style.maxHeight = '100px';\n",
       "else\n",
       "    this.style.maxHeight = 'none'; \n",
       "\">- : int array = [|3; 1; 8; 5; 2; 9; 7; 4; 6|]\n",
       "</pre>"
      ]
     },
     "execution_count": 27,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/html": [
       "<pre style=\"color:slategray;max-height:100px;overflow:hidden\" \n",
       "onclick=\"\n",
       "if (this.style.maxHeight === 'none') \n",
       "    this.style.maxHeight = '100px';\n",
       "else\n",
       "    this.style.maxHeight = 'none'; \n",
       "\">- : int array = [|2; 7; 8; 4; 5; 3; 6; 9; 1|]\n",
       "</pre>"
      ]
     },
     "execution_count": 27,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/html": [
       "<pre style=\"color:slategray;max-height:100px;overflow:hidden\" \n",
       "onclick=\"\n",
       "if (this.style.maxHeight === 'none') \n",
       "    this.style.maxHeight = '100px';\n",
       "else\n",
       "    this.style.maxHeight = 'none'; \n",
       "\">- : int array = [|6; 5; 4; 1; 8; 9; 3; 2; 7|]\n",
       "</pre>"
      ]
     },
     "execution_count": 27,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/html": [
       "<pre style=\"color:slategray;max-height:100px;overflow:hidden\" \n",
       "onclick=\"\n",
       "if (this.style.maxHeight === 'none') \n",
       "    this.style.maxHeight = '100px';\n",
       "else\n",
       "    this.style.maxHeight = 'none'; \n",
       "\">- : int array = [|1; 9; 3; 6; 7; 2; 8; 5; 4|]\n",
       "</pre>"
      ]
     },
     "execution_count": 27,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "petit_carre p3 n3 t3 0 0;;\n",
    "petit_carre p3 n3 t3 0 1;;\n",
    "petit_carre p3 n3 t3 0 2;;\n",
    "petit_carre p3 n3 t3 1 0;;\n",
    "petit_carre p3 n3 t3 1 1;;\n",
    "petit_carre p3 n3 t3 1 2;;\n",
    "petit_carre p3 n3 t3 2 0;;\n",
    "petit_carre p3 n3 t3 2 1;;\n",
    "petit_carre p3 n3 t3 2 2;;"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Enfin, la contrainte supplémentaire s'écrit exactement comme les deux autres :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<pre style=\"color:slategray;max-height:100px;overflow:hidden\" \n",
       "onclick=\"\n",
       "if (this.style.maxHeight === 'none') \n",
       "    this.style.maxHeight = '100px';\n",
       "else\n",
       "    this.style.maxHeight = 'none'; \n",
       "\">val petits_carres_sont_latins : int -&gt; int array array -&gt; bool = &lt;fun&gt;\n",
       "</pre>"
      ]
     },
     "execution_count": 28,
     "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": "markdown",
   "metadata": {},
   "source": [
    "$\\implies$ Et on peut vérifier que le tableau `t3` satisfait bien cette contrainte :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<pre style=\"color:slategray;max-height:100px;overflow:hidden\" \n",
       "onclick=\"\n",
       "if (this.style.maxHeight === 'none') \n",
       "    this.style.maxHeight = '100px';\n",
       "else\n",
       "    this.style.maxHeight = 'none'; \n",
       "\">- : bool = true\n",
       "</pre>"
      ]
     },
     "execution_count": 29,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "petits_carres_sont_latins p3 t3;;"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$\\implies$ Et on peut vérifier que le tableau `t4` ne satisfait pas cette contrainte :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<pre style=\"color:slategray;max-height:100px;overflow:hidden\" \n",
       "onclick=\"\n",
       "if (this.style.maxHeight === 'none') \n",
       "    this.style.maxHeight = '100px';\n",
       "else\n",
       "    this.style.maxHeight = 'none'; \n",
       "\">- : bool = false\n",
       "</pre>"
      ]
     },
     "execution_count": 30,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "petits_carres_sont_latins p4 t4;;"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "----\n",
    "## Conclusion\n",
    "\n",
    "Voilà pour la question obligatoire de programmation :\n",
    "\n",
    "- on a décomposé le problème en sous-fonctions,\n",
    "- on a essayé d'être fainéant, en réutilisant les sous-fonctions,\n",
    "- on a fait des exemples et *on les garde* dans ce qu'on présente au jury,\n",
    "- on a testé la fonction exigée sur de petits exemples et sur un exemple de taille réelle (venant du texte)\n",
    "\n",
    "Et on a essayé de faire *un peu plus*, en implémentant la vérification d'une contrainte de plus.\n",
    "\n",
    "> Bien-sûr, ce petit notebook ne se prétend pas être une solution optimale, ni exhaustive."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "OCaml",
   "language": "ocaml",
   "name": "iocaml-kernel"
  },
  "language_info": {
   "name": "ocaml",
   "version": "4.1.0"
  },
  "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
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}