2025 – EPITA – Sciences numériques MP-PC-PSI-PT-TSI
Le sujet se compose d’un problème et d’un questionnaire à choix multiples. Le questionnaire à choix multiples devra être inséré dans votre copie.
Les fonctions à produire dans ce sujet devront être rédigées en langage Python et ne pas avoir recours à l’usage de bibliothèques. Il est possible d’écrire des fonctions auxiliaires non explicitement demandées à condition de les documenter et de les définir avant d’en faire usage.
Problème – Le KenKen
Le KenKen est un jeu constitué d’une grille carrée de n cases de coté (en général {n\geq3}) ; n sera alors appelé taille du jeu. La grille comporte des ensembles de cases, délimités par un contour plus épais, que l’on appellera des zones.
Dans chacune de ces zones est précisé une contrainte : un nombre, généralement suivi d’un opérateur. Ces contraintes et leur format seront détaillés plus loin.
Voici l’exemple d’une grille de taille 4 :
Le but du jeu est de remplir chaque case de la grille avec un entier, de sorte que chaque ligne et chaque colonne comporte chaque entier de 1 à n et de façon à ce que les entiers présents dans les cases d’une même zone respectent la contrainte de la zone définie comme suit :
— si la zone contient une seule case : la contrainte est un simple nombre indiquant la valeur que doit contenir cette case ;
— si la zone comporte au moins deux cases : la contrainte est un chiffre r suivi d’un opérateur parmi +, ×, − et / dont la signification est donnée par la tableau ci-après : + : la somme des entiers dans les cases de la zone doit donner {r}. × : le produit des entiers dans les cases de la zone doit donner {r}. − : la différence des deux entiers des cases de la zone doit donner {r} (dans un sens ou dans l’autre).
Attention, cette contrainte ne s’applique qu’à des zones de 2 cases. / le quotient des deux entiers des cases de la zone doit donner r (dans un sens ou dans l’autre). Attention, cette contrainte ne s’applique qu’à des zones de 2 cases.
Une grille de KenKen bien formée ne comporte qu’une seule solution satisfaisant ces contraintes. Voici la solution de l’exemple précédent :
On choisit de représenter chaque zone par un dictionnaire contenant les champs val, op et cases ; val et op contiennent respectivement le nombre et l’opérateur associés à la zone tandis que cases est la liste des cases de la zone, représentées par le couple de leurs coordonnées.
On choisit de repérer les cases en ligne puis colonne en commençant par la case supérieure gauche. Ainsi, pour une grille de taille n, la case supérieure gauche aura pour coordonnées (0, 0), la case inférieure gauche (n − 1, 0) et la case inférieure droite : (n − 1, n − 1).
Pour les zones ne comportant qu’une seule case, le champ op sera une chaîne de caractères vide.
Dans l’exemple précédent, la zone comportant la case de coordonnées (0, 0) pourra être représentée par le dictionnaire {« val »:12, « op »: »× », « cases »: [(0,0),(1,0),(1,1)]} et la zone réduite à la case de coordonnées (0, 3) pourra être représentée par : {« val »:1, « op »: » », « cases »: [(0,3)]}.
Un jeu de KenKen sera alors intégralement décrit par sa taille n et par la liste des zones qui le composent.
De plus, on représente l’état du remplissage d’une grille par une liste de listes d’entiers de sorte que la sous-liste d’indice k corresponde à la valeur des cases situées sur la ligne k (parcourues de gauche à droite). Les cases non remplies de la grille se verront attribuer la valeur 0.
Dès lors, la grille de l’exemple dont on aurait effectué un remplissage partiel (en ne remplissant que la première ligne) est représentée par la liste [[2,3,4,1],[0,0,0,0],[0,0,0,0],[0,0,0,0]].
Autour des contraintes
On considère à présent disposer des fonctions suivantes :
— test_produit qui, étant donné une liste d’entiers et un entier v, retourne True si le produit des éléments de la liste vaut v et False sinon ;
— test_difference qui, étant donné une liste de deux entiers et un entier v, retourne True si la valeur v peut-être obtenue en calculant la différence des deux entiers (dans un sens ou dans l’autre) et False sinon.
On considèrera que cette fonction ne sera appelée que pour des zones portant sur des cases remplies de la grille.
Dans le cas contraire la fonction renverra True.
On souhaite à présent pouvoir regrouper les contraintes de zones selon le plus grand numéro de ligne des cases qu’elles comportent.
On interdit pour cette question l’usage des fonctions min et max de Python.
La sous-liste d’indice k sera la liste des zones du jeu telles que le numéro de ligne maximal des cases qui la composent est égal à k.
Afin de vérifier si les zones sont bien formées, on souhaite construire une fonction permettant de déterminer si une liste de cases est connexe ; c’est-à-dire s’il est possible de se déplacer entre n’importe quelles cases de la liste en passant uniquement par des cases de cette liste et au moyen de déplacements horizontaux et/ou verticaux.
Cette fonction pourra opérer comme si elle parcourait le graphe formé par les cases de la liste dont seraient adjacentes les cases se touchant horizontalement ou verticalement.
Itérateur de permutations
On rappelle qu’une permutation de {\llbracket1,n\rrbracket} est une bijection de {\llbracket1,n\rrbracket} dans {\llbracket1,n\rrbracket}. On choisit de représenter une permutation {\sigma} de {\llbracket1,n\rrbracket} par la liste d’entiers {[\sigma(1),\ldots,\sigma(n)]}.
Ainsi les listes comportant une et une seule fois chaque entier de 1 à n représentent toutes les permutations de {\llbracket1,n\rrbracket}. On considère l’ordre des permutations de {\llbracket1,n\rrbracket} comme étant l’ordre lexicographique des listes qui les représentent : {[a_1]\lt[b_1]\iff a_1\lt b_1.} {\begin{array}{l}\forall p\geq2,\ [a_1,\ldots,a_p]\lt[b_1,\ldots,b_p]\\[8pt]\iff a_1\lt b_1\text{ ou }\left\{\begin{array}{l}a_1=b_1,\\[8pt][a_2,\ldots,a_p]\lt[b_2,\ldots,b_p].\end{array}\right.\end{array}}Ainsi {[2,4,1,3]\lt[2,4,3,1]\lt[3,1,2,4]\lt[3,1,4,2]}.
Cette fonction ne fera rien dans le cas où {i\geq j} et on supposera que cette fonction n’est appelée que lorsque i et j sont dans {\llbracket1,n\rrbracket}.
On suppose que cette fonction ne sera appelée que lorsqu’un tel indice existe.
Lorsque la permutation suivante existe, la fonction renverra la valeur True ; dans le cas contraire, elle renverra la valeur False sans modifier la permutation.
Résolution
On cherche à présent à résoudre des jeux de KenKen. On propose d’essayer de remplir ligne après ligne la grille en commençant par attribuer à la première ligne, la première permutation des entiers de {\llbracket1,n\rrbracket} dans l’ordre lexicographique.
On fait de même pour la seconde ligne, puis les suivantes, en veillant à vérifier à chaque étape que le remplissage partiel de la grille est conforme aux contraintes du jeu : les zones portant sur les cases remplies doivent voir leurs contraintes vérifiées et 2 mêmes entiers ne peuvent se trouver sur une même colonne.
En cas d’échec, on essaie la permutation suivante de la ligne faisant défaut. Si aucune des permutations ne convient, c’est que l’une des lignes précédentes est en cause et on essaie alors la permutation suivante de la ligne qui précède celle faisant défaut.
Cette fonction modifiera la grille en la remplissant par la solution obtenue. La fonction renverra True si elle aboutit à un remplissage valide et False sinon.
Cette fonction retournera l’unique solution au problème et None si elle ne l’a pas trouvée.
Gestion d’un site en ligne
On cherche à présent à élaborer la base de données d’un site internet proposant des grilles de KenKen.
On choisit de stocker les informations des comptes utilisateurs, la liste des grilles disponibles et les informations des temps de résolution des grilles par les utilisateurs. On répartit ces informations en 3 tables dont on présente des extraits ci-après.
La première ligne représente les noms des champs et les suivantes les enregistrements. La clé primaire de chaque table sera indiquée en première colonne. Les clés étrangères seront soulignées.
Une première table utilisateurs permet de stocker les informations personnelles des utilisateurs :
Une seconde table grilles permet de stocker les grilles disponibles pour les joueurs, en particulier leur taille et leur niveau de difficulté.
Une troisième table parties permet de déterminer les temps de résolution des grilles par les joueurs.
On stocke l’identifiant idUtilisateur de l’utilisateur concerné dans u_idUtilisateur qui sera donc une clé étrangère ; de même pour la clé étrangère g_idGrille permettant d’identifier la grille concernée.
Le champ resolue contient 0 pour une grille non encore résolue et 1 sinon tandis que debut (respectivement fin) contient l’instant de début (respectivement de fin) de résolution de la grille par l’utilisateur (exprimé en secondes écoulées depuis le 1er janvier 1970 à minuit).
Enfin le champ note comporte un indice de satisfaction de la grille que fournit le joueur après avoir résolu la grille. Les champs non remplis se verront attribuer la valeur NULL.
On ordonnera les réponses par temps croissant de résolution de la grille.