[Défi] Le Défi Delphi n°5 : Le Sudoku solver

[Franck SORIANO]

Bonjour,

L'équipe d'Animation vous propose son 5ème défi !

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 dans la page téléchargement de la rubrique DELPHI de www.developpez.com !

Il peut être nécessaire de savoir farfouiller sur le site de www.developpez.com dans la rubrique DELPHI et plus particulièrement dans la F.A.Q. DELPHI, dans les SOURCES DELPHI, dans les tutoriels DELPHI et dans les http://www.developpez.net/forums/forumdisplay.php?f=8.

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 s'afficher dans la grille, évidemmment

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

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 participant 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 CodeGear 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 court à votre imagination et soyez créatifs !)

EDIT 06/09/2009 :

ATTENTION :
Le défi se terminera le 30 septembre 2009 à minuit.

Vous avez donc jusqu'au 30 septembre minuit pour envoyer votre solution par mail à cette adresse.

N'oubliez pas d'indiquer votre pseudo Dvp dans le mail.

EDIT 01/02/2010 :

Les résultats du défi sont arrivés

Nous avons un vainqueur ! Il s'agit de Andnotor.



Toutes nos félicitations et un grand bravo au vainqueur, ainsi qu'à tous les participants.

Retrouvez l'intégralité des résultats, les solutions de chaque participants, et bien sûr celle du défieur !

[anapurna]

salut

Enfin un nouveau defi
bon la la date de fin n'est pas precisé ... on a l'eternité

@+ Phil

[mick605]

Je viens de m'inscrire récemment et je croyais que c'était fini les défis ! Mais non ! Trop bien !

