Contexte du projet
Dans le cadre de ma première année de BUT Informatique, nous avons eu pour mission de développer un solveur de Sudoku en langage Ada. L'enjeu principal n'était pas seulement de résoudre les grilles, mais de le faire le plus rapidement possible, car la promotion s'est ensuite mesurée lors d'un concours de vitesse de résolution.
Ada est un langage fortement typé, conçu pour les systèmes critiques, ce qui en faisait un défi particulièrement formateur pour apprendre la rigueur algorithmique.
Approche algorithmique
L'algorithme développé repose sur une stratégie de backtracking optimisée, complétée par des techniques de propagation de contraintes pour réduire l'espace de recherche avant chaque tentative de placement.
- Backtracking récursif pour explorer les solutions possibles
- Propagation de contraintes : élimination anticipée des valeurs impossibles
- Choix de la case la plus contrainte en priorité (heuristique MRV)
- Traitement de grilles de tous niveaux : facile, moyen, difficile, expert
🏆 Résultat : classé 3ème de la promotion lors du concours de vitesse de résolution, sur une vingtaine d'étudiants.
Difficultés rencontrées
Le langage Ada impose une syntaxe stricte et un typage fort qui m'était inconnu au début du projet. Il a fallu m'adapter rapidement à ses spécificités tout en gardant le cap sur la performance algorithmique.
L'optimisation de la vitesse de résolution a nécessité plusieurs itérations : chaque amélioration algorithmique devait être mesurée et comparée à la version précédente.
Ce que j'ai appris
- Découverte et maîtrise du langage Ada dans un contexte compétitif
- Compréhension profonde du backtracking et de la propagation de contraintes
- Importance de la mesure de performance dans l'optimisation
- Résoudre des problèmes complexes sous contrainte de temps