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

Citation:

---

Envoyé par 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

---

hihi, j'aime bcp l'idée du nombre aléatoire :)

Citation:

---

Envoyé par bahmani

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

---

Si tu as une solution finale que tu souhaites soumettre au Jury, envoie un Zip avec les sources, l'exe compilé, et toutes les infos annexes que tu juges utiles à cette adresse (précise en particulier la version de Delphi utilisée pour compiler l'exe).

Si tu veux juste montrer ta solution aux autres candidats (attention, ils peuvent alors pomper des idées :mrgreen:) tu peux poster le zip de l'exe compilé ici. Rien rien ne t'inderdit ensuite d'améliorer encore ta solution...

Sans les sources bien évidemment. Tout post avec des sources sera supprimé à vue :zekill:

Citation:

---

Envoyé par FullSpeed

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

---

Là, je vois bien de quoi tu parles. Lorsque j'ai écrit ma solution, les temps de résolution de AI-Escargot variaient d'un facteur 1 à 10 selon l'ordre de recherche...

Citation:

---

En piece jointe quelques grilles....

---

Tu as dû oublier la pièce jointe.

Citation:

---

Sur le net un Australien nomé GORDON publie lune liste aussi

---

Oui, les grilles minimales de Gordon Royle sont très intéressantes pour tester l'efficacité d'un solveur.
Le problème c'est que son site n'a plus l'air de répondre :aie:

Citation:

---

Envoyé par 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!!!

---

C'est ca qui est bon ;) !!

Edit : 2 Messages dans la meme minute ;)

J'ai mis le fichier en piece jointe avec le boton dedie
je reassaye:
46 000 grilles de GORDON

En fairt la liste de Gordon c'et

Grilles exemple
Le fichier est trop gros meme zippe. Alors juste quelques unes au hasard
En fait la liste de Gordon avait pour but de regroupes toutes les grilles 17 révélés car on croyait leur nombre fini et pour essayer de faire un GENERATEUR de grilles 17. On sait que le nombre de grilles 17 est infini et on a pas trouve de méthode pour générer de pbs 17.

Pour les amateurs quelques grilles un peu dur

Citation:

---

6___4___3_1_____7___5___8_____5_2___3___9___2___1_3_____8___9___7_____5_2___3___4
9___4___2_1_____7___5___8_____5_2___6___8___9___1_4_____8___1___7_____5_2___3___4
9___4___2_1_____7___7___8_____5_2___6___8___9___1_3_____8___1___7_____5_2___3___4
9___4___3_1_____7___7___8_____5_2___6___8___9___1_3_____8___1___7_____5_2___3___4
9___4___6_1_____7___7___8_____5_2___6___8___9___1_3_____8___1___7_____5_2___3___4
4___8___6_8_____3___9___2_____5_3___7___2___8___8_9_____1___7___3_____9_5___6___4
7___2___4_5_____8___1___6_____3_7___1___6___9___5_8_____6___5___8_____4_9___4___1
9___2___1_8_____3___6___5_____3_5___8___6___9___1_8_____3___6___4_____5_1___7___8
2___8___6_1_____7___9___5_____9_5___3___1___7___2_3_____5___4___7_____9_8___4___3
6___3___4_7_____1___8___2_____3_5___3___2___6___1_8_____2___7___1_____8_4___9___5
4___1___8_5_____2___6___9_____9_2___8___5___3___1_8_____9___6___2_____5_1___7___4
7___2___5_3_____6___1___4_____3_6___6___1___9___4_7_____4___3___5_____1_9___7___8
3___5___1_4_____6___7___8_____9_4___2___8___3___1_6_____9___4___6_____2_5___1___7
3___4___2_1_____6___6___8_____1_9___6___8___3___6_4_____5___9___8_____1_4___2___6
1___4___2_5_____9___8___3_____5_9___7___8___3___7_6_____7___5___9_____4_6___2___1
9___7___4_1_____5___8___2_____8_9___7___4___6___2_7_____3___1___2_____8_6___9___7
3___6___5_2_____4___7___2_____6_7___9___8___6___9_1_____2___7___4_____1_6___5___9
4___1___9_2_____3___3___6_____1_6___5___9___4___2_8_____6___2___3_____8_9___2___1
6___7___9_1_____2___5___4_____1_2___9___8___6___6_9_____1___2___3_____4_7___5___8
7___8___2_5_____9___1___3_____7_9___4___6___7___4_5_____9___5___8_____1_2___3___8
3___4___6_2_____8___7___5_____8_2___6___9___7___7_6_____8___1___5_____2_4___3___9
6___4___3_1_____7___5___8_____5_2___3___9___2___1_3_____8___9___7_____5_2___3___4
6___5___9_5_____3___4___2_____4_3___2___9___8___2_6_____1___5___3_____4_8___7___6
1___7___6_5_____8___4___3_____1_5___2___8___1___6_3_____1___7___3_____5_6___1___9
3___9___7_2_____5___7___8_____3_4___1___6___3___7_2_____4___2___8_____4_9___3___1

