Nonogram Solver — Programmation par contraintes
Conception d'un système complet de génération et résolution de Nonogrammes via Choco-Solver, avec analyse des performances en fonction de la taille, de la densité et de la structure du puzzle.
Captures d’écran
Cette première illustration montre une grille de Nonogramme entièrement vide avec uniquement les indices autour. Elle représente l'état initial du puzzle : aucune case n'est encore coloriée et seule la structure logique du problème est visible.
Cliquez sur l’image pour l’ouvrir en grand et mieux visualiser les détails.
Ici, la grille est remplie de manière aléatoire : on génère automatiquement des motifs de cases noires en respectant une densité cible. Cette étape illustre comment le système crée des Nonogrammes aléatoires avant même d'appliquer les solveurs.
Cliquez sur l’image pour l’ouvrir en grand et mieux visualiser les détails.
Cette image met en avant les étapes de résolution d'un Nonogramme. On visualise la progression du solveur qui, à partir des indices, déduit progressivement quelles cases doivent être coloriées ou laissées vides jusqu'à rendre la grille cohérente.
Cliquez sur l’image pour l’ouvrir en grand et mieux visualiser les détails.
Ce visuel montre un Nonogramme complètement résolu. Il illustre le résultat final après application de la programmation par contraintes : la grille respecte l'ensemble des indices et révèle le motif caché que l'on cherchait à reconstruire.
Cliquez sur l’image pour l’ouvrir en grand et mieux visualiser les détails.
La dernière illustration compare le comportement des deux modèles de résolution, Ternaire et Regular, sur des puzzles similaires. Elle met en évidence leurs différences en termes de temps de calcul, de robustesse et de capacité à gérer des grilles de tailles et de structures variées.
Cliquez sur l’image pour l’ouvrir en grand et mieux visualiser les détails.
À propos du projet
Projet de stage au laboratoire I3S consacré aux Nonogrammes et à la programmation par contraintes. L'objectif était de concevoir une chaîne complète allant de la génération automatique de grilles jusqu'à leur résolution avec Choco-Solver.
J'ai développé un générateur de grilles aléatoires et à partir d'images, modélisé le problème sous forme de contraintes, puis implémenté deux modèles de solveur (Regular et Ternaire). Le projet inclut également des outils pour analyser l'impact de la taille, de la densité et de la structure des grilles sur les performances.
Ce projet m'a permis d'explorer concrètement la programmation par contraintes, de manipuler de nombreux résultats expérimentaux et de mieux comprendre le comportement algorithmique des solveurs sur des puzzles complexes.