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 :
- la F.A.Q. DELPHI ;
- les Sources DELPHI ;
- les tutoriels DELPHI ;
- les forums DELPHI.
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 :
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.
| Téléchargez la solution de Félix Guillemot : |
|
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.
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 |
|
| mick605 | 3.5 | 3.5 | 7.0 | 2.0 | 16.0 | 2 |
|
| OutOfRange | 4.0 | 3.5 | 6.0 | 0.5 | 14.0 | 3 |
|
| Pascal Fonteneau | 4.0 | 3.5 | 1.0 | 3.0 | 11.5 | 4 |
|
| anapurna | 2.5 | 3.5 | 3.0 | 2.0 | 11.0 | 5 |
|
| dpiquee | 3.5 | 1.0 | 4.0 | 1.5 | 10.0 | 6 |
|
| pepito88 | 3.5 | 2.5 | 2.0 | 0.5 | 8.5 | 7 |
|
| bahmani | 4.5 | 1.5 | 0.0 | 1.5 | 7.5 | 8 |
|
| Franck SORIANO | H.C. | H.C. | H.C. | H.C. | H.C. | Hors Concours |
|
| ShaiLeTroll | H.C. | H.C. | H.C. | H.C. | H.C. | Hors Concours |
|