J-0
00m
00j
00h
00min
00s

Version interactive avec LaTeX compilé

Télécharger PDF

Centrale Option Informatique MP 2014

Notez ce sujet en cliquant sur l'étoile
0.0(0 votes)
Logo centrale
🔗 Explorer
Banque
Centrale
Année
2014
Filière
MP
Matière
Info
Centrale MPCentrale 2014MP InfoInfo 2014
2025_08_29_37be61afa5aba94bf553g
Les candidats indiqueront en tête de leur copie le langage de programmation choisi (Pascal ou Caml). Les candidats ayant choisi Caml devront donner le type de chaque fonction écrite. Les candidats travaillant en Pascal pourront écrire des fonctions ou des procédures.
Le sujet comporte trois parties: la partie I est essentiellement consacrée à présenter le problème étudié ; la partie III nécessite d'avoir compris le principe de l'encodage décrit et étudié dans la partie II, mais il n'est pas besoin d'avoir répondu aux questions de la partie II pour l'aborder.

I Présentation du jeu de sudoku

Règles du jeu

Le sudoku est un jeu de réflexion très répandu depuis quelques années. Il se présente sous l'aspect d'une grille carrée à 81 cases ( 9 lignes et 9 colonnes), elle-même scindée en 9 sous-grilles de taille appelées blocs (cf figure 1). Cette grille est initialement partiellement remplie par des chiffres compris entre 1 et 9 : c'est la grille initiale. Le but du jeu consiste à compléter entièrement la grille en remplissant les cases initialement vides par des chiffres de 1 à 9 , de telle manière qu'une fois la grille remplie, chacun des chiffres compris entre 1 et 9 apparaisse une et une seule fois dans chacune des 9 lignes, chacune des 9 colonnes et chacun des 9 blocs de la grille : on obtient alors une grille finale associée à la grille initiale.
9 2 6 5
3 2 7
7 9 5 8
1
7 9
6 4
8 7
3 4 9 1 5
3
0 1 2 3 4 5
0 0 9 0 2 0 0 6
1 3 2 0 0 0 7 0
2 0 7 0 9 0 5 0
3 0 1 0 0 0 0 0
4 0 0 7 0 0 0 0
5 6 0 0 0 0 0 0
6 0 0 8 0 0 0 0
7 0 3 0 4 9 0 0
8 0 0 0 0 0 3 0
0 0
Représentation de la grille initiale ci-contre (où le bloc numéro 3 est grisé)
Figure 1
On suppose dans tout le sujet que la grille initiale est ainsi faite qu'elle admet une et une seule grille finale qui lui soit associée. Résoudre une grille de sudoku consiste donc à déterminer la grille finale associée à une grille initiale donnée.
La figure 1 à gauche représente une grille initiale (dont 24 cases sont remplies). Les blocs sont matérialisés par un trait plus épais.
L'objet du problème est d'étudier un algorithme de résolution des grilles de sudoku fondé sur la manipulation de formules logiques. En effet, le principe de la résolution d'une grille de sudoku peut s'énoncer facilement par les cinq règles logiques ci-dessous.
Construire à partir d'une grille initiale donnée une grille finale telle que :
(K) toute case de contient une et une seule fois l'un des chiffres 1 à 9 ;
(L) toute ligne de contient une et une seule fois chacun des chiffres 1 à 9 ;
(C) toute colonne de contient une et une seule fois chacun des chiffres 1 à 9 ;
(B) tout bloc de contient une et une seule fois chacun des chiffres 1 à 9 ;
(I) toute case de remplie conserve la même valeur dans .
À ces cinq règles, il convient donc d'ajouter implicitement que la grille existe et est unique. On peut remarquer que les quatre premières conditions (K), (L), (C) et (B) présentent de la redondance d'un point de vue logique, mais cette redondance s'avère utile pour déduire plus facilement de nouveaux faits permettant de remplir la grille.

Représentation d'une grille de sudoku

