Les Défis DELPHI - Le Sudoku Solver

Équipe Delphi

Le cinquième défi Delphi, proposé par Félix Guillemot, est la réalisation d'un Sudoku Solver !

Commentez

- Titre : Les Défis DELPHI - Le Sudoku Solver

- Auteur : Équipe Delphi

- Parution : 16 juin 2009

- Mise à jour : 27 avril 2013

- Public visé :

- Licence : Copyright ® 2009 Developpez LLC. Tous droits réservés Developpez LLC. Aucune reproduction, même partielle, ne peut être faite de ce site et de l'ensemble de son contenu : textes, documents et images sans l'autorisation expresse de Developpez LLC. Sinon vous encourez selon la loi jusqu'à trois ans de prison et jusqu'à 300 000 € de dommages et intérêts.

Sommaire

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

- I-A. Le Sudoku

- I-B. Prérequis

- I-C. Les objectifs du défi

- I-D. La notation

- II. La solution du défieur

- III. Les résultats

- III-A. Le vainqueur

- III-B. La notation

- III-B-1. Notation des performances

- III-C. Les participants

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élixGuillemot

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

Le descriptif complet de la solution de Franck SORIANO.