---

C'est marrant, de relire Phidels ici ou là pour la chasse à la performance !

EDIT : Bon, ben 2h plus tard, j'ai fini ma 1ère version de Solver de Sudoku, avec un Algo archi pourri, qui me résoud des Grilles trouvées sur le Net pour 220µs, comme je suis une quiche en Sudoku, ben, j'ai des grilles ou ça fonctionne pas ! :mouarf:

Gentil petit troll je veux bien regarder ton problème si tu veux
Je ne te volerais pas tes idées promis

Dans une compète il faut travailler le moral de ses adversaires pour
les faire douter alors juste comme cela histoire que vous dormiez tous bien
si vous ne résolvez pas 1000 fois escargot en une seconde inscrivez
vous au défi de votre village... :D:D (1000 c'est pour rire en fait c'est.....)

Boris:ccool:

Citation:

---

Envoyé par FullSpeed

Gentil petit troll je veux bien regarder ton problème si tu veux
Je ne te volerais pas tes idées promis

Dans une compète il faut travailler le moral de ses adversaires pour
les faire douter alors juste comme cela histoire que vous dormiez tous bien
si vous ne résolvez pas 1000 fois escargot en une seconde inscrivez
vous au défi de votre village... :D:D (1000 c'est pour rire en fait c'est.....)

Boris:ccool:

---

:mrgreen:

Sinon, la j'ai continué le solveur par la logique et il marche alors qu'il devrait pas ! Enorme ! il me trouve des solutions justes avec des fausses hypotheses. Il arrive meme a résoudre des niveaux diaboliques ! (Pour vous ca vous change rien le niveau mais pour moi si !!)

Bon j'y retourne ! :mouarf:

Edit : Je viens de tester une de tes grilles FullSpeed : mon solveur la résoud plus rapidement que certaines grilles diaboliques !

Re Edit de malade :

Pour ceux qui savent pas, mon programme ecrit dans un mémo les étapes ...
J'avais des résultats du genre 70 ms ... je me dis, tient, essaye de ne pas afficher les étapes ... je teste .... 0 ms 8O 8O

Bon, c'est parti pour le TickCount !!!!!

Mick

Quand tu parles de solveur logique qu'entends tu exactement?
Pour moi un solveur logique est un solveur qui essaye des méthodes connues en cherchanr des configurations precises de case

Par exemple les orphelins: une case dnne contient obligatoirement telle valeur Si en ou cette valeur ne peut aller que dans cette case

Ce type de soldeur se bloque: aucune disposption connue alors il s'arrete
En plus la programmation d'un XY_Win demande beaucoupo de programation et de mise au point (good,good)
Si tu as brassé cela en 48 heurres bravo...

Il faut bannir des chronométrages tout ce qui est affichage; add dans un memo ou dans une liste, afichage d'un compteur dans un label, methode update, paint Il ne faut garder que le code de résolution
Je suis un peu surpris que personne (ou alors ils se taisent) ne soit tenterpar des Brute force; ils donnet d'execellents resultats.

Boris

Pour ma part, je vais tâcher d'exhumer un projet d'il y a qq années, mais j'ai peur de manquer de temps...

Il n'est ni abouti, ni propre, ni ne résoud toutes les grilles, ni mortellement rapide !

Je me focaliserai donc sur le reste.

Citation:

---

Envoyé par FullSpeed

Gentil petit troll je veux bien regarder ton problème si tu veux
Je ne te volerais pas tes idées promis

---

