Raphael Della Negra

Le picross est un jue style journal, oû l'on doit remplir une grille de cases selon des indices sur les côtés. Par exemple, une ligne avec les indices 5-2 indique que la ligne correspond à un bloc de 5 cases noires, au moins un blanc, puis un bloc de 2 cases noires. L'objectif est donc de comparer les indices des lignes et des colonnes pour remplir la grille. Vous pouvez tenter de jouer ici pour bien saisir les règles : https://fr.puzzle-nonograms.com/

Contexte

Pour étudier la complexité des algorithmes, un projet du second trimestre consiste à programmer un solveur picross de deux manières différentes: Une version naïve qui essaie toutes les possibilités, et une version avec propagation de contraintes plus maligne. Nous étions en binôme pour ce projet, et je me suis concentré sur la deuxième méthode alors que mon camarade programmais la première. Je me concentrerais donc sur la seconde.

Objectifs

La méthode par propagation de contraintes fonctionne comme ceci: Chaque ligne peut avoir des cases certaines selon les indices déjà présents. Par exemple dans une ligne de 5 cases avec comme indices 3, il y a trois possibilités:

3|XXX__
3|_XXX_
3|__XXX

On voit que qelque soit la réponse, la case du milieu sera toujours noire. On peut donc dors et déjà la colorier en noir. Ensuite, les colonnes pourrons prendre cette case en compte Par exemple, pour une colonne d'indices 2, avec cette case en première ligne:

2222
----
X___
XX__
_XX_
__XX
___X

On ne peut pas trouver de cases certaines dans cette configuration, Mais connaitre une case suffit à ne garder que 2 possibilités (soit 2 nouvelles cases certaines), voire une seule si cette case est sur un bord.
On peut donc continuer à alterner lignes - colonnes jusqu'à trouver la solution

Ensuite, il reste à calculer la complexité du programme, c'est à dire comment la durée du programme évolue selon la taille de la grille. Récapitulons. Pour une grille de taille n*n, avec une densité k :

On parcours chaqe ligne de la grille, puis chaque colonne, le tout un nombre indéterminé de fois (notons le A): ((n+n)*A) = 2An
Pour chaque ligne/colonne, on boucle sur chaque case de chaque ligne possible pour trouver les cases certaines, donc (n*f(k)) = nf(k). On utilise f(k) plutôt que k car il y a plus de possibilités quand k approche de 50%.
La complexité vaut donc 2An*nf(k) = 2Af(k)n².

Pour connaitre l'ordre de la complexité, il y a juste à retirer les facteurs négligeables: 2A, et f(k).
L'algorithme a donc une complexité d'ordre O(n²). Pour comparaison, la version naïve a fini avec une complexité d'ordre O(f(k)ⁿ). L'ordre O(n) veut dire que la durée du programme augmentera 2 fois plus vite que la taille de la grille.

Résulats

J'ai beaucoup aimé travaillé sur ce solveur. Le picross est un jeu que j'aime beaucup, et j'ai pu trouver des stratégies pour optimiser un code, Vous pouvez retrouver la page git du projet ici: https://gitlab.com/groupe_rml/sae202-solveur_picross, Et télécharger les fichiers ici
Outre l'optisation, ce projet m'a permi de reprendre la main sur python, et à apprendre le LaTex, dont j'ai décidé de me servir pour le compte rendu du projet.