Licence Informatique 1 - Projet Sudoku

Le jeu se présente sous la forme d'un tableau de cases à deux dimensions, de 9 lignes sur 9 colonnes. Ces cases sont de plus regroupées en 9 blocs carrés de 3 cases sur 3.

Le but du jeu est de remplir ce tableau avec des chiffres allant de 1 à 9, en respectant les contraintes suivantes :

• chaque ligne du tableau contient une seule fois chaque chiffre
• chaque colonne du tableau contient une seule fois chaque chiffre
• chaque bloc carré contient une seule fois chaque chiffre

Au départ du jeu, certaines cases sont fixées : c'est la grille initiale. Si une grille initiale est correcte, il doit exister une unique solution pour la compléter en respectant ces contraintes.

Ce programme se décompose en plusieurs étapes :

1. initialisation (récupération dans une liste de grilles prédéfinies) ;
2. définition d'une interface pour afficher la grille et permettre au joueur de remplir les cases libres ;
3. remplissage de la case : détermination des contraintes éventuellement violées et indication au joueur (en refusant d'inscrire le chiffre dans la case, et/ou en mettant en évidence le doublon).

Pour l'étape 2 ci-dessus, il peut être pratique de poser un chiffre au moment ou l'utilisateur appuie sur une touche du clavier ou sur un bouton de la souris (par exemple, clic gauche pour choisir un chiffre plus grand, clic droit pour un chiffre plus petit, clic du milieu pour effacer le contenu de la case).

• Il faut donc pouvoir récupérer le numéro du bouton de la souris cliqué, à l'intérieur de la fonction de callback associée aux cases du tableau. Pour cela, il ne faut pas utiliser le signal "clicked", mais le signal "button_press_event". La fonction de callback reçoit alors trois paramètres : le widget ayant émis le signal, l'évènement survenu sur ce widget (du type GdkEventButton *) et la donnée utilisateur (userdata). Le type GdkEventButton est un type structuré contenant le champ button, qui vaut 1, 2 ou 3 selon le bouton de la souris qui a provoqué l'envoi du signal. Dernière chose à savoir : pour que ce numéro de bouton soit effectivement enregistré et transmis à la fonction de callback, il faut le demander à GTK poliment, en appelant avant de lancer l'interface la fonction gtk_widget_set_events. Par exemple, pour que le callback d'un bouton b1 puisse recevoir le numéro de bouton de la souris, on appellera :

  gtk_widget_set_events( b1, GDK_BUTTON_PRESS_MASK );
  

• Pour récupérer le numéro d'une touche du clavier pressé, il faut utiliser le signal "key-press-event". La fonction de callback reçoit alors trois paramètres : le widget ayant émis le signal, l'évènement survenu sur ce widget (du type GdkEventKey*) et la donnée utilisateur (userdata). Le type GdkEventKey est un type structuré contenant le champ keyval, qui est un entier contenant le code de la touche qui a provoqué l'envoi du signal.

Un exemple complet est donné ici. Compilez-le et lancez-le, puis cliquez avec les différents boutons de la souris et pressez différentes touches du clavier. Essayez les touches du clavier numérique (probablement utiles pour le Sudoku).

• Menu permettant de remettre à zéro la grille
• Menu permettant de tirer une autre grille
• Menu permettant de sauver dans un fichier une grille en cours
• Menu permettant de charger une grille commencée depuis un fichier
• Aider l'utilisateur en lui donnant la liste des choix possibles pour une case, étant données les cases déjà remplies sur la ligne, la colonne et le bloc de cette case
• Aider l'utilisateur en affichant si une solution existe étant données les cases qu'il a déjà remplies (utiliser la fonction test_solutions définie dans le fichier testeur.cpp fourni)
• Génération aléatoire d'une grille initiale, en s'assurant que celle-ci admet une unique solution. A vous de trouver une méthode; vous pouvez utiliser la fonction test_solutions définie dans le fichier testeur.cpp fourni.

Pour réaliser ce projet, vous devrez partir des fichiers donnés ici.

• modele.h : un fichier complet de déclarations (mais vous pouvez en ajouter) :
  • la structure modele_t
  • déclaration des accesseurs et des fonctions de jeu (initialiser la grille, inscrire un chiffre)
• modele.c : un fichier à compléter. Au final, il devra au minimum contenir toutes les définitions des fonctions déclarées dans modele.h.
• ctr.h : fichier complet du contrôleur
• ctr.c : fichier de base du contrôleur. Vous pouvez le modifier librement. Contient la fonction principale du jeu (main).
• vue.h et vue.c : fichiers presque vides
• predef.h : un fichier d'entête déclarant la fonction predef_get_exemple, qui permet de récupérer une grille initiale parmi 18 grilles prédéfinies.
• predef.cpp : un fichier contenant les 18 grilles prédéfinies, ainsi que la définition de la fonction predef_get_exemple. Vous pouvez ajouter de nouvelles grilles dans ce fichier.
• testeur.h : un fichier d'entête déclarant la fonction test_solutions qui permet de tester si une grille initiale admet 0, 1 ou plusieurs solutions.
• testeur.cpp : un fichier contenant la définition de la fonction test_solutions. Vous ne devez pas modifier ce fichier.
• Un fichier Makefile permettant de compiler le projet. Pour utiliser la fonction test_solutions définie dans le fichier testeur.cpp fourni, il faut compiler avec la commande :

  make gecode
  

  Si vous n'utilisez pas cette fonction, il suffit de taper la commande :

  make
  

  Pour pouvoir utiliser la fonction test_solutions, il faut que la bibliothèque Gecode version 3.7.3 soit installée sur la machine. C'est en principe le cas sur les systèmes Linux de l'institut Galilée. Sinon, signalez-le à l'auteur de cette page pour qu'il s'occupe de l'installer ! Il existe des paquets de cette librairie pour plusieurs distributions de Linux. Sous Debian Wheezy, par exemple, vous pouvez l'installer facilement sur votre machine personnelle avec la commande :

  sudo apt-get install libgecode-dev
  

  La page de Gecode est ici.