Fiche d'œuvre

Un certain 26/06/2008, une news site sur le Site du Zéro. Cette news annonce une grande nouvelle, les concours sont de retours, et ils sont en forme. Bon pour moi qui ne suis utilisateur du site du Zéro que depuis un an ce n'est donc pas un retour mais plutôt un nouveau module. Le premier concours est en C++ et sur le fameux jeu du sudoku ... génial ! J'étais justement en train de finir de lire le tutoriel sur le C++. Finalement je me dis que le concours est prévu pour que tout le monde puisse y arriver, je me lance donc dans la conception de la partie minimum pour participer au concours mais ne m'inscris pas au concours sans l'avoir au moins finie. Finalement en ce 31 juillet, dernier jour avant la fin du concours, je me retrouve ici à rendre un programme qui m'aura beaucoup aidé à évoluer. Et sûrement aussi aidé à mieux coder, mais attention. Je suis encore débutant en la matière. Je me rend bien compte qu'il y a bien mieux mais j'ai quand même apprécié cette expérience et je vais peut-être même produire d'autres versions du sudoku.

Voici quelques explication sur mon programme. Distribué sous GPL v3. Pour le lancer, il vous faudra faire qmake(-qt4) puis make et lancer le programme. Enjoy !

Le Programme

Zudoku est en ce moment dans sa version 1.3. Honnêtement à chaque fois que j'ajoute quelque chose d'intéressant je rajoute 0.1 au numéro de version. Ce qui signifie que ce chiffre ne veut en faite rien dire. Trêve de bla-bla. Voici les fonctionnalitées, et informations importantes qui valent le coup de développer un peu ici.

Information concernant l'orthographe/grammaire/syntaxe

Concernant ce premier points, je souhaitais absolument m'excuser. Tout d'abord pour les accents, car ils sont absents à l'appel et ceci dû au faite qu'ils font tout simplement « buguer » mon programme. Ce n'est pas à proprement parler un bug puisque tout les scriptes marchent. Mais ils apparaissent d'une drôle de façon (sûrement un problème d'encodage), et j'ai également un autre problème liée aux accents dans code::blocks.
Je voulais également m'excuser s'il reste des fautes d'orthographe ou de grammaire ici ou dans le programme.

Chargement de grilles

Les grilles sont chargées à partir de fichiers *.txt . Il se passe en une ou deux étapes. Soit on vous demande juste le niveau, si vous avez demandé à charger la grille aléatoirement, sinon on vous demande également le numéro de la grille que vous voulez charger.

Vérification

Depuis la première version, je pense que c'est le script ayant le plus évolué. Au départ, je ne m'étais pas vraiment cassé la tête pour coder ce script. Et ceci a donner un script qui faisait pas moins de 6500 itérations. Car j'avais imbriqué une boucle de 81 itérations dans une deuxième boucle de 81 itérations afin de vérifier les cases une par une. Depuis je suis passé à 243 itérations maximum. Je pense donc que ce script a vraiment subi une grande évolution.

Le Principe de la Vérification

Pour la vérification, le principe est simple. On part du fait que la grille de sudoku n'est valide que si tout les cases sur les lignes, colonnes et blocs sont remplies différemment. Ainsi je me base dessus pour vérifier les lignes, puis les colonnes et enfin les blocs. D'origine on estime que la grille est valide au départ puis on la met invalide si l'on détecte une erreur.

Résolution

Là, on peut dire que le concours m'a fait évoluer. Car il m'a fait tester de nouvelles choses, et entre autres la conception d'algorithme. Une grande avancé. Et apparemment même si ce début aurait pu être mieux, je m'en sort pas trop mal. Mon algorithme est encore à améliorer car il ne résout que les grilles de niveau facile (niveaux 1 à 3 dans les cahiers). Question temps, il est plutôt efficace, si l'idée que je me fait d'un bon temps est bonne, car je ne l'ai pas chronométré.

Le Principe de la résolution

Ainsi le principe de la résolution est également simple. Chaque cases a 9 attributs de type bool qui représentent chacun la possibilité ou non que le chiffre soit présent dans la case. Ainsi on passe sur toute les cases plusieurs fois, on met à jour les possibilités, et si une case n'a plus qu'une possibilité, on la remplit. Voilà le principe de mon algorithme de résolution.

La grille

Cela fait maintenant un certain temps que vous jouez à Zudoku ? Vous souhaitez ajouter des grilles au programme car les 428 grilles de la bibliothèque ne vous suffisent pas ? Eh bien voici comment procéder.

Organisation de la grille

Voici l'organisation de la grille. Chacune des cases est située avec un abscisse, une ordonnée et un bloc. Ainsi, cela permet d'avoir toute les cases bien repérées sur la grille, ce qui permet d'éviter beaucoup de lignes de codes.
Maintenant que vous savez comment est organisée la grille, nous pouvons voir comment ajouter des grilles.

Ajouter des grilles

Pour ajouter des grilles, rendez-vous dans le dossier du programme puis dans le dossier grilles. Vous y trouverez 4 fichiers. Le premier se nomme bibliothèque, il regroupe l'ensemble des grilles. Il y a également 3 autres fichiers qui sont classés par niveau de difficulté. Dans ces fichiers vous trouverez un certain nombre de lignes, chaque ligne représente une grille. Pour en ajouter une, voici comment lire votre grille:



Et ainsi, vous tapez les chiffre dans l'ordre où vous les lisez, si la case est vide d'origine, entrer le 0. Si vous utilisez la première méthode de lecture, votre grille sera exactement comme sur le papier, cependant si vous utilisez la seconde méthode, votre grille sera toujours tout aussi valide. Ce sera juste une rotation autour de la diagonale partant du coin en haut à gauche vers le coin en bas à droite.

Conclusion

En conclusion je pourrais dire que ce concours m'a procuré beaucoup de plaisir, et que je pense ressayer au prochain concours s'il y en a un ? J'espère que tous les autres concurrents ont pris autant de plaisir que moi. Pour finir voici deux screens, le premier provient de la version 1.0 et le second de la dernière version en date, la 1.3.



Secret (cliquez pour afficher)

L'archive est correctement organisée, mis à part la présence d'un fichier .cbp (code::blocks) qui n'était pas demandé. Mais passons.

Côté code

C'est globalement du bon travail. Le code est propre : correctement commenté (juste ce qu'il faut) et bien indenté.
Le tout semble s'efforcer de respecter des conventions, bien que ce ne soit pas toujours le cas mais rien de bien grave.