Une grille est représentée par un tableau à deux dimensions à 9 lignes et 9 colonnes numérotées chacune de 0 à 8 . Elle est découpée en 9 blocs numérotés également de 0 à 8 dans l'ordre de lecture de gauche à droite et de haut en bas et les 9 cases d'un bloc donné sont également numérotées de 0 à 8 selon le même procédé. Ainsi, la même case d'une grille peut être référencée de deux manières différentes : pour , on appelle case d'indice ( ) la case de la grille située à l'intersection de la ligne et de la colonne ; pour ( ) , on appelle case de bloc ( ) la case de la grille située dans le bloc numéro ayant le numéro . Une case non encore remplie est affectée de la valeur 0 .
La figure 1 à droite représente le tableau correspondant à la grille initiale donnée à gauche, dans laquelle le bloc numéro 3 est grisé. Les éléments du bloc grisé de numéros et 8 sont donc respectivement affectés des valeurs et 0 . La case d'indice ( 5,0 ) est aussi la case de bloc ( 3,6 ) : elle est grisée de manière plus foncée.

Caml

Une grille de sudoku est représentée par un tableau défini par make_matrix 990 ; pour , l'accès à la case d'indice ( ) d'un tel tableau T se fait par l'expression T.(i).(j).

Pascal

Une grille de sudoku est représentée par un tableau rectangulaire array [0..8,0..8] of integer ; pour , l'accès à la case d'indice d'un tel tableau T se fait par l'expression .

Préliminaires

