{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Sudoku"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Marc Lorenzi - 10 mars 2018"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import random\n",
    "\n",
    "count = 0"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 1. Représentation des données"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "On représente un problème de Sudoku par une matrice 9x9. Les cases inconnues sont remplies par des zéros. Ci-dessous deux problèmes faciles."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "pb01 = [\n",
    " [0,3,0,0,6,0,1,0,5],\n",
    " [0,2,0,4,0,0,3,9,0],\n",
    " [0,0,7,0,3,0,4,0,0],\n",
    " [0,6,1,0,5,0,9,0,0],\n",
    " [8,0,2,7,0,6,5,0,1],\n",
    " [0,0,5,0,4,0,7,6,0],\n",
    " [0,0,4,0,8,0,2,0,0],\n",
    " [0,7,8,0,0,1,0,4,0],\n",
    " [2,0,3,0,7,0,0,5,0]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "pb02 = [\n",
    "[0,6,9,2,0,7,4,0,0],\n",
    "[0,0,1,9,0,0,0,0,0],\n",
    "[2,0,0,0,0,0,0,6,0],\n",
    "[0,1,0,6,0,0,9,0,0],\n",
    "[7,0,0,1,0,2,0,0,4],\n",
    "[0,0,5,0,0,3,0,7,0],\n",
    "[0,2,0,0,0,0,0,0,6],\n",
    "[0,0,0,0,0,4,3,0,0],\n",
    "[0,0,4,5,0,1,7,9,0]\n",
    "]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Les problèmes `harder` et `ai_escargot` ci-dessous sont réputés très difficiles. Voir [ce site](http://aisudoku.com/index_en.html). Nous allons voir que leur réputation est surfaite."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "harder = [\n",
    "[8,0,0,0,0,0,0,0,0],\n",
    "[0,0,3,6,0,0,0,0,0],\n",
    "[0,7,0,0,9,0,2,0,0],\n",
    "[0,5,0,0,0,7,0,0,0],\n",
    "[0,0,0,0,4,5,7,0,0],\n",
    "[0,0,0,1,0,0,0,3,0],\n",
    "[0,0,1,0,0,0,0,6,8],\n",
    "[0,0,8,5,0,0,0,1,0],\n",
    "[0,9,0,0,0,0,4,0,0]\n",
    "]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "ai_escargot = [\n",
    "[1,0,0,0,0,7,0,9,0],\n",
    "[0,3,0,0,2,0,0,0,8],\n",
    "[0,0,9,6,0,0,5,0,0],\n",
    "[0,0,5,3,0,0,9,0,0],\n",
    "[0,1,0,0,8,0,0,0,2],\n",
    "[6,0,0,0,0,4,0,0,0],\n",
    "[3,0,0,0,0,0,0,1,0],\n",
    "[0,4,0,0,0,0,0,0,7],\n",
    "[0,0,7,0,0,0,3,0,0]\n",
    "]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Rajoutons à cela le problème vide, qui n'est pas un vrai problème pouisqu'il ne possède pas vraiment une unique solution :-)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "vide = [\n",
    "[0,0,0,0,0,0,0,0,0],\n",
    "[0,0,0,0,0,0,0,0,0],\n",
    "[0,0,0,0,0,0,0,0,0],\n",
    "[0,0,0,0,0,0,0,0,0],\n",
    "[0,0,0,0,0,0,0,0,0],\n",
    "[0,0,0,0,0,0,0,0,0],\n",
    "[0,0,0,0,0,0,0,0,0],\n",
    "[0,0,0,0,0,0,0,0,0],\n",
    "[0,0,0,0,0,0,0,0,0]\n",
    "]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 2. Conversions entre problèmes et grilles"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Lors de la résolution du problème on a besoin, pour chaque case, de mémoriser les possibilités pour remplir cette case. Nous appellerons dans la suite \"grille\" une matrice 9x9 contenant à la ligne $i$, colonne $j$ la liste des possibilités pour remplir la case $(i,j)$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Voici une fonction qui permet de transformer un problème en grille. Tout d'abord, on remplit les cases de la grille par la liste des entiers de 1 à 9. Puis, pour chaque case connue du problème, on impose sa valeur dans la grille.\n",
    "\n",
    "La fonction `imposer`, qui reste à écrire, force la case $(i, j)$ de la grille à une valeur $c$. Puis elle élimine de la ligne $i$, de la colonne $j$, et du carré 3x3 contenant la case $(i,j)$, la possibilité $c$. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def probleme_vers_grille(probleme):\n",
    "    g = 9 * [None]\n",
    "    for k in range(9): g[k] = 9 * [None]\n",
    "    for i in range(9):\n",
    "        for j in range(9):\n",
    "            g[i][j] = list(range(1, 10))\n",
    "    for i in range(9):\n",
    "        for j in range(9):\n",
    "            c = probleme[i][j]\n",
    "            if c != 0:\n",
    "                imposer(g, i, j, c)\n",
    "    return g"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "La fonction réciproque prend en paramètre une grille censée être résolue : toutes les cases de la grille contiennent des listes à 1 élément. Elle renvoie le problème correspondant. Elle lève une exception en cas de case de la grille qui n'est pas un singleton."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def grille_vers_probleme(g):\n",
    "    pb = [[0 for i in range(9)] for j in range(9)]\n",
    "    for i in range(9):\n",
    "        for j in range(9):\n",
    "            if len(g[i][j]) != 1: raise Exception\n",
    "            else: pb[i][j] = g[i][j][0]\n",
    "    return pb"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 3. Affichage"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "La fonction `afficher_probleme` ... affiche joliment notre problème de Sudoku."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def afficher_probleme(pb):\n",
    "    s = '' \n",
    "    for i in range(9):\n",
    "        for j in range(9): s += ('%2d' % pb[i][j])\n",
    "        if i != 8: s += '\\n'\n",
    "    print(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "afficher_probleme(ai_escargot)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 4. Résolution"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 4.1 La fonction de résolution"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Nous y voilà. La fonction `resoudre` prend une grille $g$ en paramètre. \n",
    "\n",
    "- On commence par faire un peu de ménage en regardant les cases de la grille qui sont des singletons (ménage sur ligne, colonne, carré).\n",
    "- Puis on choisit une case de la grille qui contient le moins possible d'éléments (le cas des singletons étant retenu en dernière extrémité).\n",
    "- Si la case retenue est un singleton c'est que le problème est résolu.\n",
    "- Si la case retenue est vide c'est que le problème est impossible.\n",
    "- Sinon, on fait une copie toute neuve, $g_1$, de la grille $g$. On sélectionne une valeur $c$ au hasard parmi toutes les possibilités pour $g[i][j]$ et on l'impose dans $g_1$. On appelle ensuite récursivement `resoudre` sur $g_1$. Si cela réussit, tant mieux, on a fini. Sinon, on retire la possibilité $c$ pour la case $(i,j)$ de $g$ et on appelle résoudre sur le $g$ ainsi légèrement modifié."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def resoudre(g):\n",
    "    global count\n",
    "    count = count + 1\n",
    "    for (i,j) in random_walk():\n",
    "        if len(g[i][j]) == 1:\n",
    "            c = g[i][j][0]\n",
    "            imposer(g, i, j, c)\n",
    "    i, j = choisir_case(g)\n",
    "    if (i, j) == (-1, -1): return (g, True) # Grille résolue\n",
    "    elif len(g[i][j]) == 0: return (g, False) # Grille impossible\n",
    "    else:\n",
    "        g1 = copie(g)\n",
    "        c = choisir_hasard(g1[i][j])\n",
    "        imposer(g1, i, j, c)\n",
    "        (g2, b) = resoudre(g1)\n",
    "        if not b: # échec ! \n",
    "            g[i][j].remove(c) # car c ne convient pas\n",
    "            return resoudre(g)\n",
    "        else:\n",
    "            return (g2, True)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 4.2 Copie d'une grille"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Sans commentaire, voici la fonction de copie."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def copie(g):\n",
    "    g1 = [[None for i in range(9)] for j in range(9)]\n",
    "    for i in range(9):\n",
    "        for j in range(9):\n",
    "            g1[i][j] = g[i][j][:]\n",
    "    return g1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 4.3 Choix d'une case de la grille"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "La fonction `choisir_case` choisit une case de la grille ayant un nombre minimal d'éléments, mais si possible pas un seul. Elle renvoie les coordonnées de la case, sauf ti toutes les cases ont un seul élément (problème résolu !). Dans ce cas, la fonction renvoie le couple $(-1,-1)$. La grille est parcourue au hasard pour donner un peu plus de chance à la chance."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def random_list(n):\n",
    "    s = list(range(n))\n",
    "    for i in range(n):\n",
    "        j = random.randint(0, i)\n",
    "        s[i], s[j] = s[j], s[i]\n",
    "    return s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "print(random_list(81))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Voici une fonction qui renvoie un parcours au hasard des cases d'un tableau 9x9."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def random_walk():\n",
    "    s = random_list(81)\n",
    "    return [(x // 9, x % 9) for x in s]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "print(random_walk())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def note(g, i, j):\n",
    "    l = len(g[i][j])\n",
    "    if l == 1: return 1000000\n",
    "    else : return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def choisir_case(g):\n",
    "    u, v = 0, 0\n",
    "    for (i, j) in random_walk():\n",
    "        nij = note(g, i, j)\n",
    "        nuv = note(g, u, v)\n",
    "        if nij <= nuv: u, v = i, j\n",
    "    if note(g, u, v) == 1000000: u, v = -1, -1\n",
    "    return (u, v)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Fonction ci-dessous : RAS :-)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def choisir_hasard(s):\n",
    "    k = random.randint(0, len(s) - 1)\n",
    "    return s[k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "choisir_hasard([1,7,2,8,5,3])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 4.4 Imposer une valeur à une case"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Dernière ligne droite : imposer une valeur à une case. Facile ..."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def imposer(g, i, j, c):\n",
    "    g[i][j] = [c]\n",
    "    ajuster_ligne(g, i, j, c)\n",
    "    ajuster_colonne(g, i, j, c)\n",
    "    ajuster_carre(g, i, j, c)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "... euh oui, facile lorsqu'on aura écrit les fonctions d'ajustement !"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def ajuster_ligne(g, i, j, c):\n",
    "    for k in range(9):\n",
    "        if k != j and c in g[i][k]:\n",
    "            g[i][k].remove(c)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def ajuster_colonne(g, i, j, c):\n",
    "    for k in range(9):\n",
    "        if k != i and c in g[k][j]:\n",
    "            g[k][j].remove(c)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def ajuster_carre(g, i, j, c):\n",
    "    for (k, l) in carre(i, j):\n",
    "        if (k != i or l != j) and c in g[k][l]:\n",
    "            g[k][l].remove(c)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def carre(i, j):\n",
    "    coin_x = 3 * (i // 3)\n",
    "    coin_y = 3 * (j // 3)\n",
    "    return [(coin_x + k, coin_y + l) for k in range(3) for l in range(3)] "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 5. Tests"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Nous sommes maintenant en mesure de tester notre fonction de résolution. Tant qu'à faire, on encapsule toutes les étapes dans une unique fonction que nous appellerons `solution`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def solution(probleme):\n",
    "    g = probleme_vers_grille(probleme)\n",
    "    count = 0\n",
    "    g1, b = resoudre(g)\n",
    "    if not b:\n",
    "        print(\"Pas de solution\")\n",
    "    else:\n",
    "        afficher_probleme(grille_vers_probleme(g1))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "On tente un problème facile ?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "solution(pb01)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Réponse donnée en 0 seconde. On essaie plus difficile ?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "solution(pb02)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Le problème ci-dessous est réputé difficile."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "solution(harder)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "La solution est donnée en moins de 10 secondes, au pire. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Selon [ce site](http://aisudoku.com/index_en.html), voici un problème vraiment très très difficile. Bof."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "solution(ai_escargot)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficile pour un humain ... mais pas pour un python :-)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 6. Derniers doutes levés"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Après quelques grilles vérifiées à l'oeil, je me décide. La fonction `verifier` prend un problème en paramètre et sa solution (?) et teste si le problème est vraiment résolu."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def verifier(pb, sol):\n",
    "    b = True\n",
    "    comparer(pb, sol)\n",
    "    for i in range(9): b = b and verifier_ligne(sol, i)\n",
    "    for j in range(9): b = b and verifier_colonne(sol, j)\n",
    "    for x in range(3):\n",
    "        for y in range(3):\n",
    "            b = b and verifier_carre(sol, x, y)\n",
    "    return b"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def comparer(pb, sol):\n",
    "    b = True\n",
    "    for i in range(9):\n",
    "        for j in range(9):\n",
    "            if pb[i][j] != 0:\n",
    "                b = b and pb[i][j] == sol[i][j]\n",
    "    return b            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def verifier_ligne(pb, i):\n",
    "    s = 0\n",
    "    for j in range(9):\n",
    "        s = s + pb[i][j]\n",
    "    return s == 45"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def verifier_colonne(pb, j):\n",
    "    s = 0\n",
    "    for i in range(9):\n",
    "        s = s + pb[i][j]\n",
    "    return s == 45"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def verifier_carre(pb, x, y):\n",
    "    s = 0\n",
    "    for i in range(3):\n",
    "        for j in range(3):\n",
    "            s = s + pb[3 * x + i][3 * y + j]\n",
    "    return s == 45"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def solution_verifiee(probleme):\n",
    "    g = probleme_vers_grille(probleme)\n",
    "    g1, b = resoudre(g)\n",
    "    if not b:\n",
    "        print(\"Pas de solution\")\n",
    "    else:\n",
    "        sol = grille_vers_probleme(g1)\n",
    "        afficher_probleme(sol)\n",
    "        print('')\n",
    "        if verifier(probleme, sol): print('Grille résolue !!!')\n",
    "        else: print('Aie aie aie, l''impossible s''est produit.')\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%%time\n",
    "solution_verifiee(ai_escargot)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%%time\n",
    "count = 0\n",
    "solution_verifiee(harder)\n",
    "print(\"Nombre d'appels à resoudre : \", count)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 7. Des milliers de grilles ..."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Le fichier joint `sudoku17.txt` contient 49151 problèmes de Sudoku avec 17 cases connues au départ. 17 est à ce jour le nombre minimum connu de cases nécessaires pour qu'un problème de Sudoku ait une solution unique. Il se peut qu'on trouve mieux un jour ...\n",
    "\n",
    "Certains de ces problèmes donnent du fil à retordre à l'algorithme, le numéro 39949 par exemple (plus d'une minute de recherche pour obtenir la solution)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "La fonction `get_sudoku` prend un entier $k$ en paramètre et renvoie le $k$ième problème du fichier."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def get_sudoku(k):\n",
    "    lines = open('sudoku17.txt', 'r').readlines() \n",
    "    s = lines[k]\n",
    "    pb = [[0 for i in range(9)] for j in range(9)]\n",
    "    for i in range(9):\n",
    "        for j in range(9):\n",
    "            pb[i][j] = int(s[9*i+j])\n",
    "    return pb"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%%time\n",
    "pb = get_sudoku(2018)\n",
    "afficher_probleme(pb)\n",
    "print()\n",
    "solution_verifiee(pb)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "La fonction `random_sudoku` renvoie un problème pris au hasard dans le fichier, ainsi que le numéro de ce problème."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def random_sudoku():\n",
    "    k = random.randint(0, 49150)\n",
    "    return (get_sudoku(k), k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%%time\n",
    "pb, k = random_sudoku()\n",
    "print('Problème numéro ', k)\n",
    "afficher_probleme(pb)\n",
    "print()\n",
    "solution_verifiee(pb)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}