[Défi n° 2] Un résolveur de grilles de Sudoku : les résultats !

**darrylsite** · 26/08/2009, 18h56

Envoyé par FullSpeed

Pour la vitesse j'ai une certaine experience. Darryl
si tu veux je peux t'aider: calcul des possibles pour chaque case par exemple...
Jérôme
Jerome

J'accepte volontier. je suis actuellement entrain de rechercher d'eventuel bug dans mon programme qui contient dejà environ 9 unités

apres quoi je te ferai signe.

Pour ce qui de la conversion delphi vers lazarus, dans le menu Outils de lazarus, il y a plusieurs options concernant la conversion des unites, projets, paquets delphi vers lazarus.

**FullSpeed** · 26/08/2009, 20h03

Surtout
tu n'hesite pas et c'est sur pas besoin dASM

jojpa54 je te rassures moi il n'y a pas des grilles que je n'arrive pas a finir: j'en ai jamais fini une!
Par contre des solveurs j'en ai ecris...

Si tu veux des pistes avant de demarrer...
Jerome

**mick605** · 27/08/2009, 01h12

Meeuuhhh non, le Topic sur le Forum Delphi est pas tourné compet' !! C'est juste que c'est interdit (et c'est logique) de donner du code !

jojpa54 > Pour te prouver que l'asm ne fait pas tout : Mon code ne contient pas une seule ligne d'asm, je n'ai pas un niveau tres élevé en programmation (je viens juste d'apprendre sur les pointeurs), et pourtant, mon solveur LOGIQUE résoud 5000 grilles tres difficiles a la seconde (10 000 pour des faciles). Il ne les résoud pas toutes, mais en faisant un solveur BruteForce, tu pourras toutes les résoudres tres facilement

(le temps par contre est a optimiser). La comparaison avec la résolution a la main n'est pas tres juste : La tu vois la difficulté d'un solveur logique, pas bruteforce. Donc je te conseilles de te lancer !!!

Envoyé par FullSpeed

Il n'existe pas de méthode dite logique qui permettent de résoudre TOUTES les grilles

ah ca ... on sait pas encore !

darrylsite > 9 unités ? He ben ! Ca en fait du code (je suis a 4 unités dont 2 tres petites

)

Pourriez vous dire quelle solution vous preferez et/ou vous utilisez dans vos solveur (BruteForce ou Logique, aux sens larges des termes) ?

**FullSpeed** · 27/08/2009, 13h48

J'ai converti mon projet et mes sources en Lazarus
Par contre j'obtiens un mystérieux message
Mais j'ai vu apparaitre un message disant que pour les debutants il fallait mettre une application Lazarus dans le dossier projet.

Et je la prends où?
J'ai le meme message quand j'essaye de construire les samples
Merci pour l'info ASM Mac
A ce sujet la syntaxe est la meme en D qu'avec Lazarus?
Jerôme

**darrylsite** · 27/08/2009, 13h52

Envoyé par mick605

darrylsite > 9 unités ? He ben ! Ca en fait du code (je suis a 4 unités dont 2 tres petites

)

Pourriez vous dire quelle solution vous preferez et/ou vous utilisez dans vos solveur (BruteForce ou Logique, aux sens larges des termes) ?

ouais ça fait deja beaucoup

. Le truc c'est que je suis un adepte de la programmation orientée objet, alors je modelise tout avec des classes. En plus je prefere separer systematiquement la vue des donnees et du traitement c'est ce qui fait croitre le nombre de lignes de code de mon projet. Bien que je crois que la poo reduit la vitesse de calcul, du moment ou on doit compter le temps de creation/destruction des objets, appel multiple de methodes,...

Je prefere le solveur logique. Le but de ma participation est d'abord de m'amuser en apprenant un max de truc. Alors faire un solveur force brute me parait pas tres compliqué : Je pense que je suis de ceux qui aime dire "pourquoi faire simple si on peut faire compliqué"

Vu que j'ai encore le temps, je crois que je vais peut etre combiner les deux selon le schema:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
 
 if not canSolveWithLogic() then
 solveWithForceBrut();

**mick605** · 27/08/2009, 14h26

Envoyé par darrylsite

Je prefere le solveur logique. Le but de ma participation est d'abord de m'amuser en apprenant un max de truc. Alors faire un solveur force brute me parait pas tres compliqué : Je pense que je suis de ceux qui aime dire "pourquoi faire simple si on peut faire compliqué"