On commence par écrire quelques fonctions qui seront utiles dans les parties suivantes.
I. - Écrire une fonction appartient d'appartenance d'un élément à une liste.
I. - Écrire une fonction supprime de suppression de toutes les occurrences d'un élément dans une liste.
I. - Écrire une fonction ajoute d'ajout d'un élément dans une liste sans redondance (si l'élément appartient déjà à la liste, on renvoie la liste sans la modifier).
- Écrire une fonction/procédure indice qui, étant donné un couple correspondant à la case de bloc ( ) dans une grille, renvoie l'indice ( ) de cette case dans la grille. Cette fonction pourra utiliser judicieusement les quotients et restes de divisions euclidiennes par 3 et on justifiera les formules utilisées. Par exemple, la case de bloc est la case d'indice (c'est la case grisée en plus foncé dans la figure 1): indice appliqué au couple ( 3,6 ) doit donc renvoyer le couple ( 5,0 ).

Caml

La fonction aura pour signature
indice : int * int -> int * int = < fun >
On rappelle que pour deux entiers et , les expressions quo et mod calculent respectivement leur quotient et leur reste dans la division euclidienne.

Pascal

La procédure aura pour en-tête
procedure indice(b, r: integer ; var i, j : integer) ;
et modifiera la valeur des entiers et .
On rappelle que pour deux entiers et , les expressions DIV et MOD calculent respectivement leur quotient et leur reste dans la division euclidienne.

II Codage de la formule initiale

Représentation des formules logiques

Dans tout le problème, et dénotent respectivement les connecteurs de conjonction, de disjonction et de négation. Étant donné un ensemble de variables propositionnelles, on considère l'ensemble des formules logiques construites à partir de et de l'ensemble de connecteurs .
Une valuation sur est une application (où vrai, faux désigne l'ensemble des booléens); cette application s'étend en une application , attribuant une valeur de vérité à toute formule sous la valuation . Une formule logique est satisfiable s'il existe une valuation telle que vrai. Deux formules logiques et sont équivalentes si pour toute valuation , et on note alors .
Un littéral est une formule logique réduite à ou à , où est une variable propositionnelle. Une clause est une formule logique écrite sous la forme d'une disjonction de littéraux. La clause vide est la clause ne contenant aucun littéral, elle est notée et est considérée comme non satisfiable. Une clause unitaire est une clause réduite à un seul littéral ; une clause unitaire positive (respectivement négative) est une formule logique réduite à (respectivement à ), où est une variable propositionnelle. Une formule en forme normale conjonctive est une formule logique écrite sous la forme d'une conjonction de clauses. La formule vide est la formule ne contenant aucune clause, elle est notée et est considérée comme satisfiable.
Dans tout le problème, les variables propositionnelles sont indexées par un triplet d'entiers ( ) et notées , avec la sémantique suivante : pour un triplet , une valuation assigne la valeur vrai à lorsque la case d'indice ( ) de la grille de sudoku contient la valeur . L'ensemble utilisé dans le problème est donc constitué des variables propositionnelles , où ( ) parcourt .
À titre d'exemples :
  • la clause exprime qu'une au moins des quatre cases situées aux coins de la grille est occupée par un 5 ;
  • la formule sous forme normale conjonctive exprime que chacune des valeurs de la colonne 7 est constituée de chiffres compris entre 1 et 9 ;
  • la clause exprime que l'une des cases du bloc numéro 3 de la grille contient le chiffre 6 (où indice est la fonction/procédure de la question I.D).
    Pour la programmation, les clauses sont des listes de littéraux et les formules logiques (qui seront écrites exclusivement en forme normale conjonctive) des listes de clauses.
    Ainsi, en notant les listes entre , la formule est représentée formellement par la liste de listes (où un triplet surligné désigne un littéral négatif). Plus précisément:

Caml

On déclare le type litteral comme suit:
type litteral of int int int NonX of int int int ; ;
Dans un triplet d'entiers de type int * int * int, le premier élément correspond au numéro de ligne, le second au numéro de colonne et le troisième à la valeur comprise entre 1 et 9 . Une clause est de type litteral list et une formule logique (en forme normale conjonctive) de type litteral list list.

Pascal

On déclare le type litteral comme suit:
type litteral record signe : boolean ; i : integer ; j : integer ; k: integer end ;
On dispose d'une fonction
litt(signe: boolean; i: integer ; j: integer ; k: integer) : litteral
qui permet de créer des littéraux. Par exemple litt(true, 0, 0, 9) renvoie le littéral et litt(false,
) renvoie le littéral . On suppose qu'on a défini les types clause et formule comme des listes pour lesquelles on dispose des primitives usuelles suivantes:
  • Nil qui est la liste vide ; on peut tester si une liste 1 est vide avec l'expression ;
  • tete(c: clause) : litteral et tete(f : formule) : clause qui permettent d'obtenir le premier élement d'une liste ;
  • queue(c: clause) : clause et queue(f : formule) : formule qui permettent d'obtenir la queue d'une liste ;
  • ajout_en_tete(l : litteral ; c : clause) : clause et ajout_en_tete(c : clause ; f : formule) : formule qui permettent d'ajouter un élément en tête d'une liste ;
  • concatener(f1: formule ; f2: formule) : formule qui permet de concaténer deux listes, cette fonction a un coût linéaire en la taille de la première liste.
    On suppose que l'on peut tester l'égalité de deux littéraux 11 et 12 à l'aide de l'expression . Cette opération n'est pas disponible pour les clauses et les formules.
Avant de décrire des stratégies de résolution d'une grille de sudoku, on va coder l'information contenue dans la grille initiale par une formule logique en forme normale conjonctive. Ce codage se fait en deux temps : on code déjà la règle générale du jeu, représentée par les quatre règles logiques (K), (L), (C) et (B) ; puis on code l'information propre à la grille initiale fournie, qui repose sur la cinquième règle (I).

II.A - Formule logique décrivant la règle du jeu

On s'intéresse dans cette partie à coder par une formule logique en forme normale conjonctive l'information fournie par la règle du jeu.
Chacune des quatre règles logiques et peut être scindée en deux sous-règles:
(K1) toute case de contient au moins une fois l'un des chiffres 1 à 9 ;
(L1) toute ligne de contient au moins une fois chacun des chiffres 1 à 9 ;
(C1) toute colonne de contient au moins une fois chacun des chiffres 1 à 9 ;
(B1) tout bloc de contient au moins une fois chacun des chiffres 1 à 9 ;
(K2) toute case de contient au plus une fois l'un des chiffres 1 à 9 ;
(L2) toute ligne de contient au plus une fois chacun des chiffres 1 à 9 ;
(C2) toute colonne de contient au plus une fois chacun des chiffres 1 à 9 ;
(B2) tout bloc de contient au plus une fois chacun des chiffres 1 à 9 .

II.A.1)

a) Pour , écrire une clause qui traduit la phrase mathématique : .
b) Traduire la condition (K1) par une phrase mathématique.
c) En déduire une formule en forme normale conjonctive qui exprime la condition (K1).
d) Déterminer le nombre de clauses que contient .
e) Écrire une fonction case1 qui ne prend pas d'argument et renvoie la liste qui représente la formule logique .
II.A.2) Traduire la condition (L1) par une phrase mathématique et en déduire une formule en forme normale conjonctive qui exprime (L1).

