I. Le sujet de ce cinquième défi

Le défi nous est lancé par Félix Guillemot. Il s'agit de réaliser un solveur de grilles de Sudoku.

Merci à Félix Guillemot de nous avoir proposé ce défi !

I-A. Le Sudoku

Est-il encore nécessaire de présenter le Sudoku ?

Le jeu se déroule sur une grille de 9x9, elle-même divisée en 9 sous-grilles de 3x3.

Le but est de remplir la grille avec des nombres de 1 à 9, tout en respectant les contraintes suivantes :

  • chaque nombre doit figurer une et une seule fois par ligne ;
  • chaque nombre doit figurer une et une seule fois par colonne ;
  • chaque nombre doit figurer une et une seule fois par sous-grille.

I-B. Prérequis

Pour réaliser ce défi, une simple édition personnelle de Delphi suffit. Pas besoin d'avoir les bibliothèques spécifiques aux versions Pro/Entreprise/Architecte !

Certaines versions personnelles de DELPHI sont disponibles au téléchargement sur Developpez.com.

Il peut être nécessaire de savoir farfouiller dans la rubrique DELPHI et plus particulièrement dans :

I-C. Les objectifs du défi

Votre solution devra offrir les fonctionnalités suivantes :

  • une IHM qui montre la grille de Sudoku et qui permet à l'utilisateur de saisir les chiffres de départ ;
  • un élément de l'interface (bouton, menu item…) qui permet de déclencher la résolution de la grille.

Après la résolution, la solution doit évidemment s'afficher dans la grille.

De plus, afin de faciliter les tests, votre solution devra permettre de charger une grille pré-définie à partir d'un fichier texte.

Le fichier aura le format suivant :

 
Sélectionnez
090871340
410903080
386245910
048090100
601500498
950184000
509030071
074600030
820019654 
  • une ligne pour chaque ligne de la grille (donc 9 lignes en tout) ;
  • les chiffres des colonnes collés les uns aux autres, avec des 0 pour les cases vides.

Pour info, en cherchant un peu, vous trouverez AI Escargot, la grille annoncée comme la plus difficile à résoudre au monde : elle a été fabriquée par Arto Inkala, un mathématicien finlandais, et fut un chantier de trois mois de modélisation à l'aide d'un ordinateur et l'examen de trois milliards de possibilités.

Et bien sûr, le défi ne consiste pas à résoudre AI Escargot, c'est juste un point de repère, une référence. Il faut commencer par des plus simples et résoudre. AI Escargot n'est pas le seul but à atteindre, ce n'est pas LE défi à relever, un challenge tout au plus.

Les participants doivent respecter les règles du défi, et le déroulement du défi et plus précisément que « l'utilisation de composantes ou bibliothèques autres que celles fournies en standard par Embarcadero sont interdites, qu'elles soient commerciales, freewares, open-source, etc. »

I-D. La notation

Les critères déterminants pour le jury qui devra désigner le meilleur "Sudoku Solver" sont les suivants :

  • performance du Solver : temps mis pour résoudre une grille, capacité à résoudre les grilles dites « difficiles » (pensez à prévoir un chronomètre) ;
  • ergonomie et présentation de l'interface ;
  • propreté du code : documentation (commentaires), indentation, modularité, enfin bref : on enlève les moufles ;
  • fonctionnalités originales et/ou pertinentes (laissez libre cours à votre imagination et soyez créatifs !).

II. La solution du défieur

Selon les règles du défi, Félix Guillemot a mis au point une solution pour son défi.

Image non disponible

Téléchargez la solution de Félix Guillemot : Télécharger

Félix nous présente sa solution ici : http://www.flx.fr/methodologie/livresblancs/

III. Les résultats

III-A. Le vainqueur

Tout d'abord, l'équipe tient à féliciter tous les participants et également Félix Guillemot pour avoir proposé ce défi.

Le vainqueur du défi est Andnotor.

Image non disponible

Il a réussi à développer une solution originale, parmi les plus performantes. Mais également très bien écrite.

Un grand Bravo à Andnotor !

III-B. La notation

