Projet de Programmation Système

Contexte

On souhaite créer des grilles de sudoku contenant trèss peu de chiffres initiaux. On commence avec une grille complètement résolue et valide. Puis, on prend au hasard une case non vide de la grille et on essaie de résoudre le sudoku en remplaçant cette case par tous les autres chffres. Si au moins une solution est trouvée, alors on n'enlève pas cette case, mais si aucune solution n'est trouvée, alors cela signife qu'il n'y a qu'une seule possibilité de résolution pour cette case, on peut donc l'enlever de la grille.

On procède ainsi jusqu'à ce que la grille ne comporte plus que N chffres (N fixé au début). Cet algorithme de recherche de grille est gourmand en temps de calcul, il faut donc essayer de le découper en différentes tâches en utilisant les threads.

Pour chaque case tirée au hasard, il faut générer huit threads qui vont essayer de résoudre la nouvelle grille en remplaçant la valeur initiale de la case par toutes les autres possibilités. Si l'un d'eux trouve une solution, tous les autres doivent être arrêtés et le calcul est ensuite recommencé pour une autre case par huit nouveaux threads. Sinon, il faut attendre la fin du dernier thread, et si aucun ne trouve de solution (valide), on peut retirer cette case et continuer avec une autre.

Consignes

Spéficiations sur le programme à produire

Le programme que vous devrez produire est un programme générant des grilles de sudoku comportant N valeurs et possédant exactement une solution. Pour ce faire, votre programme devra satisfaire les contraintes suivantes.

• La valeur de N devra être passée en argument en ligne de commande.
• Votre programme devra utiliser des nombres pseudo aléatoire. Il pourra par exemple utiliser les fonctions srand (initialisation de la génération de nombres aléatoires) et rand (production de nombres aléatoires).
• Pour que la grille ait exactement une solution, votre programme devra partir d'une solution valide générée aléatoirement. C'est à vous de créer une fonction C permettant de construire une solution valide. Ensuite, en partant de cette solution, vous pourrez construire la grille ayant seulement N cases non vides.

Makefile

Afin de compiler et d'exécuter votre programme, vous devez écrire un fichier Makefile afin de permettre de compiler et d'exécuter votre programme. Votre Makefile devra contenir trois règles : build qui compile votre programme, run permettant de le lancer (comme il faut passer une valeur pour tester le programme, vous passerez une valeur comprise entre 40 et 50) et enfin debug qui compilera votre programme pour le rendre debogable.

Utilisation de la bibliothèque libsudoku.so

Afin de vous aider à la réalisation de ce projet, vous êtes autoriser à utiliser la la bibliothèque libsudoku.so. Cette bibilothèque contient les fonctions suivantes :

/* Création d'une grille de sudoku */
int **sudoku_init();

/* Libération de la mémoire allouée pour la grille */
void sudoku_free(int **sudoku);

/* Affichage de la grille */
void sudoku_print(int **sudoku);

/* Récupération de la valeur d'une case (si la case est vide, renvoit 0) */
int sudoku_get(int **sudoku, int x, int y);

/* Modification de la valeur d'une case */
void sudoku_set(int **sudoku, int x, int y, int value);

Assurez-vous de placer la bibliothèque libsudoku.so dans un répertoire (lib par exemple).