II.A.3)

a) Obtenir de même des formules logiques et exprimant les conditions (C1) et (B1).
b) Écrire une fonction bloc1 qui renvoie la liste qui représente la formule logique .

II.A.4)

a) Pour , exprimer mathématiquement le fait que la ligne de numéro de la grille contient au plus une fois la valeur et écrire une formule en forme normale conjonctive qui traduit cette condition.
b) En déduire une phrase mathématique qui traduit la condition (L2) et une formule en forme normale conjonctive qui exprime (L2).
c) Déterminer le nombre de clauses que contient L2.
d) Écrire une fonction lig2 qui renvoie la liste qui représente la formule logique .
II.A.5) Obtenir de même des formules logiques et exprimant les conditions (C2), (B2) et (K2).
On suppose avoir écrit des fonctions lig1, col1, case2, col2 et bloc2 qui renvoient respectivement les listes qui représentent les formules logiques et .
On pose alors èè est la formule logique en forme normale conjonctive décrivant la règle du jeu. Elle contient 11988 clauses.

II.B - Formule logique décrivant la grille initiale

On s'intéresse dans cette partie à coder par une formule logique en forme normale conjonctive l'information fournie par la grille initiale à compléter.
On pourrait pour cela se contenter de considérer une formule logique construite à partir de la cinquième règle (I) donnée au début de l'énoncé : pour toute case de la grille d'indice initialement remplie par la valeur , on considère la clause réduite au littéral positif et, si est le nombre de cases remplies dans la grille initiale, on pose comme étant la conjonction des clauses ainsi obtenues.
Mais, pour accélérer la phase d'inférences logiques qui sera menée dans la partie III, on n'hésite pas à introduire à nouveau de la redondance en déduisant d'emblée un certain nombre de faits que l'on ajoute à la formule liée à la grille initiale. Ces nouveaux faits sont de deux ordres :
  • si dans la grille initiale, la case d'indice est déjà remplie par la valeur , on peut considérer d'emblée, en plus de la clause unitaire positive (déjà prise en compte par la formule ci-dessus), les 8 clauses unitaires négatives avec ; on enrichit ainsi la formule en une formule
    en forme normale conjonctive constituée de clauses unitaires positives (celles de ) et négatives (où est le nombre de cases remplies dans la grille initiale) ;
  • si, dans une grille initiale, une case d'indice ( ) n'est pas remplie (c'est-à-dire est occupée par la valeur 0 ), alors on sait que cette case ne peut être remplie par aucune valeur apparaissant déjà dans la ligne , ou dans la colonne , ou dans le bloc auquel appartient la case d'indice ( ); puisqu'une telle valeur est interdite pour la case d'indice ( ), on peut donc considérer la clause unitaire négative ; ainsi, pour la case d'indice ( 1,3 ) de l'exemple de la figure 1 à droite, il n'est pas question de remplacer la valeur 0 par aucune des valeurs appartenant à : on peut donc ajouter les clauses , et ; on note alors la formule en forme normale conjonctive constituée de la conjonction de toutes ces clauses unitaires négatives obtenues en parcourant toutes les cases non remplies de la grille initiale.
    La formule décrivant la grille initiale est donc .
    II.B.1) Écrire une fonction donnees qui, à partir d'une grille de sudoku initiale (donnée sous la forme d'un tableau), renvoie la formule , toujours sous la forme d'une liste de listes de littéraux.

