Défi Pascal n° 2 : un résolveur de grilles de Sudoku
Avec Lazarus

Le , par Alcatîz, Responsable Pascal, Delphi et Assembleur
Bonjour à toutes et à tous,

L'équipe Delphi vient de lancer son 5ème défi : un résolveur de grilles de Sudoku.

L'équipe Pascal vous propose cette année de lancer un défi... à Delphi, en participant également à ce défi mais en allant encore plus loin grâce à l'atout majeur de Lazarus : la compilation multi-plateforme.

Le but du défi sera donc de réaliser un résolveur de grilles de Sudoku pouvant compiler indifféremment pour Linux et Windows, voire même d'autres plateformes.

Le défi est ouvert à tous les membres du forum (si vous n'êtes pas encore membre et souhaitez participer, enregistrez-vous gratuitement).

Eventuellement, pour ceux qui ne maîtriseraient pas les règles du jeu, les voici brièvement : la grille de Sudoku est un carré de neuf cases de côté, subdivisé en autant de sous-grilles carrées identiques, appelées régions. Chaque ligne, colonne et région ne doit contenir qu’une seule fois tous les chiffres de 1 à 9. Formulé autrement, chacun de ces ensembles doit contenir tous les chiffres de 1 à 9. Précision : une vraie grille de Sudoku ne possède qu'une et une seule solution.


(image provenant de Wikipedia)

Vous disposez d'un peu plus de quatre mois pour peaufiner votre programme, soit jusqu'au 31 décembre 2009.
La cotation prendra en compte tous les aspects : le respect du cahier des charges, le look du logiciel, l'originalité, mais aussi la qualité du code (élégance des solutions choisies, découpage en modules, choix des algorithmes, optimisation, etc), la qualité du source (indentation, choix des identificateurs, qualité des commentaires, etc).

Un classement sera réalisé sur base des cotations. Le vainqueur pourra faire partie du jury du défi suivant (sauf, bien sûr, s'il décide de concourir) !
Les sources des meilleurs candidats seront publiés dans la rubrique Sources.

Voici le règlement complet du défi :

Cahier des charges :
  • Réaliser un résolveur de grilles de Sudoku, qui charge une grille stockée dans un fichier ou composée par l'utilisateur, l'affiche et la résoud à la demande de l'utilisateur (et affiche bien entendu le résultat );
  • Compilable pour Windows et Linux au minimum;
  • Avec Lazarus;
  • Sans restriction de choix des composants.

Une grille stockée dans un fichier texte aura le format suivant :
Code : Sélectionner tout
1
2
3
4
5
6
7
8
9
160000009 
000008005 
007050600 
020903000 
009060400 
000504090 
004070900 
500800000 
900000063
(une ligne de la grille = une ligne du fichier, les 0 étant des cases vides).

Dates :

Les sources pourront être envoyés à Alcatîz jusqu'au 31-12-2009.
Au fur et à mesure de la réception des sources, la liste des participants sera mise à jour à la suite de ce message.
Surtout ne postez pas vos sources sur le forum.

Cotation :
  • Respect du cahier des charges : 5 points;
  • Qualité du code exécutable (principalement la performance du solveur : rapidité, capacité à résoudre des grilles difficiles) : 7 points;
  • Qualité du source : 4 points;
  • Look, ergonomie, originalité, créativité : 4 points.

Publication des résultats :

Dans le courant du mois de janvier 2010.

Bonne chance à tous les participants !

Liste des participants inscrits :

(dans l'ordre d'inscription)

darrylsite
Le Seynois
dimanche2003
Ludelphi7

Résultats :

Allez, faisons encore durer un peu le suspense le temps d'un clic de souris !
Les résultats sont ici : http://www.developpez.net/forums/m4934763-84/

Félicitations au vainqueur !


Vous avez aimé cette actualité ? Alors partagez-la avec vos amis en cliquant sur les boutons ci-dessous :


 Poster une réponse

Avatar de krachik krachik - Expert confirmé http://www.developpez.com
le 22/01/2010 à 17:40
Citation Envoyé par darrylsite  Voir le message
Salut,
je suis bien content du résultat. A vrai dire, je ne pensais pas pouvoir y arriver.

genre !!!!

aux participants, tous les projets sont
Avatar de darrylsite darrylsite - Rédacteur http://www.developpez.com
le 22/01/2010 à 18:01
Citation Envoyé par krachik  Voir le message
genre !!!!

Avatar de dimanche2003 dimanche2003 - Membre actif http://www.developpez.com
le 24/01/2010 à 17:41
Lors d’une compétition, plusieurs voitures dont une Rolls et une Deuche se sont présentées. Après délibération, le jury s’est prononcé et a accordé son prix à la Deuche… !!!
Explication : la Rolls n’a pas voulu démarrer…


Que notre ami Darrylsite ne se fâche pas (car il s’agit bien de lui, et j’ai eu l’occasion de le féliciter par ailleurs) mais enfin, son programme, s’il court comme un lapin, n’a pas plus de cervelle qu’un lièvre ! Il ne sait même pas distinguer un Sudoku d’une grille incomplète et fournit une solution en un clin d’œil sans vérifier qu’elle est unique…
Reconnaissons par ailleurs que les programmes de résolution de Sudoku sont plutôt nombreux sur le web, et il existe même un programme champion qui est écrit avec moins de 300 octets ! L’intérêt d’un nouveau programme, même en Lazarus, ne peut donc pas résider dans le seul objectif de trouver une solution, ce qui reviendrait à chercher la réinvention de l’eau tiède…
Bon, alors qu’apporte la Rolls de différent ? Elle permet –entre autres- de calculer pas à pas la solution, d’évaluer la difficulté de la grille (élémentaire, mon cher Watson), de présenter des statistiques comparées s’appuyant, au départ, sur plus de 400 grilles et… cerise sur le gâteau, de construire une grille nouvelle de la forme et du niveau de son choix, incluant une chaîne numérique de son choix…Et là, il s’agit d’une solution vraiment originale, totalement inédite à ma connaissance…
Tout ceci est présenté par un fichier d’aide très détaillé, sudo.chm, au format standard, disponible maintenant sur le site.
Ok, ok, j’entends déjà les voix qui me disent « c’est parfait, mais dommage que cette Rolls ne démarre pas ! ». Là, j’ai un problème : j’ai compilé et recompilé mon projet avant de l’envoyer, et cela sans la moindre erreur… sur mon poste. Et à l’arrivée, le projet ne compile plus ou mal ? What is wrong ?
Je suis trop néophyte pour comprendre et là, j’ai besoin d’aide. Qui est volontaire ?
Avatar de mick605 mick605 - Membre chevronné http://www.developpez.com
le 25/01/2010 à 2:54
Citation Envoyé par dimanche2003  Voir le message
Lors d’une compétition, plusieurs voitures dont une Rolls et une Deuche se sont présentées. Après délibération, le jury s’est prononcé et a accordé son prix à la Deuche… !!!
Explication : la Rolls n’a pas voulu démarrer…


Que notre ami Darrylsite ne se fâche pas (car il s’agit bien de lui, et j’ai eu l’occasion de le féliciter par ailleurs) mais enfin, son programme, s’il court comme un lapin, n’a pas plus de cervelle qu’un lièvre ! Il ne sait même pas distinguer un Sudoku d’une grille incomplète et fournit une solution en un clin d’œil sans vérifier qu’elle est unique…
Reconnaissons par ailleurs que les programmes de résolution de Sudoku sont plutôt nombreux sur le web, et il existe même un programme champion qui est écrit avec moins de 300 octets ! L’intérêt d’un nouveau programme, même en Lazarus, ne peut donc pas résider dans le seul objectif de trouver une solution, ce qui reviendrait à chercher la réinvention de l’eau tiède…
Bon, alors qu’apporte la Rolls de différent ? Elle permet –entre autres- de calculer pas à pas la solution, d’évaluer la difficulté de la grille (élémentaire, mon cher Watson), de présenter des statistiques comparées s’appuyant, au départ, sur plus de 400 grilles et… cerise sur le gâteau, de construire une grille nouvelle de la forme et du niveau de son choix, incluant une chaîne numérique de son choix…Et là, il s’agit d’une solution vraiment originale, totalement inédite à ma connaissance…
Tout ceci est présenté par un fichier d’aide très détaillé, sudo.chm, au format standard, disponible maintenant sur le site.
Ok, ok, j’entends déjà les voix qui me disent « c’est parfait, mais dommage que cette Rolls ne démarre pas ! ». Là, j’ai un problème : j’ai compilé et recompilé mon projet avant de l’envoyer, et cela sans la moindre erreur… sur mon poste. Et à l’arrivée, le projet ne compile plus ou mal ? What is wrong ?
Je suis trop néophyte pour comprendre et là, j’ai besoin d’aide. Qui est volontaire ?

Salut

Il me semble que tu oublies un point très important marqué dans le sujet :
Cotation :
Respect du cahier des charges : 5 points;
Qualité du code exécutable (principalement la performance du solveur : rapidité, capacité à résoudre des grilles difficiles) : 7 points;
Qualité du source : 4 points;
Look, ergonomie, originalité, créativité : 4 points.

D'apres ce que je vois, tu parles d'originalité et de créativité : c'est loin d'être le point le plus important du défi ... A ce que je vois, yaurait environ 3 points sur ce que tu cites. Et franchement, je suis sur que les correcteurs te les ont attribués (enfin, je sais pas si ils avaient aussi l'exe avec tes sources, mais si ils l'avaient, je pense que tu les aurait les points).

Mais bon, pour ce qui est de la qualité de source, et de l'efficacité du solveur, je pense que darryl se défend TRES bien. (Je suis en train d'étudier son source) Ensuite, niveau look et ergonomie, son solveur est plutot pas mal

Donc, dire que si ton projet compilait, il gagnerait, je pense que c'est vite avancé...

A part cela, j'aimerais justement obtenir ton exe, si tu pouvais nous le fournir, je te serais reconnaissant

Allez, a+

Mick605
Avatar de darrylsite darrylsite - Rédacteur http://www.developpez.com
le 25/01/2010 à 14:55
Salut,
Dimanche2003 >
C'est bien vrai que tu as été très créatif et ton projet est bien super. J'ai juste fait un survol rapide de ton projet. Mais bravo. Mais qui sait, t'aurais peut etre remporté ce defi. Je ne m'en fais pas trop pour ça. Pour moi, le but est atteint en participant à ce défi : m'amuser et apprendre à aimer Lazarus.

En fait, j'avais fini mon projet un ou deux mois apres le lancement de ce défi. Mon projet étais plutot volumineux avec beaucoup d'options que j'ai par la suite enlevées pour ne pas trop sortir du cahier de charge qui disait
* Réaliser un résolveur de grilles de Sudoku, qui charge une grille stockée dans un fichier ou composée par l'utilisateur, l'affiche et la résoud à la demande de l'utilisateur (et affiche bien entendu le résultat );

Sinon, mon projet complet permet de vraiment jouer au sodoku : generation de grille, proposition des solutions, aide à la resolution, debloquage des niveaux difficiles à mésure qu'on résoud les grilles faciles, ...

Mais si tu penses que tu aurais gagné si on avait bien corrigé, ou que si ton projet se compilait bien, alors tu as surement raison.

Mais, on m'a un jour dit que la deuxieme place est toujours la plus mauvaise. On se dit toujours que si ..., j'aurais gagné. Au premier défi, j'avais volontairement ralenti l'IA de l'ordinateur pour que le joueur humain ait l'impression que l'ordinateur réflechi. A la fin, j'ai été deuxieme, et je crois que c'est parce que mon mon IA étais un peu plus lent que les autres. Je me suis aussi dit que si j'avais ..., j'aurais bien pu gagné.
Avatar de dimanche2003 dimanche2003 - Membre actif http://www.developpez.com
le 25/01/2010 à 17:43
Pour Darrylsite.
Bravo pour cette réaction, encore bravo pour ton succès.
Il est vrai que, au plan esthétique, ta fenêtre a fière allure.
Tu nous dis que tu as bridé ton logiciel pour réussir, et je trouve cela… très regrettable !
Pour mon projet, il paraît que certains aient eu des problèmes de compilation. Il semble que cela se soit bien passé pour toi ?

Pour Mick605.
Qui conteste les règles du concours ?
J’ai simplement signalé que j’avais un problème, et que je sollicitais de l’aide… Tu souhaites mon programme exe, en voici deux : l’un compilé avec Lazarus, l’autre avec Delphi. Le second inclut l’aide sonore (tout à fait sommaire, j’en conviens, mais c’était plutôt un exercice de style…) alors que pour le premier, je n’ai pas trouvé de solution pour remplacer le mediaplayer. Il n’y a donc pas, au moment où j’ai déposé mon projet, d’aide sonore. Pour le reste, les différences sont minimes, comme tu pourras le constater.
Si ce blog ne me permet pas de transférer le zip (4,6 Mo), tu pourras le trouver ici.
http://www.adrive.com/public/8be6bde...f9de94239.html
Si tu as des difficultés pour charger de fichier, indique-moi un mail où je pourrai te l'envoyer...

Amicalement à tous.
Avatar de mick605 mick605 - Membre chevronné http://www.developpez.com
le 25/01/2010 à 18:10
Salut

En effet, tres bon logiciel, complet, rapide, peut être un tantinet complexe ...
Par contre, je sais pas si ca vient de moi, mais j'ai téléchargé les deux exe et les fichiers nécéssaires pour le bon fonctionnement, mais pour celui compilé avec Delphi, j'ai un beau :
Code : Sélectionner tout
1
2
3
4
5
6
7
--------------------------- 
SudoDelphi.exe - Composant introuvable 
--------------------------- 
Cette application n'a pas pu démarrer car rtl100.bpl est introuvable. La réinstallation de cette application peut corriger ce problème.  
--------------------------- 
OK    
---------------------------
Et sur Lazarus, j'ai régulièrement des "violations d'acces" et des "Out of bounds" Je sais pas si ca vient de mon ordi ou pas ... Parce que si tu dit que ca marches sur le tien ...

J'aimerais aussi tester ton outil de statistiques, mais toujours les messages d'erreurs ...

Enfin bref, voyons les autres membres, pour voir si ils ont les memes problemes que moi ...

En tout cas, mes félicitations !!

Mick605
Avatar de darrylsite darrylsite - Rédacteur http://www.developpez.com
le 25/01/2010 à 19:22
Citation Envoyé par dimanche2003  Voir le message
Pour Darrylsite.
Bravo pour cette réaction, encore bravo pour ton succès.
Il est vrai que, au plan esthétique, ta fenêtre a fière allure.
Tu nous dis que tu as bridé ton logiciel pour réussir, et je trouve cela… très regrettable !

C'est pas que j'ai bridé mon logiciel pour réussir. Seulement, j'ai essayé de comprendre ce qu'on demande à ma manière afin de donner un projet qui respecte ces exigences. Sinon, on a tous fait un choix d'une manière ou d'une autre. Rien ne prouve que si ton projet marchait bien tu aurais gagné. De toute façon, tout le mode peut dire que si ..., je ... Par exemple, j'ai enlevé les méthodes des chainagesX et autres. Mais qui sait si ça m'a pénalisé.
Code : Sélectionner tout
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
 
procedure TIASolver.xChain(); 
 var i, j, a, b, d : byte; 
     liste : TArraylist; 
     plat1, plat2 : TPlateau; 
     gp : TGroup; 
     solv : TIAsolver; 
begin 
 
 for a:=1 to 3 do 
  for b:=1 to 3 do 
   for d:=1 to 9 do 
    begin 
     if (not plateau.getGroup(a, b).countDigit(d)<>2) then 
      continue; 
      gp:=plateau.getGroup(a, b); 
     liste := TArraylist.init(); 
     for i:=1 to 3 do 
      for j:=1 to 3 do 
       if (gp.getCase(i, j).existPossibility(d)) then 
        liste.add(gp.getCase(i, j)); 
 
     plat1:=TPlateau.cloner(plateau); 
     plat2:=TPlateau.cloner(plateau); 
 
     plat1.getCase(liste.get(1).getX(), liste.get(1).getX()).setChoice(d); 
     plat2.getCase(liste.get(2).getX(), liste.get(2).getX()).setChoice(d); 
 
     solv:= TIAsolver.init(plat1); 
     solv.eleminatePossibility(liste.get(1).getX(), liste.get(1).getX(), d); 
     solv.fixOnePossibility(); 
     solv.searchOnePossibility(); 
 
     solv:= TIAsolver.init(plat2); 
     solv.eleminatePossibility(liste.get(1).getX(), liste.get(1).getX(), d); 
     solv.fixOnePossibility(); 
     solv.searchOnePossibility(); 
 
     for i:=1 to 9 do 
      for j:=1 to 9 do 
       if (not plateau.getCase(i, j).isChoosen) then 
        if (plateau.getCase(i, j).existPossibility(d)) then 
         if (not plat1.getCase(i, j).isChoosen()) then 
           if (not plat2.getCase(i, j).isChoosen()) then 
            if (not plat1.getCase(i, j).existPossibility(d)) then 
             if (not plat2.getCase(i, j).existPossibility(d)) then 
             begin 
              plateau.getCase(i, j).clearPossibility(d); 
            {  if (plateau.getCase(i, j).getPossibilitySize()=1) then 
               begin 
                plateau.getCase(i, j).setChoice(plateau.getCase(i, j).getPossibility(1)); 
                inc(devoile); 
                eleminatePossibility(i, j, plateau.getCase(i, j).getChoice()); 
               end; 
            } 
             end; 
    end; 
end;
Sinon, chez moi aussi, ton programme lance sans cesse des exceptions. Et même une grille chargée n'apparait pas sur l'écran, ...

Sinon, tu pourras peut être avoir mon projet complet sur mon site si jamais je me résous à le distribuer sur le net.
Avatar de dimanche2003 dimanche2003 - Membre actif http://www.developpez.com
le 31/01/2010 à 19:03
OK, je pense avoir trouvé l’origine des problèmes : l’instruction ExtractFilePath(Application.ExeName) qui servait à l’ouverture du fichier archives fonctionnait d’une façon inattendue ; les grilles d’archives ne se chargeaient pas, les listes de choix étaient vides, les statistiques et graphiques inutilisables…
En supprimant cette instruction, la création des forms se fait sans problème, et il semble que tout le reste fonctionne aussi.

Le reste : Darrylsite me signale qu’une grille semble ne pas se charger. Si c’est la grille n°1, c’est normal, elle ne compte que des zéros, qui s’affichent par des espaces dans la grille. Avec le classement automatique, cette grille se retrouve obligatoirement en première position. J’ai inversé le sens du tri, et la grille vide se retrouve maintenant en fin de liste…

Pour le reste encore, j’ai toujours un problème avec le mediaplayer, et le son reste inactif dans la version Lazarus. Si quelqu’un a une idée…

Ouala… Les courageux chargeront sources + exe en cliquant sur le lien suivant.
http://www.adrive.com/public/2528470...40d3d7a1e.html

Et merci d’avance pour vos observations, remarques, suggestions, critiques, etc…

Tout le monde peut progresser ! La preuve… !

Mick605 relève que mon exe sous Delphi exige un rtl (run time library) et me suggère de revoir les options de compilation. Hélas, j’ai beau inclure les librairies, mon exe reste toujours aussi maigrelet. Est-ce dû à ma version (Turbo Delphi 2006) ?
Avatar de darrylsite darrylsite - Rédacteur http://www.developpez.com
le 01/02/2010 à 22:16
Salut tous,

Les resultat du defi Delphi sont arrivés : ICI

le vainqueur a sorti une vraie merveille.
Avatar de gaetantri gaetantri - Nouveau Candidat au Club http://www.developpez.com
le 02/02/2010 à 13:49
En aillant vu ce défi un peu tardivement, j'ai pas eu le temps de défendre mes chances sur ce projet, mais en tout cas, je voulais dire que j'avais essayer de participer au défi, et que l'idée de coder un résolveur de Sudoku était pas mal.... vivement le 3e Défi !

Gaëtan
Offres d'emploi IT
Développeur Web Front
People Centric - Ile de France - Paris (75000)
Consultant SAP Logistique H/F
CSC - Ile de France - Paris la Défense
Développeur c#/wpf
Invenia Resourcing - Ile de France - Paris (75000)

Voir plus d'offres Voir la carte des offres IT
Responsables bénévoles de la rubrique Lazarus : Alcatîz - Gilles Vasseur -