sujet PDF
Contents
1. de tester si elles ont une solution Comme pour la question 1 on vous demande de g n rer une instance du probl me SAT telle que toute valuation qui satisfait l instance repr sente une grille qui poss de au moins une solution Comme pour la question 1 expliquez votre codage du probl me en logique propositionnelle Vous pourrez tester votre proc dure en utilisant la proc dure de la question 1 pour r soudre les grilles que vous g n rez Etendre votre proc dure pour qu elle g n re n grilles diff rentes n tant donn en param tre par l utilisateur Expliquez comment vous proc der Pour acc l rer votre programme lors de la g n ration de n grilles vous pouvez utiliser l incr mentalit de MiniSat Par exemple si vous ajoutez des clauses suppl mentaires une formule au lieu de d clarer un nouveau solveur vous pouvez relancer le solveur pr c dent avec la nouvelle formule MiniSat r utilise en effet les r sultats pr c dents pour la r solution de la nouvelle formule Par exemple le programme suivant Solver s createClauses1 s s solve Solver s createClauses1 s createClauses2 s s solve o les proc dures createClauses1i et createClauses2 g n rent un ensemble de clauses et l ajoute au solveur peut tre optimis en Solver s createClauses1 s s solve createClauses2 s s solve Notez que cette fonctionnalit ne peut tre utilis e que si vous utilisez2. les sources de MiniSat Question 3 Unicit de la solution Ecrire une proc dure qui r sout une grille comme dans la question 1 et qui teste si la solution est unique via une instance de SAT Si la solution n est pas unique votre proc dure devra sortir une deuxi me solution Attention n oubliez pas que la lettre A est toujours donn e au d part et ne peut donc pas tre d plac e Expliquez comment vous proc der en particulier expliquez quelles formules vous g n rez Vous pouvez tester votre proc dure sur les exemples qu on vous a donn s dans les r pertoires unique pour les grilles avec solution unique et les r pertoires notunique pour les grilles avec au moins deux solutions pour des grilles de taille 7x7 et 8x8 Pour la question suivante on pourra se limiter des grilles de taille 8x8 au plus Question 4 Bonus 1 G n ration de grilles avec au moins deux solutions Ecrire une proc dure qui g n re n grilles diff rentes n tant donn en entr e telle que chaque grille a au moins deux solutions On ne vous demande pas ici de proc der en deux tapes g n rer une grille et tester si la solution est unique recommencer sinon jusqu temps que n grilles soient trouv es On vous demande plut t de proc der en une seule tape g n rer une seule instance de SAT telle que les valuations qui satisfont cette instance repr sentent des grilles avec au moins deux solutions Pour la question pr c dente vous
3. on vous demande de donner dans un fichier 5 grilles g n r es pour chaque taille 7x7 8x8 et 9x9 Les grilles seront au format texte comme dans la section 1 s par es par une ligne vide Vous devez donc rendre trois fichiers pour la question 2 chacun avec 5 grilles deux fichiers pour la question 4 car on se limite aux grilles de taille 8x8 au plus et un fichier pour la question 5 on se limite aux grilles de taille 7x7 Le tout rapport grilles g n r es et sources devra tre rendu dans un dossier compress dont le nom portera les deux noms de famille du bin me et envoy l adresse efiliot ulb ac be avec pour objet Projet Logique nom de famillei nom de famille2 Le fichier est envoyer pour la m me date que la version papier
4. que les temps de calcul soient longs jusqu plusieurs minutes pour les grandes grilles soyez patients Question 1 R solution d une grille Ecrire une proc dure qui prend en entr e une grille au format texte de la section 1 et qui r sout cette grille en utilisant MiniSat Votre proc dure devra donner la solution sous format texte comme dans la section 1 Votre proc dure devra g n rer une instance du probl me SAT telle que les valuations qui satisfont la formule s il en existe repr sentent des solutions de la grille Expliquer comment vous coder le probl me comme une instance du probl me SAT repr sentation de la grille des lettres des variables formules g n r es ventuellement expliquer comment vous mettez sous forme normale conjonctive l adresse http www ulb ac be di info f 302 index html vous trouverez un ensemble de grilles 7x7 8x8 et 9x9 pour tester votre proc dure Question 2 G n ration de grilles Ecrire une proc dure qui g n re une grille c est dire un contour et le placement de la lettre A de d part telle que la grille g n r e a au moins une solution Pour cette question la contrainte est la suivante une m me lettre ne peut pas appara tre plus d une fois sur le contour et le n appara t pas sur le contour cette contrainte serait en effet inutile car la position du A est donn e au d part Pour cette question il ne s agit pas de g n rer al atoirement des grilles et
5. un vecteur de lit raux vec lt Lit gt lits clause pO or not pi lits push Lit 0 ajout du lit ral 0 lits push Lit 1 ajout du lit ral non 1 s addClause lits ajout de la clause clause not p0 or p2 lits clear r initialisation du vecteur de clauses lits push Lit 0 ajout du lit ral non 0 lits push Lit 2 ajout du lit ral 2 s addClause lits ajout de la clause if s solve r solution par MiniSat la formule est satisfaisable cout lt lt La formule est satisfaisable avec la valuation o n for int i O0 i lt 2 i r cup ration de la valuation if s model i 1_True cout lt lt la variable lt lt i lt lt est mise vraie n else cout lt lt la variable lt lt i lt lt est mise faux n else cout lt lt La formule n est pas satisfaisable n Si votre clause ne contient qu un seul lit ral vous pouvez utiliser la m thode addUnit par exemple addUnit Lit 0 Si elle ne contient que deux lit raux vous pouvez utiliser par exemple addBinary Lit 0 Lit 2 3 Questions Dans toutes ces questions vous pouvez vous contenter de ne consid rer que des grilles de taille 5x5 Si votre programme prend en plus la taille de la grille comme un param tre d fini par l utilisateur il vous sera attribu un bonus Toutefois vous pouvez vous limiter des grilles de taille 9x9 au plus Attention il se peut
6. UNIVERSITE LIBRE DE BRUXELLES INFO F 302 Logique informatique Projet Le Jeu ABCPath et Utilisation d un Solveur SAT L objectif de ce projet est de mod liser plusieurs probl mes en logique propositionnelle autour du jeu ABCPath et de r soudre ces probl mes l aide du solveur SAT MiniSat 1 Le Jeu ABCPath Une instance du jeu ABCPath est donn e par une grille 7x7 BCDWJNF RA X S V U 0 G I M E TYHKQPL Nous appellerons contour la partie ext rieure de la grille c est dire celle o apparaissent les lettres B C D W J N F X V etc Nous appellerons int rieur le reste de la grille c est dire le carr 5x5 se trouvant au milieu L objectif est de remplir l int rieur de cette grille avec les lettres A jusque Y avec les contraintes suivantes la position du A est toujours donn e 1 chaque lettre n appara t qu une seule fois l int rieur 2 pour toute lettre a qui n est pas Y la lettre suivante dans l ordre alphab tique appara t dans le voisinage direct de a Autrement dit si i j est la position de a la lettre suivante se trouve en position i d j e pour un certain couple d e 1 0 1 x 1 0 1 3 pour chaque lettre du contour une lettre de la colonne ligne diagonale correspondante doit appara tre dans l int rieur de la grille Par exemple le C doit appara tre dans la premi re colonne de l int rieur le S dans la deuxi me li
7. aurez peut tre besoin d utiliser l astuce suivante pour mettre une formule sous forme normale conjonctive en ajoutant des variables Prenons par exemple la formule suivante ni N2 NZ V A sx i 1 j 1 k 1 o pour tout i 1 n1 j 1 n k E 1 n3 lijk est un lit ral Pour mettre cette formule en forme normale conjonctive vous pouvez distribuer la disjonction au risque de cr er une formule exponentiellement plus grande ou utiliser l astuce suivante pour tout i j ajouter la variable y j et transformer la formule comme ceci Ni N2 Ni N2 A V uD AA AG usa i 1 j 1 i 1 j 1 Cette formule peut facilement tre mise sous forme normale conjonctive n no ni N2 N3 ni n2 N V uia AA N vi V lis A A N tisy de i 1 j 1 i 1 1 k 1 i 1 j 1 k 1 Il est donc possible en introduisant de nouvelles variables de mettre en forme normale conjonctive une formule en vitant l explosion combinatoire Si on applique cette astuce la formule suivante a Ab V aAc A aAb Vd on obtient en premi re tape la formule y1 V y2 A y3 V ya A y a Ab y2 a Ac A y3 ma b A ya d Chaque double quivalence peut facilement tre mise sous forme normale conjontive et la formule devient y1 V y2 A y3 V ya Ag V a A yi V b A Aly V a V b A A y V a A y2 V A y2 V na V c A A y3 V ma A oys V b A y3 V a V b A ya V nd A ya V d Toute valuation qui
8. gne de l int rieur le K dans la troisi me colonne dans l int rieur le B dans la diagonale de l int rieur qui commence en haut gauche etc Voici une solution pour cette grille BCDWJNF RAXWQRX SYBVSPV UCHTUOO GGDILNI MFEKJME TYHKQPL Vous pouvez vous entrainer r soudre des grilles l adresse suivante http www brainbashers com abcpath asp Dans ce projet il vous sera demand de r soudre des grilles l aide d un solveur SAT de tester l unicit d une solution de g n rer des grilles avec au moins deux solutions ou avec solution unique tout cela pour des grilles de tailles variables 7x7 8x8 ou 9x9 On peut en effet g n raliser le probl me des grilles de taille plus grande on aura alors besoin de plus de lettres Nous utiliserons les lettres minuscules a b c etc qui seront tri es dans l ordre suivant A B Y Z a b z Par exemple pour une grille 8x8 la grille int rieure aura une taille 6x6 donc on prendra les 36 lettres dans l intervalle Aj et les contraintes de contour seront elles aussi exprim es avec des lettres de l intervalle Aj Voici par exemple une grille 8x8 FHdKLMSO J AE D B G c R P Y U SE R te g aIbZXWTQ et une solution FHdKLMSO JIJELMAE DHFKDNBB GGbj0csc RciaPRTP YhdZYQUU egfeXxXWVeg albZXVWTAQ 2 Le Solveur SAT MiniSat Le solveur SAT MiniSat prend en entr e une formule de logique propositionne
9. lle en forme normale conjonctive en teste la satisfiabilit et retourne une valuation qui satisfait la formule dans le cas o elle est satisfaisable Dans ce projet nous vous laissons le choix de l utilisation de MiniSat vous pouvez soit programmer dans le langage de votre choix et faire des appels MiniSat via son syst me d entr es sorties soit programmer en C et utiliser directement la biblioth que C MiniSat que nous vous fournissons Dans le premier cas vous devrez installer MiniSat vous m me partir de l adresse suivante http minisat se MiniSat html MiniSat prend des fichiers au format Dimacs expliqu ici http 1logic pdmi ras ru basolver dimacs html Si vous utilisez la biblith que MiniSat que nous vous fournissons vous pouvez repartir du code utilis pour la r solution du probl me Sudoku disponible l adresse suivante http www ulb ac be di info f 302 index html Dans cette biblioth que chaque variable propositionnelle est repr sent e par un entier Pour cr er une clause il faut cr er une liste de lit raux Voici un exemple de code qui cr e la formule po V p1 po V p2 et affiche une valuation si la formule est satisfaisable La variable p est repr sent e par l entier pour tout i 0 1 2 include Solver hpp d claration d un solveur MiniSat Solver s ajout de trois variables for int i 0 i lt 2 i s newVar d claration d
10. satisfait cette derni re formule satisfait aussi la formule d origine R ciproquement toute valuation v de la formule d origine donc des variables a b c d peut tre transform e en une valuation 6 qui satisfait la nouvelle formule de la mani re suivante 8 a v a 8 b v b B c v c B d v d et By v a Av b B y2 v a Av c B ys v a Av b et B ya v a Pour la question suivante on pourra se limiter aux grilles de taille 7x7 mais si vous tes capables d y r pondre pour des grilles plus grande c est un plus Question 5 Bonus 2 G n ration de grilles avec solution unique En vous aidant du sol veur MiniSat crire un algorithme qui g n re n grilles telles que pour chaque grille la solution est unique Pour cette question il west pas demand de r soudre le probl me directement par n appels MiniSat mais il faut vous aider de MiniSat Conseil observez les raisons pour lesquelles une solution n est pas unique et essayez d interdire certains motifs lors de la g n ration des grilles Modalit s Le projet se fait en bin me il est rendre au bureau de Maryka Peetroons pour le 8 Mai 16h Il doit comprendre un rapport papier qui r pond aux questions et explique la mani re dont vous codez les diff rents probl mes commme des instances de SAT Il vous est demand de rendre les sources de votre programme avec un manuel d installation utilisation Pour la g n ration de grilles
Download Pdf Manuals
Related Search