Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

UE : ALGORITHMIQUE ET PROGRAMMATION TRAVAIL PERSONNEL DE L’ETUDIANT : Informati

UE : ALGORITHMIQUE ET PROGRAMMATION TRAVAIL PERSONNEL DE L’ETUDIANT : Information sur les participants : FILIERE : INFOTEL NIVEAU : III IC ENSEIGNANT: Mr DOUWE VINCENT / Mr SAMDALLE AMARIA NOMS ET PRENOMS MATRICULE GORBA HONORE 21D0483EP KOCHE HASSANA NOUHRIYA 21D0485EP NGUEBOU NTCHAMBA JEFFREYS ROSTAND 18A0156P NOLBA BASSANAGA AMOS JUNIOR 21D0495EP République Du Cameroun Paix-Travail-Patrie ****** Ministère De L’enseignement Supérieur ******* Université De Maroua ******* École Nationale Supérieure Polytechnique De Maroua ********* Département D’informatique Et Télécommunications Republic Of Cameroon Peace-Work-Fatherland ********* Ministry Of Higher Education ******** University Of Maroua ******* National Advanced School Of Engineering of Maroua ******* Department Of Computer science And Telecommunications IMPLEMENTATION EN C D’UN PROGRAMME POUR LA RESOLUTION DU SUDOKU Année académique : 2021/2022 TABLE DES MATIERES INTRODUCTION ............................................................................................... 1 I- GENERALITES ............................................................................................ 2 II- APPROCHES A LA RESOLUTION DU PROBLEME ........................ 2 III- PRINCIPE DE RESOLUTION ET COMMENTAIRE ........................ 3 1- Principe de résolution en backtracking ................................................... 3 2- Commentaires ............................................................................................ 3 IV- LES PROTOTYPE DES FONCTIONS PRINCIPALES ET LEURS UTILITES ............................................................................................................ 4 1- fonctions de verifications ........................................................................... 4 2- fonctions principales .................................................................................. 4 CONCLUSION .................................................................................................... 5 1 INTRODUCTION Etymologiquement le mot sudoku vient des mots japonais sû (chiffre) et de doku (unique) qui est un jeu en Forme de grille défini en 1979 et inspiré du carré latin. Le but du jeu est de remplir cette grille avec des chiffres allant de 1 à 9 en respectant certaines Contraintes. Certains de ces chiffres étant déjà disposés sur la grille. La grille du jeu est un carré de 9 cases de côté. Chaque ligne et chaque colonne de la grille ne doit contenir qu’une unique fois chacun des chiffres de 1 à 9. De plus par rapport au carré latin, le sudoku comporte 9 régions de 9 cases formant des carrés de 3 cases de côté. Chacune de ses régions ne peut comporter également que les chiffres de 1 à 9 de manière unique. De par sa médiatisation et son aspect ludique uniquement basé sur les contraintes, le sudoku a grandement intrigué et intéresse encore le monde scientifique notamment orienté vers l’aide des contraintes a la résolution de problèmes. De nombreux problèmes issus du Sudoku ont été amenés à être posés. Resoudre le problème de sudoku consistera pour nous d’une part de présenter les approches à la résolution du problème, le principe de résolution et d’autre part présenter les fonctions principales et leurs utilités, les difficultés rencontré et les solutions proposées. 2 I- GENERALITES Le Sudoku repose sur les principes de la « programmation par contraintes », ce qui fait que sa résolution intéresse beaucoup les informaticiens. La Programmation Par Contrainte dite P.P.C. est devenue indispensable pour gérer de nombreux problèmes complexes tant en recherche que dans l'industrie. Par exemple : • Elaborer le planning des classes d'une école. • Améliorer les itinéraires d'un ensemble d'avions de ligne. • Optimiser le parcours de plusieurs véhicules de livraison. • Planifier la production d'une suite de produits dans une usine. • Partager les bandes passantes entre les serveurs du Web. La résolution d'un sudoku représente le type même de la PPC. C'est pour cela qu'elle est étudiée très tôt comme exemples d'exercices pédagogiques en analyse et programmation. II- APPROCHES A LA RESOLUTION DU PROBLEME La principale tâche de notre travail consistait à implémenter, en C, un programme pour la résolution du Sudoku. Pour y parvenir, nous avons usé des connaissances acquises du cours, parmi lesquelles la manipulation des fichiers, la modularité en subdivisant le programme en de modules plus petits notamment des fonctions, des prototypes et un menu. Nous avons opté pour la résolution du sudoku en backtracking. Par conséquent, Le cœur de cette méthode est la fonction récursive resolve() accompagnée de la fonction case_dispo_nbre(). Ces lignes sont le cœur du système, le reste est principalement réservé à la saisie et à la vérification de celle-ci. Le logiciel prend un fichier en entré avec le format donné dans la fiche de TPE, vérifie la cohérence de celui-ci, fait le traitement et affiche la solution dans un fichier texte de sortie qu’il crée. Le temps de traitement est 3 quasi instantané pour les grilles acceptant une ou plusieurs solutions. Le temps d'exécution peut durer plusieurs minutes sur des grilles n'ayant aucune solution. III- PRINCIPE DE RESOLUTION ET COMMENTAIRE 1- Principe de résolution en backtracking Méthode récursive : La fonction resolve() cherche la première case libre. Puis la case libre cherche le prochain nombre disponible comme solution. Si il y a un nombre de disponible : • Le nombre est affecté à la case. • La fonction s'appelle elle-même, empilage. Donc le programme passera à la case libre suivante. Sinon : • La fonction revient sur elle-même, dépilage. Donc le programme passera à la case libre précédente, qui recherchera le prochain nombre disponible suivant. Notre programme prend en paramètre le nom d’un fichier qui contient la configuration initiale du Sudoku à résoudre et produit en sortie un autre fichier qui contient la configuration finale (une solution possible) dont le nom est le nom du fichier en entrée auquel l’on a ajouté le suffixe « _sol Le fichier de sortiecontient soit: - IMPOSSIBLE s’il n’y a pas de solution possible - une suite de 9 lignes qui contiennent chacune 9 valeurs (entre 1 et 9) séparées par un caractère espace Conformément à l’énoncé donné. 2- Commentaires Le programme résout : • Tout énoncé correct et complet, c'est à dire n'acceptant qu'une solution unique. • Tout énoncé correct et incomplet, même une grille vide, c'est à dire acceptant plusieurs solutions possibles. En modifiant deux lignes dans la fonction resolve(), voir les rems,le programme peut rechercher la suite des solutions possibles afférentes à l'énoncé. 4 IV- LES PROTOTYPE DES FONCTIONS PRINCIPALES ET LEURS UTILITES 1- fonctions de verifications ➢ int verif_saisie_grille(void); verifie si pas de doublon dans l'ensemble de la grille ➢ int verif_saisie_lignes(void); verifie si pas de doublon dans les lignes ➢ int verif_saisie_une_ligne(int ligne,int col,int val); verifie si pas de doublon dans la ligne ➢ int verif_saisie_colonnes(void); verifie si pas de doublon dans les colonnes ➢ int verif_saisie_une_colonne(int col); verifie si pas de doublon dans la colonne ➢ int verif_saisie_carres(void); verifie si pas de doublon dans les carres de 3 X 3 ➢ int verif_saisie_un_carre(int carre); verifie si pas de doublon dans le carre de 3 X 3 ➢ void trans_carre(char tamp[], int carre); transfert le carre de 3 X 3 dans un tableau a une dimension 2- fonctions principales ➢ void resolve(void); fonction recursive qui renvoie la solution. ➢ int case_dispo_nbre(int nbre, int ligne, int col); teste si le nbre est deja place dans la ligne, ou la colonne, ou le carre de 3 X 3 afferent a la case pointee par ligne, col ➢ void trans_carre_de_case(char tamp[], int ligne, int col); tranfert le carre de 3 X 3 d'une case dans un tableau a une dimension 5 CONCLUSION Parvenu au terme de notre travail, il convient de rappeler qu’il était question pour nous d’implémenter, en C, un programme pour la résolution du Sudoku. Nous avons fait usage des notions abordées au cours notamment la manipulation des fichiers, les pointeurs et bien d’autres pour parvenir à l’implémentation et à la réalisation du programme de résolution du sudoku. D’une analyse synthétique de notre part, il en ressort que Le Sudoku repose sur les principes de la « programmation par contraintes », ce qui fait que sa résolution intéresse beaucoup les informaticiens. Cependant, La résolution d'un sudoku représente le type même de la programmation par contraintes. C'est pour cela qu'elle est étudiée très tôt comme exemples d'exercices pédagogiques en analyse et programmation, on ne saurait terminer ce travail sans noter quelques difficultés rencontrées à l’instar de la vérification des doublons dans un bloc et de l’affichage de la solution du sudoku dans le fichier de sorti. Nous avons donc pu surmonter ces obstacles et fournir un programme conformément à l’énoncé donné. Mais toujours est-il qu’aucun programme informatique n’est parfait. uploads/Voyage/ tpe-algo-progra-grp6.pdf