II.B.2)

a) Étant donnée une case d'indice , exprimer en fonction de et le numéro de bloc auquel cette case appartient.
b) Écrire une fonction interdites_ij qui, étant données une grille de sudoku initiale et une case d'indice ( ) non remplie de la grille initiale, renvoie la conjonction des clauses unitaires négatives correspondant aux valeurs interdites pour la case d'indice ( ).
c) Écrire une fonction interdites qui, à partir d'une grille de sudoku initiale, renvoie la formule .
II.B.3) Montrer que le nombre de clauses de la formule est majoré par 729 .

Formule initiale complète

D'après II.A et II.B, la formule logique à associer à une grille initiale qui code à la fois les informations qu'elle contient et qui peut permettre de la résoudre est donc è.
On supposera dans la partie III avoir écrit une fonction formule_initiale qui, à partir d'une grille initiale, renvoie la formule .

Caml

Cette fonction a pour signature:
formule_initiale : int vect vect -> litteral list list = < fun >

Pascal

Cette fonction a pour en-tête:

III Résolution d'une grille de sudoku

III.A - Règle de propagation unitaire

Nous supposons désormais que nous disposons d'une formule en forme normale conjonctive encodant un sudoku. Pour le résoudre on cherche à satisfaire .
III.A.1) Combien existe-t-il de valuations satisfaisant ?
III.A.2) Déterminer le nombre de lignes de la table de vérité de .
Il semble donc illusoire de construire une telle table de vérité en un temps raisonnable. Nous proposons donc une méthode qui n'est pas assurée de conclure dans tous les cas mais qui utilise un nombre polynomial d'opérations. Soit une formule en forme normale conjonctive. On suppose que contient une clause unitaire réduite au littéral . Un tel littéral est appelé littéral isolé. Nous pouvons alors simplifier la formule de la manière suivante:
  • en supprimant toutes clauses de qui contiennent ;
  • en supprimant de toutes les clauses de (ainsi si une clause ne contient que elle est remplacée par la clause vide )
    Par exemple la formule contient un unique littéral isolé . En simplifiant par ce littéral, on obtient la formule .
    III.A.3) On justifie formellement cette simplification. Soit une formule en forme normale conjonctive contenant un littéral isolé (associé à la variable propositionnelle : on a donc ou ). F peut s'écrire alors sous la forme , où :
  • est une formule constituée de clauses contenant chacune le littéral ;
  • est une formule constituée de clauses contenant chacune le littéral et ne contenant pas le littéral ;
  • est une formule constituée de clauses ne contenant chacune ni le littéral , ni le littéral .
Remarquons que chacune des formules et peut être réduite à la formule vide, satisfiable.
La formule simplifiée de par le littéral est alors la formule , où s'obtient à partir de en supprimant toutes les occurrences du littéral dans chacune des clauses de .
Soit une valuation de . Montrer que satisfait si et seulement s'il existe une valuation de prenant les mêmes valeurs que sur qui satisfait . On précisera la valeur de .
L'algorithme de résolution du sudoku que nous proposons est appelé algorithme de propagation unitaire et consiste à appliquer la simplification présentée ci-dessus de manière répétée tant que l'on peut déduire de nouveaux littéraux isolés.
III.A.4) Appliquer l'algorithme de propagation unitaire à la formule

III.A.5)