La notation a été effectuée autour de quatre grands axes :

  • I. Respect du cahier des charges, Ergonomie, absence de bugs… : 5 points ;
  • II. Qualité du code, lisibilité, élégance… :5 points ;
  • III. Efficacité et performances : 7 points ;
  • IV. Fonctionnalités supplémentaires hors cahier des charges : 3 Points.

Chaque axe a été noté dans le but de classer les solutions des différents candidats les unes par rapport aux autres. C'est pourquoi les notes peuvent être très étalées. Il ne s'agit en aucun cas d'un jugement de valeur sur chaque solution, mais uniquement d'un classement.

III-B-1. Notation des performances

Comme annoncé au début du défi, une importance particulière a été accordée à l'optimisation du solveur et à ses performances. L'évaluation des performances a été réalisée de la façon suivante :

Les solutions de chaque candidat ont été testées une à une sur sept grilles de test.

Grille Description
Grille 1 Une grille facile
Grille 2 La grille de l'énoncé (triviale, mais avec plusieurs solutions)
Grille 3 Une autre grille facile
Grille 4 AI Escargot
Grille 5 Easter monster
Grille 6 Une grille de difficulté moyenne
Grille 7 La grille n°42185 de Gordon-Royle (choisie au hasard)

Un temps de résolution moyen a ainsi été déterminé pour chaque solution. Ce temps de résolution a permis de classer chaque solution d'après ses performances.

Enfin, chaque participation s'est vu attribuer un certain nombre de points (de 7 à 0) en fonction de sa position dans le classement.

Les résultats des mesures ont été les suivants (tous les temps indiqués sont en millisecondes) :

Participant Grille 1 Grille 2 Grille 3 Grille 4 Grille 5 Grille 6 Grille 7 Tps moyen
Andnotor 0.1183 0.0049 0.0104 1.0100 26.8400 0.1359 77.6500 15.1100
mick605 0.0822 0.0464 0.0514 1.3300 6.1600 0.1006 0.3256 1.1600
OutOfRange 0.6890 0.7770 0.2720 28.7270 49.8500 0.5860 4.0680 12.1400
Pascal Fonteneau 104.1235 N.A. 0.8333 189.4838 1499.4812 270.6402 11272.4832 2222.8400
anapurna 5.8911 5.7372 5.6741 63.2458 781.6023 5.7648 6.1707 124.8700
dpiquee 26.8516 6.1116 7.3332 43.0810 94.0026 20.8679 508.8882 101.0200
pepito88 7.8489 2.3579 2.3937 156.5471 968,0290 4.4491 6907.0051 1149.8000
bahmani 11.7907 0.1985 2.8757 65.7301 2479.3633 3.5301 19999.6451 3223.3000
Félix Guillemot 0.2400 0.2066 0.1575 27.1104 25.3926 0.2254 1.0492 7.7700
Franck SORIANO 0.0207 0.0096 0.0123 0.0177 0.1494 0.0196 2.1245 0.3400
ShaiLeTroll 0.1340 0.0710 0.0930 1.9690 56.6580 0.1220 0.1560 8.4576

III-C. Les participants

Participant I II III IV Total Classement Les sources de la solution
Andnotor 4.0 5.0 5.0 3.0 17.0 1 Image non disponible
mick605 3.5 3.5 7.0 2.0 16.0 2 Image non disponible
OutOfRange 4.0 3.5 6.0 0.5 14.0 3 Image non disponible
Pascal Fonteneau 4.0 3.5 1.0 3.0 11.5 4 Image non disponible
anapurna 2.5 3.5 3.0 2.0 11.0 5 Image non disponible
dpiquee 3.5 1.0 4.0 1.5 10.0 6 Image non disponible
pepito88 3.5 2.5 2.0 0.5 8.5 7 Image non disponible
bahmani 4.5 1.5 0.0 1.5 7.5 8 Image non disponible
Franck SORIANO H.C. H.C. H.C. H.C. H.C. Hors Concours Image non disponible
ShaiLeTroll H.C. H.C. H.C. H.C. H.C. Hors Concours Image non disponible

Le descriptif complet de la solution de Franck SORIANO.