Compétences personnelles
- Mise en place d'une stratégie de résolution
- Recherche de stratégies et de piste d'amélioration
Compétence 2: Optimiser des applications informatiques
Le resolveur de sudoku
Compétences techniques
- Mise en pratique de mes connaissances en langage C
- Utilisation d'un IDE (VSC)
Implémentation de technique de résolution
Après avoir créé le sudoku nous nous sommes intéressés sur différentes techniques de résolutions. Dans un premier temps nous avons implémenté la technique des singletons nus. La technique est simple sur une grille de 16 * 16 nous devions dans un premier temps voir les différents nombres possibles sur une case donnée. Toutes ces possibilités étaient stockées dans un tableau. Pour réaliser toutes ces opérations, nous avions plusieurs fonctions et procédures que vous pouvez retrouver.
Version 1 Version 2Méthode du backtracking
Une des méthodes les plus utilisée est la méthode du backtracking. Cette méthode consiste à parcourir chaque case de la grille de sudoku et pour chaque case regarder si une valeur est possible. Si la valeur peut être posée sur la case elle sera posée. Dans le cas contraire on teste une autre valeur. Nous avons donc une fonction récursive, en effet elle s’appelle à chaque passage de passer à la case d’après. Cette méthode s'arrêtera quand la valeur aura atteint la taille * taille de la grille de sudoku signifiant que toutes les possibilités ont été testées.
Méthode du backtrackingAmélioration du backtracking
Nous avons remarqué que les temps d'exécution étaient assez longs pour des grilles assez grandes. Nous avons donc choisi de changer la structure de la grille. Ainsi nous avons compté le nombre de possibilités dans la grille pour chaque case. Avec cette partie préliminaire nous avons pu garder l’algorithme du backtracking mais en passant plus vite sur les cases et donc de résoudre une grille plus rapidement que la première version.
Code optimisé Les différents temps d'exécutionLangage utlisés
Le problème des huits reines
Nous devions créer un algorithme capable de savoir le nombre de reines pouvant être placées sur un nombre quelconques de cases d'échiquier. Pour ce projet nous avons utilisé le langage python à lequel nous avons fait une interface graphique permettant de voir l'emplacement des différentes reines.
Lien du projetLangage utlisés
