Publicité
+ Répondre à la discussion Actualité déjà publiée
Page 1 sur 26 1234511 ... DernièreDernière
Affichage des résultats 1 à 20 sur 506
  1. #1
    Expert Confirmé

    Profil pro Franck Soriano
    Leader Technique
    Inscrit en
    juin 2005
    Messages
    1 757
    Détails du profil
    Informations personnelles :
    Nom : Franck Soriano
    Âge : 36
    Localisation : France, Rhône (Rhône Alpes)

    Informations professionnelles :
    Activité : Leader Technique
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : juin 2005
    Messages : 1 757
    Points : 3 942
    Points
    3 942

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

    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 [ame="http://www.developpez.net/forums/forumdisplay.php?f=8"]forums DELPHI[/ame].

    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 !

  2. #2
    Membre Expert Avatar de anapurna
    Développeur informatique
    Inscrit en
    mai 2002
    Messages
    1 581
    Détails du profil
    Informations professionnelles :
    Activité : Développeur informatique

    Informations forums :
    Inscription : mai 2002
    Messages : 1 581
    Points : 1 987
    Points
    1 987

    Par défaut

    salut

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

    @+ Phil
    Nous souhaitons la vérité et nous trouvons qu'incertitude. [...]
    Nous sommes incapables de ne pas souhaiter la vérité et le bonheur, et sommes incapables ni de certitude ni de bonheur.
    Blaise Pascal
    PS : n'oubliez pas le tag

  3. #3
    Membre Expert

    Homme Profil pro
    Étudiant
    Inscrit en
    juin 2009
    Messages
    936
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 23
    Localisation : France, Aveyron (Midi Pyrénées)

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : juin 2009
    Messages : 936
    Points : 1 744
    Points
    1 744

    Par défaut

    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 !

  4. #4
    Expert Confirmé

    Profil pro Franck Soriano
    Leader Technique
    Inscrit en
    juin 2005
    Messages
    1 757
    Détails du profil
    Informations personnelles :
    Nom : Franck Soriano
    Âge : 36
    Localisation : France, Rhône (Rhône Alpes)

    Informations professionnelles :
    Activité : Leader Technique
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : juin 2005
    Messages : 1 757
    Points : 3 942
    Points
    3 942

    Par défaut

    Citation Envoyé par mick605 Voir le message
    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 !

  5. #5
    Membre Expert Avatar de edam
    Homme Profil pro said
    Développeur Delphi/c++/Omnis
    Inscrit en
    décembre 2003
    Messages
    1 813
    Détails du profil
    Informations personnelles :
    Nom : Homme said
    Localisation : Maroc

    Informations professionnelles :
    Activité : Développeur Delphi/c++/Omnis
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : décembre 2003
    Messages : 1 813
    Points : 2 384
    Points
    2 384

    Par défaut

    salut tout le monde,
    je suis pas sûr de participer à 100% mais j'ai commencé à fuiné voir ici
    PAS DE DESTIN, C'EST CE QUE NOUS FAISONS

  6. #6
    Membre confirmé
    Avatar de Pascal Fonteneau
    Profil pro
    Inscrit en
    février 2007
    Messages
    130
    Détails du profil
    Informations personnelles :
    Âge : 51
    Localisation : France, Var (Provence Alpes Côte d'Azur)

    Informations forums :
    Inscription : février 2007
    Messages : 130
    Points : 269
    Points
    269

    Par défaut Je releve de defi

    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

  7. #7
    Membre Expert Avatar de anapurna
    Développeur informatique
    Inscrit en
    mai 2002
    Messages
    1 581
    Détails du profil
    Informations professionnelles :
    Activité : Développeur informatique

    Informations forums :
    Inscription : mai 2002
    Messages : 1 581
    Points : 1 987
    Points
    1 987

    Par défaut

    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
    Nous souhaitons la vérité et nous trouvons qu'incertitude. [...]
    Nous sommes incapables de ne pas souhaiter la vérité et le bonheur, et sommes incapables ni de certitude ni de bonheur.
    Blaise Pascal
    PS : n'oubliez pas le tag

  8. #8
    Expert Confirmé

    Profil pro Franck Soriano
    Leader Technique
    Inscrit en
    juin 2005
    Messages
    1 757
    Détails du profil
    Informations personnelles :
    Nom : Franck Soriano
    Âge : 36
    Localisation : France, Rhône (Rhône Alpes)

    Informations professionnelles :
    Activité : Leader Technique
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : juin 2005
    Messages : 1 757
    Points : 3 942
    Points
    3 942

    Par défaut

    Citation Envoyé par Pascal Fonteneau Voir le message
    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

  9. #9
    Expert Confirmé

    Profil pro Franck Soriano
    Leader Technique
    Inscrit en
    juin 2005
    Messages
    1 757
    Détails du profil
    Informations personnelles :
    Nom : Franck Soriano
    Âge : 36
    Localisation : France, Rhône (Rhône Alpes)

    Informations professionnelles :
    Activité : Leader Technique
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : juin 2005
    Messages : 1 757
    Points : 3 942
    Points
    3 942

    Par défaut

    Citation Envoyé par anapurna Voir le message
    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 !

    Citation Envoyé par anapurna Voir le message
    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)

  10. #10
    Membre Expert Avatar de anapurna
    Développeur informatique
    Inscrit en
    mai 2002
    Messages
    1 581
    Détails du profil
    Informations professionnelles :
    Activité : Développeur informatique

    Informations forums :
    Inscription : mai 2002
    Messages : 1 581
    Points : 1 987
    Points
    1 987

    Par défaut

    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
    Nous souhaitons la vérité et nous trouvons qu'incertitude. [...]
    Nous sommes incapables de ne pas souhaiter la vérité et le bonheur, et sommes incapables ni de certitude ni de bonheur.
    Blaise Pascal
    PS : n'oubliez pas le tag

  11. #11
    Inactif
    Inscrit en
    mars 2009
    Messages
    182
    Détails du profil
    Informations forums :
    Inscription : mars 2009
    Messages : 182
    Points : 192
    Points
    192

    Par défaut Speed...

    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);

  12. #12
    Membre Expert Avatar de anapurna
    Développeur informatique
    Inscrit en
    mai 2002
    Messages
    1 581
    Détails du profil
    Informations professionnelles :
    Activité : Développeur informatique

    Informations forums :
    Inscription : mai 2002
    Messages : 1 581
    Points : 1 987
    Points
    1 987

    Par défaut

    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
    Nous souhaitons la vérité et nous trouvons qu'incertitude. [...]
    Nous sommes incapables de ne pas souhaiter la vérité et le bonheur, et sommes incapables ni de certitude ni de bonheur.
    Blaise Pascal
    PS : n'oubliez pas le tag

  13. #13
    Expert Confirmé

    Profil pro Franck Soriano
    Leader Technique
    Inscrit en
    juin 2005
    Messages
    1 757
    Détails du profil
    Informations personnelles :
    Nom : Franck Soriano
    Âge : 36
    Localisation : France, Rhône (Rhône Alpes)

    Informations professionnelles :
    Activité : Leader Technique
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : juin 2005
    Messages : 1 757
    Points : 3 942
    Points
    3 942

    Par défaut

    Citation Envoyé par FullSpeed Voir le message
    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 :
    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);
    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.

  14. #14
    Expert Confirmé

    Profil pro Franck Soriano
    Leader Technique
    Inscrit en
    juin 2005
    Messages
    1 757
    Détails du profil
    Informations personnelles :
    Nom : Franck Soriano
    Âge : 36
    Localisation : France, Rhône (Rhône Alpes)

    Informations professionnelles :
    Activité : Leader Technique
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : juin 2005
    Messages : 1 757
    Points : 3 942
    Points
    3 942

    Par défaut

    Citation Envoyé par anapurna Voir le message
    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...

  15. #15
    Membre Expert Avatar de anapurna
    Développeur informatique
    Inscrit en
    mai 2002
    Messages
    1 581
    Détails du profil
    Informations professionnelles :
    Activité : Développeur informatique

    Informations forums :
    Inscription : mai 2002
    Messages : 1 581
    Points : 1 987
    Points
    1 987

    Par défaut

    salut

    Citation Envoyé par Franck SORIANO Voir le message
    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
    Nous souhaitons la vérité et nous trouvons qu'incertitude. [...]
    Nous sommes incapables de ne pas souhaiter la vérité et le bonheur, et sommes incapables ni de certitude ni de bonheur.
    Blaise Pascal
    PS : n'oubliez pas le tag

  16. #16
    Inactif
    Inscrit en
    mars 2009
    Messages
    182
    Détails du profil
    Informations forums :
    Inscription : mars 2009
    Messages : 182
    Points : 192
    Points
    192

    Par défaut Sudoku

    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

  17. #17
    Membre Expert

    Homme Profil pro
    Étudiant
    Inscrit en
    juin 2009
    Messages
    936
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 23
    Localisation : France, Aveyron (Midi Pyrénées)

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : juin 2009
    Messages : 936
    Points : 1 744
    Points
    1 744

    Par défaut

    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 !!

  18. #18
    Inactif
    Inscrit en
    mars 2009
    Messages
    182
    Détails du profil
    Informations forums :
    Inscription : mars 2009
    Messages : 182
    Points : 192
    Points
    192

    Par défaut

    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

  19. #19
    Inactif
    Inscrit en
    mars 2009
    Messages
    182
    Détails du profil
    Informations forums :
    Inscription : mars 2009
    Messages : 182
    Points : 192
    Points
    192

    Par défaut Grilles de test

    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

  20. #20
    Invité de passage
    Inscrit en
    avril 2002
    Messages
    18
    Détails du profil
    Informations forums :
    Inscription : avril 2002
    Messages : 18
    Points : 1
    Points
    1

    Par défaut

    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

Liens sociaux

Règles de messages

  • Vous ne pouvez pas créer de nouvelles discussions
  • Vous ne pouvez pas envoyer des réponses
  • Vous ne pouvez pas envoyer des pièces jointes
  • Vous ne pouvez pas modifier vos messages
  •