Les commentaires expliquent vraiment les réflexions que s'est fait le développeur, et ça c'est bien. Cependant, de nombreuses fautes d'orthographe réduisent parfois un peu la crédibilité des propos. Rien de bien grave, en fait on a vu pire. Mais c'est dommage quand même.

L'application est assez bien architecturée au niveau du code, la séparation des classes est convenable.
Globalement donc, sans être du travail de pro c'est du bon travail amateur et on sent comme le dit l'auteur qu'il y a eu de l'évolution dans la technique. Si ce concours a permis d'évoluer, tant mieux, c'était le but.

Côté application

La grille est facile à prendre en main, le GUI est correctement construit sans véritables fioritures.

Les menus sont un peu surprenants (notamment le menu Fichier qui ne contient que "Quitter"), l'application aurait gagnée à être un peu plus étudiée au niveau de son interface par endroits. D'ailleurs, certaines icônes (comme générer la grille aléatoirement) ne sont pas logique. Avec une disquette on s'attend à enregistrer. Ce n'est pas normal que le comportement soit différent. Il ne faut pas chercher à dévier des éléments de leur sens communément acquis sur une interface.

Autre erreur d'interface : le choix du niveau de difficulté lorsqu'on lance une nouvelle partie. C'est mignon de devoir écrire à la main au clavier "facile", "moyen", "difficile", mais ça ne sert pas le programme. Pour ce genre d'options on s'attend à avoir des boutons d'option, ou à la rigueur une liste déroulante. Ici rien de tout cela.

Voilà donc au final un certain nombre d'erreurs au niveau de l'interface qui aurait gagnée à être plus réfléchie. Notons que chez certains membres du jury le lancement d'une nouvelle partie semble ne pas avoir fonctionné, ce qui n'était pas le cas chez moi.


On peut générer aléatoirement une grille ou en choisir une dans un fichier. De nombreuses grilles prêtes à l'emploi sont livrées avec le logiciel.
La résolution des grilles est simple mais intelligente. Cependant, elle ne peut résoudre que des grilles de niveau facile ce qui est un peu frustrant. Le programme aurait dû implémenter une méthode un peu plus brutale (backtracking) à activer lorsque la méthode "fine" montre ses limites.

Du reste, la validation de la grille fonctionne bien mais on n'a pas d'aide à l'utilisateur, c'est un peu dommage.


Globalement donc du bon travail, mais il te reste à t'améliorer sur la conception de l'IHM (Interface Homme Machine) et à implémenter des algorithmes un peu plus poussés. Bon courage pour la suite !