a) Sur l'exemple de la figure 1 , déterminer la valeur de la case d'indice ( 0,7 ) dans la grille finale en raisonnant à la manière d'un joueur de sudoku (le raisonnement suivi sera décrit).
b) Retrouver le résultat de la question précédente en appliquant l'algorithme de propagation unitaire, c'est-à-dire montrer que l'on peut, au terme d'un certain nombre de simplifications à partir de la formule associée à cette grille initiale, déduire le littéral isolé . On ne sélectionnera dans la formule que des clauses utiles à l'obtention du littéral isolé .
III.A.6) Écrire une fonction nouveau_lit_isole qui, à partir d'une formule , renvoie un littéral isolé de . Si ne contient pas de tel littéral, la fonction renverra le littéral qui n'est pas utilisé comme variable propositionnelle par ailleurs.
III.A.7) Écrire une fonction simplification qui, à partir d'un littéral et d'une formule , renvoie la formule simplifiée après propagation du littéral dans .
III.A.8) Écrire une fonction propagation qui, à partir d'un tableau représentant le sudoku et d'une formule représentant les contraintes du sudoku, renvoie la formule obtenue par propagation unitaire. Cette fonction modifiera le tableau quand de nouveaux littéraux isolés découverts au cours de l'algorithme permettent de déduire la valeur d'une case du sudoku.
III.A.9) Que peut-on dire sur le tableau modifié et la formule renvoyée par la fonction propagation dans le cas où l'algorithme de propagation unitaire permet de résoudre le sudoku? Et dans le cas où il ne permet pas de le résoudre?
III.A.10) On appelle taille d'une formule le nombre total de littéraux apparaissant dans ses clauses. Évaluer le nombre d'opérations effectuées par les fonctions nouveau_lit_isole, simplification, puis par la fonction propagation quand elles s'appliquent à une formule de taille . On donnera une estimation de la forme que l'on justifiera.

III.B - Règle du littéral infructueux

On décrit maintenant une autre méthode de déduction plus puissante combinant la propagation unitaire et une opération appelée règle du littéral infructueux décrite ci-dessous.
Étant donné une formule en forme normale conjonctive et une variable propositionnelle ,
  • si l'algorithme de propagation unitaire appliqué à la formule permet de déduire la clause vide alors on ajoute la clause à ;
  • si l'algorithme de propagation unitaire appliqué à la formule permet de déduire la clause vide alors on ajoute la clause à .
    III.B.1) Justifier formellement que si l'on peut déduire la clause vide à partir de la formule alors 。
    III.B.2) Écrire une fonction variables qui, à partir d'une formule, renvoie la liste de ses variables sans doublons.
    On supposera qu'on dispose d'une fonction flatten qui à partir d'une formule renvoie la clause formée de tous les éléments des sous-listes de . Par exemple flatten appliqué à renvoie .
    III.B.3) Écrire une fonction deduction qui, à partir d'un tableau, d'une variable et d'une formule , renvoie 1 si la règle du littéral infructueux permet d'ajouter la clause à si elle permet d'ajouter la clause à et 0 sinon.
    On supposera qu'on dispose d'une fonction copier_matrice qui à partir d'un tableau renvoie un autre tableau distinct contenant les mêmes valeurs.
    III.B.4) Nous proposons un deuxième algorithme de propagation basé sur la règle du littéral infructueux. Celui-ci consiste à appliquer la propagation unitaire et, quand celle-ci ne permet plus de déduire de nouvelles clauses, à appliquer la règle du littéral infructueux pour obtenir une nouvelle clause unitaire de la forme ou . Dès lors on peut reprendre la propagation unitaire. Le processus s'arrête lorsque ni la propagation unitaire ni la règle du littéral infructueux ne permettent de déduire de nouvelles clauses.
    Écrire une fonction propagation2 qui, à partir d'un tableau représentant le sudoku et d'une formule représentant les contraintes du sudoku, met en œuvre cet algorithme. Cette fonction modifiera le tableau selon la valeur des cases pouvant être déduites.
    III.B.5) Écrire une fonction sudoku qui, à partir d'un sudoku donné sous forme d'un tableau , modifie et renvoie la grille complétée au maximum en utilisant les techniques précédentes.
    Expérimentalement, la règle de propagation unitaire permet de résoudre les sudokus les plus faciles et environ la moitié des sudokus les plus difficiles. À notre connaissance, il n'existe pas de sudoku ne pouvant être résolu intégralement à l'aide de la règle du littéral infructueux.
Centrale Option Informatique MP 2014 - Version Web LaTeX | WikiPrépa | WikiPrépa