C'est gentil de ta part, mais cela ne serait plus un défi, si je ne trouve pas par moi même, donc aucun intérêt, en fait, je vais tenter un algo d'Heuristique une fois que l'algo de base a terminer sa résolution.

Citation:

---

Envoyé par FullSpeed

Mick

Quand tu parles de solveur logique qu'entends tu exactement?
Pour moi un solveur logique est un solveur qui essaye des méthodes connues en cherchanr des configurations precises de case

Par exemple les orphelins: une case dnne contient obligatoirement telle valeur Si en ou cette valeur ne peut aller que dans cette case

---

C'est le cas :ccool: ! Il teste exactement comme un humain les possibilités de la grille. POur l'instant, il sait :
- chercher si une case contient un seul candidat
- chercher si dans une ligne, colonne, ou bloc, il existe une seule valeur possible
- plusieurs autres techniques (Humaines) dont je me tairais sur ce point :ccool: !

Citation:

---

Envoyé par FullSpeed

Ce type de soldeur se bloque: aucune disposption connue alors il s'arrete

---

C'est pour ca qu'il faut coder le plus de techniques de résolutions, en commencant par la plus simple, en finissant par la plus compliquée ...
C'est comme un humain : il teste les techniques évidentes, si il ne trouve rien, il teste des techniques un peu plus dures... Ainsi de suite...

Citation:

---

Envoyé par FullSpeed

En plus la programmation d'un XY_Win demande beaucoupo de programation et de mise au point (good,good)
Si tu as brassé cela en 48 heurres bravo...

---

Ouais, niveau programmation, c'est du solide ;) ! Faut toujours avoir l'idée qui va accélerer la resolution ! Mais qu'est ce que tu entends par XY_Win ?

Citation:

---

Envoyé par FullSpeed

Il faut bannir des chronométrages tout ce qui est affichage; add dans un memo ou dans une liste, afichage d'un compteur dans un label, methode update, paint Il ne faut garder que le code de résolution

---

Ca m'énerve, je voulais justement afficher les étapes ! Je me demande si en mettant une checkbox, et des conditions pour afficher les messages, c'est plus long que de ne pas afficher de messages du tout ?

Citation:

---

Envoyé par FullSpeed

Je suis un peu surpris que personne (ou alors ils se taisent) ne soit tenterpar des Brute force; ils donnet d'execellents resultats.

---

Tiens, j'aurais dit le contraire ....

Citation:

---

Envoyé par FullSpeed

Boris

---

Mickael :mouarf:


Sinon, j'ai une question : Combien ya t-il de TickCounts dans une milliseconde ??

Citation:

---

Envoyé par mick605

Sinon, j'ai une question : Combien ya t-il de TickCounts dans une milliseconde ??

---

Grosso modo, tu as un tick toutes les 15 ms... Donc tu ne peux pas mesurer de durée inférieure à 30 ms de façon à peu près fiable avec GetTickCount.

Citation:

---

Envoyé par Franck SORIANO

Grosso modo, tu as un tick toutes les 15 ms... Donc tu ne peux pas mesurer de durée inférieure à 30 ms de façon à peu près fiable avec GetTickCount.

---

