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

Citation:

---

Envoyé par mick605

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

---

Si tu as un doute, le mieux c'est de le vérifier par toi même !

Fait un petit programme qui se contente de lire GetTickCount en boucle :

Code:

---

1 2 3 4 5 6 7 8 9 10 11

var old : cardinal; courant : cardinal; begin old := GetTickCount; repeat courant := GetTickCount; until courant<>old; ShowMessage(IntToStr(courant-old)); end;

---

Tu verras qu'en moyenne, GetTickCount s'incrémente de 15 en 15 (parfois un peu plus d'ailleurs...).

Citation:

---

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

---

En théorie, oui, ça dépend de l'électronique et de l'horologe utilisée pour Windows pour calculer le compteur. C'est pour ça que tu dois lire QueryPerformanceFrequency, pour faire la convertion en unités de temps, comme l'a indiqué ShaiLeTroll. QueryPerformanceCounter et
QueryPerformanceFrequency s'utilisent ensemble.

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:

---

Hello les amis :

Je profite du message de Boris pour rebondir...

J'ai lu tous vos posts et suis ravi que le défi déclenche autant de passion et une telle émulation.
Je tiens quand même à vous rappeler que le but du jeu n'est pas de faire un algo qui résoud AIEscargot le plus vite possible.

Un petit rappel des règles :

Citation:

---

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

---

Si vous ne résolvez pas 1000 AI escargot en une seconde, votre participation est la bienvenue car vous serez tout simplement dans mon cas !
Effectivement, le mien effectuant cette résolution entre 20 et 70ms, je n'ai pas cherché à l'optilmiser plus : l'effet est immédiat, on n'attend pas et pour un utilisateur, c'est ce qui compte.
A part cette grille, mon logiciel trouve une solution toutes les millisecondes pour une grille diabolique (affichage du compteur compris dans le chronométrage).
UN millième de seconde pour résoudre une grille,ça me paraît très bien !

Sachez que la délibération du jury ne va pas se faire en comptant les nanosecondes en + ou en - d'une solution à l'autre en faisant un protocole expérimental sur 100 machines différentes. La mienne date de 2005 d'ailleurs...

N'oubliez pas qu'une bonne solution logicielle est une solution ergonomique, agréable à utiliser, avec des fonctionnalités utiles, comme dans la vraie vie quoi !
Etant musicien par ailleurs, je suis sensible à la créativité, à l'esthétisme aussi, donc ne faites pas trop les nerds :mouarf:
Egalement, celui qui me pond une solution qui fait des violations d'accès ou des indices hors limite aura beau m'avoir fait une ferrari du sudoku sera mal noté. ça va de soi me direz vous, mais testez bien quand même...
Egalement bis, le code non commenté, mal indenté, sans casse, qui n'utilise pas les constantes, non modulaire, qui ignore la programmation objet etc me donne des boutons.
Encore une fois, mettez vous bien en situation réelle : un code lisible, compréhensible, maintenable, fait dans le règles de l'art : celui qui me met toutes les lignes de sa procédure au taquet de la goutierre de l'éditeur va être sanctionné...
Comme il est dit aussi, les fonctionnalités ou effets visuels inventifs, intelligents etc sont plus que bienvenus.

Moralité : Il est clair que si je dois attendre 10 minutes pour que l'application résolve une grille, ça risque de ne pas aller, mais entre 1 milliseconde et une picoseconde, je ne suis pas sûr que mon cerveau fasse la différence, (d'où l'idée du chronomètre ok ok), mais à ce niveau, on va regarder l'ensemble de l'application, et un sudoku solver plus rapide qu'un autre peut être moins bien classé que ce dernier.

A bon entendeur...

Entièrement d'acocrd la vitesse n'est pas tout mais c'est la où je suis bon
alors j'insiste. Je suis particulièrement nul pour l'aide par exemple et si j'arrive a être le plus rapide je risque fort d'être le dernier sur l'aide
(Comme on dit je fais l'ane pour avoir du son ;D)

Il y a un petit problème avec les règles: si on fait un soldeur pur il n'a a pas de fonctionnalités a montrer: on calcule et c'est tout
Ou alors on fait un playeur dans lequel on propose des solutions ou des options qui permettent au joueur de progresser dans la résolution et la de fait on peut mettre des options !!!
Vu l'engouement de ce defi on pourrait peut etre ramenér la date de cloture plus tot: il va etre dur de maintenir les esprits aussi longtemps.
Je proposerai bien fin Juillet mais les aoutiens vont râler!

Mick le XY_wing est une variante du X_wing.

Pout les tickcount qui evoleuent par 15 ou 16: combien cela fait un centieme de seconde divise par 60?
Comme disait Lavoisier rien ne se perds, rien ne se cree,
tout se transforme
Boris

Citation:

---

Envoyé par FullSpeed

Entièrement d'acocrd la vitesse n'est pas tout mais c'est la où je suis bon
alors j'insiste. Je suis particulièrement nul pour l'aide par exemple et si j'arrive a être le plus rapide je risque fort d'être le dernier sur l'aide
(Comme on dit je fais l'ane pour avoir du son ;D)

Il y a un petit problème avec les règles: si on fait un soldeur pur il n'a a pas de fonctionnalités a montrer: on calcule et c'est tout
Ou alors on fait un playeur dans lequel on propose des solutions ou des options qui permettent au joueur de progresser dans la résolution et la de fait on peut mettre des options !!!
Vu l'engouement de ce defi on pourrait peut etre ramenér la date de cloture plus tot: il va etre dur de maintenir les esprits aussi longtemps.
Je proposerai bien fin Juillet mais les aoutiens vont râler!

Mick le XY_wing est une variante du X_wing.

Pout les tickcount qui evoleuent par 15 ou 16: combien cela fait un centieme de seconde divise par 60?
Comme disait Lavoisier rien ne se perds, rien ne se cree,
tout se transforme
Boris

---

Si tu es bon en "vitesse" ou optimisation, essaie de progresser sur d'autres disciplines, ça te servira dans le cadre professionnel notamment.

Par expérience, lorsque tu présentes une application à un client, ce qu'il apprécie et qu'il remarque en premier, c'est le petit truc ergonomique qu'il trouve pratiqueet joli, une petit jauge bleue ou une information qui clignote.
Ton super algo, il s'en fout et ne le voit pas, ça marche ou ça ne marche pas, point.
On est d'accord qu'ici on est entre developpeurs, et ne tombons pas dans cet extrême, mais ne tombons pas dans l'autre non plus, car aucun n'est bon.

Il ne s'agit pas de développer "l'aide".
Et contrairement à ce que tu penses, même l'interface du solver peut présenter un intérêt : il faut que l'utilisateur puisse saisir les chiffres facilement, que la grille soit agréable à regarder, que quand il y a plusieurs solutions, on puisse les visualiser facilement.
Le solver peut être considéré comme un assistant expert pour un joueur ? Et pourquoi pas ?
Il y a plein d'idées à développer, soyez créatifs !!!

Bon, moi je dis ça, c'est par rapport au défi en lui même.
Maintenant si ce qui vous fait triper c'est d'explorer l'infiniment petit et de faire de l'optimisation, éclatez vous !
Le but, c'est de s'amuser et d'échanger, de faire connaissance et pour moi aussi de repérer des bons Delphimens...

Bonne prog !

Je suis entierement d'accord avec toi on est la pour lier connaissance et se faire plaisir.
Je m'applique sur l'ergonomie et la clarté du code: quand on optimise on a pas ce genre de soucis;
En realite je sis occupe a enlever tous les bouts d'ASM qui trainaient et dont le seul but etait la vitesse.

Par contre j'ai acquis une certaine experience en optimisation
Cela fait30 ans que je programme: il serait dommage de rien avoir appris
Aussi si je peux renvoyer l'ascenseur des connaissance par le biais des defis.

Proposition d'une modifie :
Le format standard des grilles de sudoku est un string de 81 characteres
avec 0 pour les cases vides
Ne pourrait-on pas imposer ce format (et non 9 strings de 9?)
Boris

Au fait Il y a quoi a gagner? Rien je l'espere!

Citation:

---

Au fait Il y a quoi a gagner? Rien je l'espere!

---

Cette année non il n'y a rien à gagner à part la satisfaction d'avoir fait un beau programme en Delphi et peut-être appris ou progressé dans certains domaines ;)

Citation:

---

Envoyé par FullSpeed

Je suis entierement d'accord avec toi on est la pour lier connaissance et se faire plaisir.
Je m'applique sur l'ergonomie et la clarté du code: quand on optimise on a pas ce genre de soucis;
En realite je sis occupe a enlever tous les bouts d'ASM qui trainaient et dont le seul but etait la vitesse.

---

Aujourd'hui, le compilateur Delphi est vraiment très performant. L'ASM apporte rarement grand chose. Quand j'ai fait ma solution, j'ai tout coder en Delphi, puis j'ai désassemblé chaque routine critique pour voir si on pourrait gagner en y mettant de l'ASM. Ben... le compilo avait déjà fait toutes les optims que je pensais pouvoir faire en ASM... même l'arithmétique des pointeurs n'a pas donné grand chose...

Citation:

---

Envoyé par FullSpeed

Proposition d'une modifie :
Le format standard des grilles de sudoku est un string de 81 characteres
avec 0 pour les cases vides
Ne pourrait-on pas imposer ce format (et non 9 strings de 9?)

---

Pourquoi faire ?
Rien ne t'empêche de gérer les deux formats si tu veux. Le format standard qu'on a définit est fait pour qu'on puisse tester facilement les solutions sur nos grilles de test.

Citation:

---

Envoyé par FullSpeed

Au fait Il y a quoi a gagner? Rien je l'espere!

---

C'est un défi, pas un concours... Tu gagnes déjà le droit d'être connu 8-), ce qui n'est pas rien ;).

Tout a fait d'accord sur ces points la !

Dis moi, Félix Guillemot, simple curiosité, ton solveur fait il par la logique ou en passant toutes les solutions ?

Citation:

---

Envoyé par mick605

Tout a fait d'accord sur ces points la !

Dis moi, Félix Guillemot, simple curiosité, ton solveur fait il par la logique ou en passant toutes les solutions ?

---

A l'origine, j'ai observé ma femme jouer au Sudoku, et essayé de m'y mettre et ai vite constaté que j'étais une vraie tâche : je bloquais sur un problème pendant longtemps, et n'étais pas sûr d'aboutir.
Dans ma démarche de méthodologie (http://www.flx.fr/methodologie/), je me suis dit qu'il devait exister une méthode ou une combinaison de méthode qui permettait de résoudre un Sudoku, sans hésiter, sans bloquer, en appliquant bêtement la méthode, de la même façon qu'on résoudrait un système d'équations à l'école.
J'y suis arrivé, et ai voulu défier ma femme avec ma méthode. Je me suis aperçu du fait que cette méthode ne supportait pas la moindre faute d'étourderie, et que j'échouais parfois à cause de ça, mais j'étais convaincu qu'elle fonctionnait. Ma femme était sceptique, et ça m'énervait, alors j'ai pris mon Delphi et j'ai modelisé cette méthode dans un algorithme pour la vérifier. Et elle fonctionne parfaitement. Débat clos donc.
Tout ça pour expliquer que le but de départ était de fabriquer une méthode appliquable par un humain qui joue au Sudoku.
Je l'expliquerai en détail à la fin du défi.
J'espère avoir répondu correctement à ta question.

Félix.

Citation:

---

Envoyé par FullSpeed

Je suis entierement d'accord avec toi on est la pour lier connaissance et se faire plaisir.
Je m'applique sur l'ergonomie et la clarté du code: quand on optimise on a pas ce genre de soucis;
En realite je sis occupe a enlever tous les bouts d'ASM qui trainaient et dont le seul but etait la vitesse.

Par contre j'ai acquis une certaine experience en optimisation
Cela fait30 ans que je programme: il serait dommage de rien avoir appris
Aussi si je peux renvoyer l'ascenseur des connaissance par le biais des defis.

Proposition d'une modifie :
Le format standard des grilles de sudoku est un string de 81 characteres
avec 0 pour les cases vides
Ne pourrait-on pas imposer ce format (et non 9 strings de 9?)
Boris

Au fait Il y a quoi a gagner? Rien je l'espere!

---

Le but est de s'amuser, on est d'accord, donc si tu ne veux faire que de l'optimisation, y a vraiment aucun problème, je suis juste venu rappeler que ce n'était pas l'unique sujet de ce défi et pour ne tombe pas dans un concours de bits :D

Pour le format, il a été adopté après débat parce qu'à sa lecture, il permet de voir la grille, sans interface, sans rien. Une informatique plus humaine...

Je pense que ça ne devrait pas poser de problème...

C'était pour pouvoir utiliser les grilles qui trainent un peu patrtout sur le net
La vraie difficulté d'un format est de reconnaitre les grilles apres flip,rotation,, inversion de chiffres
Alors on indique un format par sa terminaison .sdd .ssd...

Felix: on a arrêter de chercher a faire des générateurs car on a jamais réussi a déterminer la fonction precises des révélés: sur un probleme donné on ne peut changer la place des reveles: Pourquoi? Pourquoi faut-il placer un revele la et pourquoi 17 ou 20 oui 25?
Partant d'un carré latin comment créer un problème si se n'est en retirant J'ao hate de voir ta methode

Je pense que l'on ne sera pas on n'aura pas de solution logique universelle
Mais j'ai le droit de me tromper
Boris

Citation:

---

Envoyé par FullSpeed

Felix: on a arrêter de chercher a faire des générateurs car on a jamais réussi a déterminer la fonction precises des révélés: sur un probleme donné on ne peut changer la place des reveles: Pourquoi? Pourquoi faut-il placer un revele la et pourquoi 17 ou 20 oui 25?

---

je suis désolé mais je ne comprends pas ce que tu veux dire ?

générateurs = ?
révélés , reveles = ?
"Pourquoi faut-il placer un revele la et pourquoi 17 ou 20 oui 25" = ?
"un carré latin" = ?

De quoi parles tu ? Quel est le sujet ?

Je ne comprends pas les termes que tu emploies, ni les concepts.

Désolé.

mick605 pour tes problemes de chrono mais en VB
http://www.developpez.net/forums/d65...s-tres-courts/
pour les tests tu peux lire ce poste
http://www.developpez.net/forums/sho...95&postcount=5

Sans qu'il ne s'agisse d'une langue il y a quelques mots clefs pour parler du sudoku

Au départ du Sudoku est le carré latin qui existe depuis des siecles
il s'agit de matrice carrée (pas forcement 9*9) dont les cases sont remplies avec des symboles differents appartenant tous a un ensemble de depart de la même taille que la matrice

par exemple un carre latin de 4*4 pourra etre
ABCD
BCDA
CDAB
DABC
n'existe pour ces carres que la notion de colonnes et rangées
Pour le sudoku la matrice fait 9*9 et les valeurs sont les chiffres de 1 à 9
Mais on a rajoute une notion c'est celle,des boites,carres,regions(Il n'y a pas de nom defini)

123 456 789
456 789 123
789 123 456

Nous avons définie trois régions dans lesquelles le sudoku oblige a l'unicité des valeurs
Un ensemble de trois régions forme un block. Il y a trois blocks horizontaux et trois blocks verticaux. Si on prends une grille de sudoku on peu permuter les blocks deux a deux sans modifiés le problème
a l'intérieur d'un bloc de trois rangées par exemple on peut permuter les lignes

123 456 789 456 789 123
456 789 123 789 123 456
789 123 456 123 456 789 deux fois le meme

Une fois le carré latin remplit il faut le transformer en problème. Pour cela on cache un certain nombre de cases pour ne laisser apparents que les 'reveles' Dans un Sudoku le nombre de reveles maximum est 30. Il n'y a pas de minimum mais on ne peut en faire avec 16 reveles
On peut bien sur physiquement ne laisse que 16 révélés mais il existe alors plusieurs solutions: on peut reconstituer plusieurs carrés latins.
Le sudoku oblige a l'unicité de la solution
Tu l'as compris un générateur est donc un logiciel qui partant d'un carré latin va cacher des cases en vérifiant que l'on peut retrouver le carré original

L'interet pour les joueurs est qu'en realité quand on fabrique un problème on n'applique pas des 'techniques' de cachage que l'on peut retrouver: on procede par hasard

on part du carre latin on enleve 49 cases au hasard . On regarde si il existe une solution (notre solveur) puis on enlevé les révélés un par un et on regarde si on peut retrouver le carré. Si oui on en enlevé un autre etc..

Quand on commnece a creer un pb de sudoku on ne sait pas combien il y aura de reveles ni la complexite de la grille
Car il ne faut pas lier la difficulté d'une grille au nombre de reveles: une grille 17 reveles peuvent etre beaucoup plus difficile que des 23 (AI escargot)
La grosse question mathématique est pourquoi partant d'un meme carré latin il est possible de fabriquer des pb 17 ou 25 reveles, de difficulté 1 ou 6 et donc comment les reveles influent dessus

J'espère ne pas avoir été trop abscons et que maintenant le jargon sudoku est compréhensible

Je reviens sur l'ASM en Delphi: les compilateurs sont de fait de plus en plus performants et le code generé est souvent bien au dela des compétences des programmeurs que nous sommes. C'était moins vrai il y a cinq ans quand je travaillais sur le sudoku
Il reste une raison qui justifie l'usage de l'ASM: les Langage de troisieme generation comme le C, le Fortran,le Pascal ne permettent pas d'acceder aux INDICATEURS du processeurs. Parfois leur usage peut se reveler opportun.

Dans la logique qui a fait passer des langages de deuxieme generation
ou d'assemblage on a fait des langages qui s'eloignaient du hard encore plus. Et comme les indicateurs sont liés au hard on les a ecarte

Dans un 6502 vous aviez 1 indicateur mais dans un core 4 peut etre une dizaine (il faudrait regarder) Alors les langages ne peuvent les integrer.
Mais la part de l'ASM diminue.
Et surtout si j'ai comis des erreurs rectifie les :D


Boris

Citation:

---

Envoyé par Montor

mick605 pour tes problemes de chrono mais en VB
http://www.developpez.net/forums/d65...s-tres-courts/
pour les tests tu peux lire ce poste
http://www.developpez.net/forums/sho...95&postcount=5

---

Merci, mais j'ai déja ce qu'il faut niveau chrono !
En tout cas, j'avais pas pensé a ce qu'il y a dans le deuxieme lien, mais je ne pense pas avoir besoin de cette précision la :ccool: !!

Merci quand meme !

Quand on fait une boucle de plusieurs milliers
il faut penser a remettre les variables a leur valeur initiales
autrement le calcul est faux

Code:

---

1 2 3

a:=Probleme for i:=1 to 10000 do resout(a)

---

Si le résultat est dans a : mauvaise pioche
Boris

En méthode purement brute force
avec 81 boucles les premiers resultats sont les suivants
Avec AI Escargot 400 résolutions a la seconde
Je suis loin des miiiemes de secondes mais cela me semble encourageant
Boris

Code:

---

1 2 3 4 5

i := gettickcount; for j:=1 to 400 do BF_Solveur(S); Generew.Caption := IntTostr((gettickcount-i));

---

Yeah ! C'est pas mal ! Mais bourrin !!! ^^

Essaye avec du recursif !
Et pour ce type de solver, le plus dur, c'est pas AI Escargot, mais une grille avec le moins de valeurs possibles ! Genre les 17 que tu nous a filé !!

Bonjour

Merci Fullspeed pour ces infos sur les carrés latins et ta manière de voir les choses concernant la création de grilles. Pour ma part, j'ai opté pour la resolution par la logique , ce qui me permet de créer les grilles autrement. je m'explique avec ce pseudo-code allegé

1/ Preparation -> aucune case révélée et tous les candidats sont possibles.
2/ je recherche aleatoirement un case encore non révélée
3/ Je pose un chiffre choisi aléatoirement dans la liste des candidats encore possible pour cette case (je met un drapeau 'révélé') et je met a jour la liste des candidats en L C et Regions
4/ Je retourne en 2 16 fois.
5 / Je tente de resoudre la grille avec toutes mes methodes programmées et en boucle a chaque fois que j'ai pu avancer un peu. chaque decouverte st flagué 'non révélé'

6 / si erreur dans la grille retour en 1
7/ si grille terminée je creer ma grille avec les seuls flagués 'révélés' et exit;
8/ si la grille n'est pas terminé, je pose un révélé en plus ( goto 2,3,5)

Cela donne 75% de grille fausses, donc 25% environ de grilles justes. ce qui suffit largement. L'algo produit 350 grilles justes à la seconde.

Mon projet avance, je code la logique des X et Y wings en ce moment

C'est vrai les grilles de 17 révélés sont durs a résoudre par la logique, je seche !

a+
Pascal

Citation:

---

Envoyé par Pascal Fonteneau

Bonjour

je m'explique avec ce pseudo-code allegé

1/ Preparation -> aucune case révélée et tous les candidats sont possibles.
2/ je recherche aleatoirement un case encore non révélée
3/ Je pose un chiffre choisi aléatoirement dans la liste des candidats encore possible pour cette case (je met un drapeau 'révélé') et je met a jour la liste des candidats en L C et Regions
4/ Je retourne en 2 16 fois.
5 / Je tente de resoudre la grille avec toutes mes methodes programmées et en boucle a chaque fois que j'ai pu avancer un peu. chaque decouverte st flagué 'non révélé'

6 / si erreur dans la grille retour en 1
7/ si grille terminée je creer ma grille avec les seuls flagués 'révélés' et exit;
8/ si la grille n'est pas terminé, je pose un révélé en plus ( goto 2,3,5)

Cela donne 75% de grille fausses, donc 25% environ de grilles justes. ce qui suffit largement. L'algo produit 350 grilles justes à la seconde.

---

Pas Mal! Surtout les 25%:ccool:

Comment fais tu pour savoir si ton problème n'a pas plusieurs solutions?
Un solver logique a du mal...
Boris