Vu que j'ai encore le temps, je crois que je vais peut etre combiner les deux selon le schema:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
 
 if not canSolveWithLogic() then
 solveWithForceBrut();

+1 ! Je suis tout a fait d'accord !
Bon donc comme tu fais dans la logique, pourrais tu me dire quelles sont les méthodes de résolution que tu as déja codées ?
Moi j'ai codé :
Candidat unique
Emplacement unique
Candidats doubles, triples, quadruples ...
Paires, triplets, quadruplets, etc. cachés
Interaction

(cette question s'applique a toutes les personnes qui tentent un solveur logique

)

Aurais tu des chronos aussi ?

**FullSpeed** · 27/08/2009, 15h34

Mick
Quand je dis qu'il n'existe pas de soldeurs universel cela ne veut pas dire qu'ilk n'en existera pas un demain. Mais aujourd'hui il n'y en a pas et il y a quand meme quelques cerveaux qui se penchent dessus (hormis les nôtres)

Mon solveur Brute force est loin de faire des milliers de grilles a le seconde je reste toujours stupéfait..

Jerome

**darrylsite** · 27/08/2009, 15h36

Envoyé par mick605

+1 ! Je suis tout a fait d'accord !
Bon donc comme tu fais dans la logique, pourrais tu me dire quelles sont les méthodes de résolution que tu as déja codées ?
Moi j'ai codé :
Candidat unique
Emplacement unique
Candidats doubles, triples, quadruples ...
Paires, triplets, quadruplets, etc. cachés
Interaction

(cette question s'applique a toutes les personnes qui tentent un solveur logique

)

Aurais tu des chronos aussi ?

J'ai deja codé toutes tes methodes

, mais j'ai aussi ma boite secrete qui contiennent des methodes de resolutions que j'ai moi meme developpé. Mais les methodes x-swing, formations en etoiles,... je n'y ai pas encore touché. Il y a quelques erreurs dans mon programmes actuelles que je traque encore, apres je vais essayer de coder ces methodes.

Je n'ai pas encore mis de chronos. A vrai dire je ne suis pas un pro de lazarus, je ne sais meme pas encore comment il faut le faire. Comme quoi, nous sommes tous des debutants

Participes tu aussi au defi avec lazarus?

**mick605** · 27/08/2009, 20h39

Envoyé par darrylsite

J'ai deja codé toutes tes methodes

, mais j'ai aussi ma boite secrete qui contiennent des methodes de resolutions que j'ai moi meme developpé. Mais les methodes x-swing, formations en etoiles,... je n'y ai pas encore touché. Il y a quelques erreurs dans mon programmes actuelles que je traque encore, apres je vais essayer de coder ces methodes.

Bah ca va alors. Moi je suis sur le solveur BruteForce. Va sur le forum Delphi, vers les dernieres pages, tu trouvera plusieurs grilles (7 pour etre précis). Peut tu me dire quelles grilles tu arrive a résoudre (par la logique de ton solveur) ?

Envoyé par darrylsite

Je n'ai pas encore mis de chronos. A vrai dire je ne suis pas un pro de lazarus, je ne sais meme pas encore comment il faut le faire. Comme quoi, nous sommes tous des debutants

Participes tu aussi au defi avec lazarus?

Non, je n'y participe pas

Je viens sur le forum juste pour parler du défi

Edit : FullSpeed > Mon solveur brute force tout moche et pas optimisé pour un sou, bien qu'il contienne un gros bug, arrive a résoudre une grille en 890 µs

Je te conseille d'utiliser PRO Delphi pour voir ou tu perds du temps

**jojpa54** · 27/08/2009, 21h24

Envoyé par mick605

Non, je n'y participe pas

Je viens sur le forum juste pour parler du défi

Dommage ...

**darrylsite** · 27/08/2009, 22h39

Envoyé par mick605

Bah ca va alors. Moi je suis sur le solveur BruteForce. Va sur le forum Delphi, vers les dernieres pages, tu trouvera plusieurs grilles (7 pour etre précis). Peut tu me dire quelles grilles tu arrive a résoudre (par la logique de ton solveur) ?

J'arrive à resoudre les grilles suivantes : grille 1- grille 2- grille 6- grille 7.
je vois que j'ai encore du boulot

Arrives tu avec ta logique a toutes les resoudre?