Par contre, en ce moment, je suis occupé sur un programme, donc je ne participerai pas (a moins que je finisse bien avant la date de fin, s'il y en a une )

En tout cas, je suivrais l'avancement du défi ... Et je participerai surement au prochain défi !

Bonne chance a tout les participants !

[Franck SORIANO]

Envoyé par mick605

Je viens de m'inscrire récemment et je croyais que c'était fini les défis ! Mais non ! Trop bien !

Mais non

Tant qu'il y a des défieurs, il n'y a pas de raison d'arrêter !

Pour ce qui est de la date de fin, on n'a pas définit de date pour l'instant.
Elle sera fixée et communiquée ultérieurement, en fonction de l'avancement du défi et de la participation !

[edam]

salut tout le monde,
je suis pas sûr de participer à 100% mais j'ai commencé à fuiné voir ici

[Pascal Fonteneau]

Bonjour

Et un de plus, je releve le défi. J'espère que nous serons nombreux.
Pour ma part, j'ai deja un petit quelque chose de ma création. Il est toutefois necessaire de revoir le tout (sources,commentaires, et quelques parties a reprendre)

Voila

A+

Pascal

[anapurna]

salut

bon ,
moi j'en suis deja a ma version deux la premiere ne reussisant pas a touver la solution pour la grille proposer en exemple

apres quelque recherche je me suis orienté vers l'algorithme dlx
ou dancing links de Donald Knuth

il faut que je revise un peu mon code et que je fasse different essai
mais le gros du boulot est terminé

@+ Phil

[Franck SORIANO]

Envoyé par Pascal Fonteneau

Et un de plus, je releve le défi. J'espère que nous serons nombreux.
Pour ma part, j'ai deja un petit quelque chose de ma création. Il est toutefois necessaire de revoir le tout (sources,commentaires, et quelques parties a reprendre)

Tu pars donc avec de l'avance !

Bonne chance

[Franck SORIANO]

Envoyé par anapurna

moi j'en suis deja a ma version deux la premiere ne reussisant pas a touver la solution pour la grille proposer en exemple

hehe... faut dire aussi que cette grille possède plusieurs solutions !

Envoyé par anapurna

apres quelque recherche je me suis orienté vers l'algorithme dlx
ou dancing links de Donald Knuth

J'ai hâte de voir le résultat (et la vitesse de résolution)

[anapurna]

salut

les résultat son encourageant
47 pour le AI Escargot
différence entre deux gettikcount

vous auriez pas un chronos plus rapide
pour ton exemple il m'affiche 000000

@+ Phil

[FullSpeed]

Enfin un bon défi de vitesse .
On va pouvoir faire parler le silicone
J'ai moi aussi déjà travailler sur des solveurs: attention monsieur le rédacteur en chef!
au delà de ma participation au défi je serai content de faire profiter,
si cela les intéresse, d' autres participants de l'expérience acquise
Pour info un solveur Brute Force résout plusieurs dizaines de milliers de solutions a la seconde mais va mettre ,pour certains cas particuliers, plusieurs secondes
Si vous utilisez les dancings links et autres fish eyes les solveurs se bloquent sur des grilles comme la grille la plus dure du monde sans que vous puissiez le savoir

C'est un paramètre qu'il faut impérativement intégrer: la constance du temps de résolutions. Quelque soit la grille le temps doit être le mime car autrement vous aurez forcement des grilles bloquantes. La vitesse de pointe s'est bien mais on est aux 24 heures du Mans. Il faut jouer la durée.

Boris

Et souvenez vous: l'important c'est de gagnez pas de participer!
On ne se souviet que du vainqueur

Pour le chrometrage des soluces les tick sont insuffisant
Personnellement j'utilise des cycles du processeur

Cela fonctionne exactement comme le tickcount mais ne depends
pas de la fréquence. On n'obtient pas le même résultat a chaque fois(a cause des interruptions) mais la précision est supérieure

Code :

1
2
3
4
5
6
function GetCycleCount: Int64;
asm
  dw $310F  // opcode for RDTSC
end;
 i := GetCycleCount;
 Generew.Caption := IntTostr((GetCycleCount-i)div 1000000000);

[anapurna]

salut

j'aimerai avoir un exemple que le dancing-links ne serait pas capable de réaliser
si tu as une grille il suffit de l'afficher ici

merci pour le compteur
je vais regarder cela de plus pres


@+ Phil

PS je ne repond pas au message privée

[Franck SORIANO]

Envoyé par FullSpeed

C'est un paramètre qu'il faut impérativement intégrer: la constance du temps de résolutions. Quelque soit la grille le temps doit être le mime car autrement vous aurez forcement des grilles bloquantes. La vitesse de pointe s'est bien mais on est aux 24 heures du Mans. Il faut jouer la durée.

Tu peux détailler ? Je ne comprends pas trop ce que tu veux dire.

Personnellement j'utilise des cycles du processeur

Cela fonctionne exactement comme le tickcount mais ne depends
pas de la fréquence. On n'obtient pas le même résultat a chaque fois(a cause des interruptions) mais la précision est supérieure

Code :

Je savais qu'il existait celui là, mais c'est la première fois que je vois quelqu'un l'utiliser

Cependant, à en croire wikipedia ça ne semble pas très conseillé.

Sinon, il y a aussi les compteurs de performances (QueryPerformanceCounter) qui permettent de mesurer une durée avec une incertitude de 200 ns.

[Franck SORIANO]

Envoyé par anapurna

les résultat son encourageant
47 pour le AI Escargot
différence entre deux gettikcount

C'est un bon début ! mais sur quelle config ? Ca peut changer beaucoup de choses...

[anapurna]

salut

Envoyé par Franck SORIANO

C'est un bon début ! mais sur quelle config ? Ca peut changer beaucoup de choses...

XP service Pack 3

Intel Core2 Duo
2.6 Ghz
4 Go de RAM

@+ Phil

[FullSpeed]

Pour le chrono en realite il faut le diviser tres fort pour avoir une relative stabilité. C'est la methode utilmisépar lespecialistes de la vitesse

Anapurna excuse le MP mais comment recupere les versions des autres competiteurs?

Pour la constence des solveurs c'est assez simple a concevoir

imagine les grilles

000000000
000000000
000000000
000000000
000000000
...
123456789

et
123456789
000000000
000000000
000000000
000000000
....

Si ton solveur recherche la disposition 100x
0xx0
il trouvera dans la 2 pas dans la 1 il changera sa recherche pour 0xx0
100X
Si tu changes l'ordre de recherche tu iras plus vite pour la deuxieme recherche mais moins pour la premiere: il fait donc trouver des solutions moyennes et symétriques qui elles sont constantes

Pour des exemples j'ai quelques milliers de grilles au format text
si cela interresse quelqu'un?
Sur le net un Australien nomé GORDON publie lune liste aussi

Un petit coup de main pour ceux qui ne dorment pas: Il est toujours possible de trier les colonnes afin que la premiere rabngée soit
123456789 on peut se fixer cette contrainte afin de minimiser les candidats
Ensuite on peut trier les blocs de trois rangees
de telle maniere que les rangées ayant le plus de reveles soit en tete



5_______9 <== onionverse R1 et R2
_2_1___7_
__8___3__

_4_6_____<< R4 et r5 puis r5 et 6
____5____
___2_7_1_

__3___8__
_6___4_2_ <=== R7et R6 puis r8 etb R9
9_______5
On passe apres aux colonnes.

l'idee etant d'obtenir
123400000
456700000
789100000
312200000
000000000
000000000
Il est plus facile pour notre cerveau de travailler de gauche a droite et de bas enhaut que l'inverse
Bon sudoku à tous

[mick605]

Bon, finalement, trop tentant ... J'ai commencé.

Alors je vois toutes vos idées ... Mais personne n'essaye par la logique ? Meme si c'est plus lent, ca permet de voir plus de choses, genre les étapes ...

En plus, je pense que niveau programmation, c'est plus dur (enfin c'est mon avis, je sais pas si c'est le cas) que de passer toutes les grilles ...

Au fait, quand s'arrete le défi ? des la premiere solution fonctionnelle ? Ou a une date précise ?

Bon, sinon, bonne chance a tous !!

[FullSpeed]

mick65

si si j'ai des solveurs qui passe par la logique
hidden oppairs, quintet...
Lde probleme est que plus on avance plus les me-tpdes spnt compliquées e surtout on ne sait pas laquelle utiliser alors au niveau de la viotesse c'est catastrophique
M
mais il y a de la programmaation!!!
/////////////
47 pour le AI Escargot
différence entre deux gettikcount
//////////////////
Cela se lit comment? 47 tickcount pour resoudre ou eon resout 47 fois le temps d'un tick?
Merci de la precision

Boris

[FullSpeed]

En piece jointe quelques grilles....

Toutes les grilles ont 17 reveles
sont uniques (pas de rotation, permutations ou autrre)

La collection servait a mesurer les performances des solveurs
Combien de temps pour résoudre 35000 problèmes différents

Pour mesurer l'efficacité des solveurs on peut se servir des cases cachées
Si sur une geille de 81 cases il vous manque 60 cases on calcule le nombre de tests fait avant de positionner la bonne valeuir et on divise par 60
Bien sur moins de test par case => meilleure pertinance

[bahmani]

Bonne jour tour le monde

Je ne suis qu' un débutant amateur de développement,
C’est ma première contribution dans le forum, je viens de finir le codage de mon solver, je l’ai testé sur plusieurs grilles (il marche apparemment) sur ESCARGO-AI il m’affiche entre 16 et 78 Ms (ma méthode se base sur des générations des nombre aléatoires, ce qui explique le différence de temps de résolution à chaque fois)


Ma Config
XP-SP3
Core 2 Deo 1.83 GH
2 GM de RAM

Je ne sais pas, s’il faut envoyer mon solver (à qui ?) ou il faut déposer dans le forum ?


Merci