Si j'ai bien compris, mon solver met environ moins d'une milliseconde pour des grilles diaboliques, 12 ms avec affichage (j'ai une technique !!). Donc ca met moins d'un tickcount ?? a ouais quand meme !!

Existe-t-il des unités plus petites que la milliseconde ?

Citation:

---

Envoyé par mick605

Existe-t-il des unités plus petites que la milliseconde ?

---

Une réponse à cette question se trouve dans la première page de ce topic :roll:

Utilise QueryPerformanceCounter et QueryPerformanceFrequency, pour un tems plus précis à la millisecondes

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13

procedure GetBeginTime(var Value: Int64); begin QueryPerformanceCounter(Value); end;   function GetElapsedTime(var BeginTime: Int64): Cardinal; var EndTime, TickPerSec: Int64; begin QueryPerformanceCounter(EndTime); QueryPerformanceFrequency(TickPerSec); Result := Round((EndTime - BeginTime) / TickPerSec * 1000); end;

---

Tu peux faire à la µs

Code:

---

Result := Round((EndTime - BeginTime) / TickPerSec * 1000000);

---

Merci ShaiLeTroll, j'ai déja trouvé la réponse dans la faq :ccool:

donc avec QueryPerformanceCounter, j'ai 267 Microsecondes pour une grille diabolique.

J'y retourne !

Edit : 337 Microsecondes avec une grille a 17 valeurs de FullSpeed

le tick: 60 eme on multiplie par 6000 pour avoir des secondes
Les BRUTE FORCE: par exemple on calcule toutes les combinaisons de neuf ety on les essaye avec les reveles
On ecrit un logiciel avec 891 boucles imbriquées on tutilse se genre de techniques plutot qu'un parcours d'arbrte ou un bel algo recursif: on fgait dans le bestial

XY_Win et autre :D tu gardes bien précieusement tes techniques mais on utilise tous les memes. l'implémentation fait la différence
Le Xwing est un peu complique a explique mais tu le trouveras sur le net sans probleme II est plus facile de faire la chasse aux trios...
Et je vais pas t'aider cherche et programme :D Il parait que tu aimes cela!

Mais comme finalement je fais pas comme toi je vais te donner une technique que personne n'utilise:

020000050
134567891
567891234
0500000X0 <=== tu peux enlever des candidat de X le deux
Pourquoi? Parce qu'il est impossible d'avoir la dispo suivante
0200000500
xxx
xxx
0500000200
Car on peut permuter les paires de 2 et de 5 et on a alors plusieurs solutions Ce qui est interdit
0500000200
xxx
xxx
0200000500
Et un candidat de moins
pour une case on cherche souvent les valeurs possibles du fait de la disposition des autres mais le corolaire est productif: on cherche les valeurs qui ne peuvent pas être la

Je pense sortir les premiers chrono demain. Je les publierais (si j'ai pas trop honte)
Boris

Citation:

---

Envoyé par FullSpeed

le tick: 60 eme on multiplie par 6000 pour avoir des secondes

---

Ah bon, c'est donc plus petit que la milliseconde !
Vous vous contredisez avec Franck Soriano !!

Citation:

---

Envoyé par FullSpeed

Les BRUTE FORCE: par exemple on calcule toutes les combinaisons de neuf ety on les essaye avec les reveles
On ecrit un logiciel avec 891 boucles imbriquées on tutilse se genre de techniques plutot qu'un parcours d'arbrte ou un bel algo recursif: on fgait dans le bestial

---

Ca, je voyais bien ce que ca pouvais etre !! :lol:

Citation:

---

Envoyé par FullSpeed

XY_Win et autre :D tu gardes bien précieusement tes techniques mais on utilise tous les memes. l'implémentation fait la différence
Le Xwing est un peu complique a explique mais tu le trouveras sur le net sans probleme II est plus facile de faire la chasse aux trios...
Et je vais pas t'aider cherche et programme :D Il parait que tu aimes cela!

---

A ok, c'est des techniques de résolution de sudoku, je pensais a autre chose ! Je connais, pour le X-Wing !!

Citation:

---

Envoyé par FullSpeed

Mais comme finalement je fais pas comme toi je vais te donner une technique que personne n'utilise:

020000050
134567891
567891234
0500000X0 <=== tu peux enlever des candidat de X le deux
Pourquoi? Parce qu'il est impossible d'avoir la dispo suivante
0200000500
xxx
xxx
0500000200
Car on peut permuter les paires de 2 et de 5 et on a alors plusieurs solutions Ce qui est interdit
0500000200
xxx
xxx
0200000500
Et un candidat de moins
pour une case on cherche souvent les valeurs possibles du fait de la disposition des autres mais le corolaire est productif: on cherche les valeurs qui ne peuvent pas être la

---

Merci pour la technique, mais est ce que le solver ne doit pas justement résoudre les grilles a plusieurs combinaisons ? (voir premier post) En plus, je ne pense pas que ce que tu dises soit vrai : Exemple, dans ton dessin, imaginons que tout les chiffres sauf le X soient donnés : Tu peux mettre un deux et il ne pourra pas y avoir permutation !! (puisque les autres sont fixes)

Citation:

---

Envoyé par FullSpeed

Je pense sortir les premiers chrono demain. Je les publierais (si j'ai pas trop honte)
Boris

---

Bien sur que non t'auras pas honte, ca sert a ca les forums ! Bonne chance pour les chronos ...

En parlant de chrono , la fonction QueryPerformanceCounter dépends-elle de la performance du PC ?? (il me semble que non, mais ...)