**mick605** · 27/08/2009, 23h31

Si j'y arrivais, mais je me ferais du pognon la dessus !
Parce que la grille 4 est AI Escargot, la grille la plus difficile du monde !
Et la 5 est Easter Monster, une grille treeeees dure, peut etre plus que AIE !
Mais par contre la 3 est juste une grille diabolique trouvée sur un site !!
C'est en fait celle la que j'aurais aimé savoir si tu la résolvais...

Tiens, si ca t'interresse, retourne sur le Forum Delphi, je viens de poster un message avec des chronos détaillés !

Envoyé par jojpa54

Dommage ...

Je ne participe par parce que je programme seulement en Delphi

. Ce n'est pas pour autre chose ...
Et toi tu y participes alors ??

**jojpa54** · 28/08/2009, 08h20

Bonjour

Envoyé par mick605

Je ne participe par parce que je programme seulement en Delphi

. Ce n'est pas pour autre chose ...
Et toi tu y participes alors ??

Derrière Delphi il y a Pascal et derrière Lazarus il y FreePascal. Donc je pense que ça ne doit pas etre trop dur de transposer de Delphi vers Lazarus.

Participer moi ? .... Heu je ne sais pas encore, j'ai déja du mal à faire l'algo du jeu de morpion... mais j'y réfléchis quand même histoire de dire.. Je serais sans doute très près du zéro mais ça ne serait pas un drame.

**darrylsite** · 28/08/2009, 14h55

Envoyé par mick605

Si j'y arrivais, mais je me ferais du pognon la dessus !
Parce que la grille 4 est AI Escargot, la grille la plus difficile du monde !
Et la 5 est Easter Monster, une grille treeeees dure, peut etre plus que AIE !
Mais par contre la 3 est juste une grille diabolique trouvée sur un site !!
C'est en fait celle la que j'aurais aimé savoir si tu la résolvais...

Je viens d'ajouter un niveau d'intelligence a mon solveur et il a pulveriser la grille 3. Il ne reste que le IAE et le ester Monster.
Je sais integrer le chrono a mon solveur, et je t'en ferai part.

Envoyé par jojpa54

Participer moi ? .... Heu je ne sais pas encore, j'ai déja du mal à faire l'algo du jeu de morpion... mais j'y réfléchis quand même histoire de dire.. Je serais sans doute très près du zéro mais ça ne serait pas un drame.

Voici un lien qui te donnera plien de details sur la resolution logique :
http://vincent.planete.org/sudoku/
Sinon, pour ce qui est de lazarus, tu peux faire ton programme pascal traditionnel, ensuite une fois au point tu peux le tranferer vers lazarus qui n'interviendra que pour l'interface, et quelques petits trucs.

**mick605** · 28/08/2009, 19h59

Envoyé par darrylsite

Je viens d'ajouter un niveau d'intelligence a mon solveur et il a pulveriser la grille 3. Il ne reste que le IAE et le ester Monster.
Je sais integrer le chrono a mon solveur, et je t'en ferai part.

Bravo ! J'espere juste que ce n'est pas la pose d'hypothese ce fameux niveau d'intelligence

Le lien que tu as donné, c'est marrant, parce que c'est la dessus que je prends mes techniques

... Le "niveau d'intelligence" fait il partit d'une de ces techniques ?

**darrylsite** · 02/09/2009, 02h27

j'ai finalement opté pour une version logique-force brute qui offre la possibilité de résoudre les grilles les plus difficiles avec un chrono résonable. j'ai de meilleurs chronos pour les grilles 4 et 5. je posterai les chronos une fois le code optimisé.

**mick605** · 02/09/2009, 21h06

Alors, cette optimisation, ca avance ??

**Alcatîz** · 15/10/2009, 17h50

Le premier candidat à nous envoyer un projet complet est Le Seynois.

**dimanche2003** · 16/10/2009, 18h38

Merci de noter ma participation au défi !

Mon projet est bien avancé, solution presque instantanée des grilles les plus difficiles, mais il me reste quelques friandises à travailler, + l'aide, + ini,... le tout sous Delphi 2006/Windows ; je crains d'être pris par le temps (déplacements...).
A la rigueur, est-ce que je pourrais vous laisser le soin de tout basculer sur Lazarus, si ne n'ai pas eu le temps de le faire avant le 31 octobre...?

A moins que 15 jours supplémentaires soient envisageables ?