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

**darrylsite** · 17/10/2009, 16h56

voila qui commence à etre interessant. J'avais abandoné mon projet un certain temps vu que les participants ne se manifestaient pas

Je vais donc reprendre le projet, et faire quelques retouches.

Envoyé par Alcatîz

C'est tout-à-fait envisageable, une autre demande a été faite par MP.
Une nouvelle date limite sera communiquée incessamment.

Ouais, ce sera genial. Vu que je n'ai pas trop le temps ces temps ci, occupé à finir mes exams.

Envoyé par dimanche2003

Mon projet est bien avancé, solution presque instantanée des grilles les plus difficiles

ça fait combien en millisecondes? Moi, ma plus faible performance est de 5ms pour une grille vide; sinon je suis dans les micro-secondes.

**mick605** · 18/10/2009, 03h52

Envoyé par dimanche2003

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

Salut

As tu participé au défi Delphi ?

Envoyé par darrylsite

ça fait combien en millisecondes? Moi, ma plus faible performance est de 5ms pour une grille vide; sinon je suis dans les micro-secondes.

Essaye la grille Near Worst Case (elle porte bien son nom) :

Code :

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

Allez, a+

**dimanche2003** · 18/10/2009, 07h52

Envoyé par mick605

Salut

As tu participé au défi Delphi ?

Essaye la grille Near Worst Case (elle porte bien son nom) :

Code :

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

Allez, a+

Pour Delphi, je n'étais pas prêt, dommage... Voyons cette grille.
ok, il me faut 4,009 s... J'étais un peu prétentieux... Essaie plutôt : 071000000000200000000000300050074000300000200000610000000000047600800000000000510 : c'est "plus pire" !
elle est pas mal...

**mick605** · 18/10/2009, 16h20

A ouais, elle est assez dure aussi ...
En BruteForce, je met 76 millisecondes, en logique et bruteforce, je met 10 millisecondes.

Par contre, avec Near Worst Case, en bruteforce, je met 3 secondes, et en logique, je met 160 micro secondes ... l'écart est plus grand ^^

**darrylsite** · 18/10/2009, 21h35

Envoyé par mick605

A ouais, elle est assez dure aussi ...
En BruteForce, je met 76 millisecondes, en logique et bruteforce, je met 10 millisecondes.

Par contre, avec Near Worst Case, en bruteforce, je met 3 secondes, et en logique, je met 160 micro secondes ... l'écart est plus grand ^^

Avec mon pseudo logic, je fais 360 micro pour le nearworst. Bien moins difficile que le easter monster et IAS.

Sinon pour la grille de dimanche2003, je fais 1,850 millisecondes. Bien dure en effet

**mick605** · 18/10/2009, 22h01

Envoyé par darrylsite

Avec mon pseudo logic, je fais 360 micro pour le nearworst. Bien moins difficile que le easter monster et IAS.

Sinon pour la grille de dimanche2003, je fais 1,850 millisecondes. Bien dure en effet

Haha, bien joué !
Tu peux me dire quelques temps sur ces grilles :

Code :

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

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
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
Grille 1 :
500004200
100020030
090000005
000400000
805196302
000005000
400000060
030070009
007300008
 
Grille 2 :
020001030
800900001
000060400
009600180
300000007
087003900
006090000
100006008
050300010
 
Grille 3 :
084010590
056009000
009050040
040500938
000000000
931004070
090040700
000900450
075080360
 
Grille 4 (AI Escargot) :
100007090
030020008
009600500
005300900
010080002
600004000
300000010
040000007
007000300
 
Grille 5 (Easter Monster) :
100000002
090400050
006000700
050903000
000070000
000850040
700000600
030009080
002000001
 
Grille 6 (1ere de la liste 17 de FullSpeed) :
071000000
000080600
000400000
000100072
800050000
000000000
040702000
600000850
000000300
 
Grille 7 (derniere de la liste 17 de FullSpeed) :
079000600
000100400
000200000
000000750
400300000
100000000
060080000
000090010
000000023

Grille 1 : 0.134 ms
Grille 2 : 0.157 ms
Grille 3 : 0.311 ms
Grille 4 : 1.130 ms
Grille 5 : 5.460 ms
Grille 6 : 0.135 ms
Grille 7 : 0.137 ms

**darrylsite** · 18/10/2009, 22h31

Envoyé par mick605

Haha, bien joué !
Tu peux me dire quelques temps sur ces grilles :

Code :

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

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
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
Grille 1 :
500004200
100020030
090000005
000400000
805196302
000005000
400000060
030070009
007300008
 
Grille 2 :
020001030
800900001
000060400
009600180
300000007
087003900
006090000
100006008
050300010
 
Grille 3 :
084010590
056009000
009050040
040500938
000000000
931004070
090040700
000900450
075080360
 
Grille 4 (AI Escargot) :
100007090
030020008
009600500
005300900
010080002
600004000
300000010
040000007
007000300
 
Grille 5 (Easter Monster) :
100000002
090400050
006000700
050903000
000070000
000850040
700000600
030009080
002000001
 
Grille 6 (1ere de la liste 17 de FullSpeed) :
071000000
000080600
000400000
000100072
800050000
000000000
040702000
600000850
000000300
 
Grille 7 (derniere de la liste 17 de FullSpeed) :
079000600
000100400
000200000
000000750
400300000
100000000
060080000
000090010
000000023

Grille 1 : 0.173 ms
Grille 2 : 0.450 ms
Grille 3 : 0.302 ms
Grille 4 : 0,480ms
Grille 5 : 1,586ms
Grille 6 : 0.344 ms
Grille 7 : 2,840ms

J'utilise actuellement force brute+logic pour resoudre les grille. J'attaque directement en force brute sans faire de la logique avant, ce qui me donne de meilleur perf pour les grille difficile, mais de mediocre pour les grille simple.

A vrai dire j'ai beaucoup travailler à reduire le temps de la grille 4, à savoir l'IAS.

**mick605** · 19/10/2009, 13h30

Envoyé par darrylsite

Grille 1 : 0.173 ms
Grille 2 : 0.450 ms
Grille 3 : 0.302 ms
Grille 4 : 0,480ms
Grille 5 : 1,586ms
Grille 6 : 0.344 ms
Grille 7 : 2,840ms

J'utilise actuellement force brute+logic pour resoudre les grille. J'attaque directement en force brute sans faire de la logique avant, ce qui me donne de meilleur perf pour les grille difficile, mais de mediocre pour les grille simple.

A vrai dire j'ai beaucoup travailler à reduire le temps de la grille 4, à savoir l'IAS.

Yeah ! Tu dois avoir un solveur bruteforce plus performant que le mien, mais un solveur logique moins performant ... Ca serait interressant de partager nos solutions, apres le défi

Les autres participants pourraient aussi donner leurs temps, ca serait bien ...

**darrylsite** · 19/10/2009, 14h43

Envoyé par mick605

Yeah ! Tu dois avoir un solveur bruteforce plus performant que le mien, mais un solveur logique moins performant ... Ca serait interressant de partager nos solutions, apres le défi

Les autres participants pourraient aussi donner leurs temps, ca serait bien ...

Certainnement ton solveur logic est plus performant, mais pour gagner en performance avec ma force brute, j'ai enlevé pas mal de methode qu'utilise la logique. Aussi, je tiens à garder la qualité de mon code, ce qui est important. En optimisant le code, j'ai degradé la qualité de mon code (non respect des regles d'encapsulation, utilisation minimum des fonction donc j'evite les decoupages en module excessive, ...).
Je crois que je ne vais pas chercher à descendre plus bas. De toute façon, resoudre toutes les grilles en moins de 50ms c'est dejà pas mal je pense.

T'es tu aussi penché sur le design ou juste la performance de ton solveur? comme la date limite est repoussée, je crois que j'ai le temps de me mettre à faire un peu de photoshop ou illustateur pour avoir une belle interface.

**mick605** · 19/10/2009, 17h33

Envoyé par darrylsite

Certainnement ton solveur logic est plus performant, mais pour gagner en performance avec ma force brute, j'ai enlevé pas mal de methode qu'utilise la logique. Aussi, je tiens à garder la qualité de mon code, ce qui est important. En optimisant le code, j'ai degradé la qualité de mon code (non respect des regles d'encapsulation, utilisation minimum des fonction donc j'evite les decoupages en module excessive, ...).
Je crois que je ne vais pas chercher à descendre plus bas. De toute façon, resoudre toutes les grilles en moins de 50ms c'est dejà pas mal je pense.

T'es tu aussi penché sur le design ou juste la performance de ton solveur? comme la date limite est repoussée, je crois que j'ai le temps de me mettre à faire un peu de photoshop ou illustateur pour avoir une belle interface.

Ouais, moi aussi, je me suis arreté d'optimiser quand j'ai jugé que le gain de temps serait dérisoire par rapport a la qualité du code ... Par contre, j'ai laissé toutes mes méthodes logiques dans la résolution ... Pour certaines grilles, j'aurais pu gagner un peu de temps en supprimant les méthodes de résolution qui n'aboutissent a rien ...

Pour le design, j'ai essayé de faire une interface sympa et correcte ... Je n'ai pas de logiciel d'image, et je ne suis pas bon en design

donc je suis resté basique ...

Je te rapelle que je ne participe pas au défi pascal

Mais j'attends avec impatience la fin de votre défi pour pouvoir recevoir les résultats sur la section Delphi (et oui, on attends apres vous

) !

Allez, A+

Mick605

**darrylsite** · 20/10/2009, 21h17

Envoyé par mick605

Ouais, moi aussi, je me suis arreté d'optimiser quand j'ai jugé que le gain de temps serait dérisoire par rapport a la qualité du code ... Par contre, j'ai laissé toutes mes méthodes logiques dans la résolution ... Pour certaines grilles, j'aurais pu gagner un peu de temps en supprimant les méthodes de résolution qui n'aboutissent a rien ...

Pour le design, j'ai essayé de faire une interface sympa et correcte ... Je n'ai pas de logiciel d'image, et je ne suis pas bon en design

donc je suis resté basique ...

Je te rapelle que je ne participe pas au défi pascal

Mais j'attends avec impatience la fin de votre défi pour pouvoir recevoir les résultats sur la section Delphi (et oui, on attends apres vous

) !

Allez, A+

Mick605

J'ai remarqué que plus le solveur logique est performant(contient pas mal de methode de resolution), le solveur brute force l'est moins. Alors, je me suis resigné à baser mes recherches sur les methodes les plus essentielles et laisser tomber celles qui font raler la recherche des solution. Je me demande maintenant pourquoi j'ai codé toutes les autres methodes starX, formation etoile, chainage forcé et autres

Sinon pour la grille 7, je fais maintenant 175 micros au lieu de 2 millis.

**mick605** · 20/10/2009, 21h53

Envoyé par darrylsite

J'ai remarqué que plus le solveur logique est performant(contient pas mal de methode de resolution), le solveur brute force l'est moins. Alors, je me suis resigné à baser mes recherches sur les methodes les plus essentielles et laisser tomber celles qui font raler la recherche des solution. Je me demande maintenant pourquoi j'ai codé toutes les autres methodes starX, formation etoile, chainage forcé et autres

Sinon pour la grille 7, je fais maintenant 175 micros au lieu de 2 millis.

Bah, mon but était d'essayer de résoudre les grilles par la logique, donc j'ai codé quelques techniques, et je ne vais pas les supprimer, au contraire ... Si j'en avait eu d'autres, j'aurais préféré coder plusieurs techniques de résolution logique et avoir un moins bon temps, que jouer le temps a tout prix ... Apres, il faut savoir quelles méthodes sont (vraiment) utiles pour la résolution logique (je doute que le truc des chaines soit dans ce cas tres utile ...)

Mon deuxieme objectif dans ce défi est d'avoir un code parfaitement modulable ... J'ai fait des méthodes de résolution tres générales, et en 5 procedures seulement (divisées en sous procédures), j'arrive a utiliser toutes les methodes de résolution de mon solveur. En clair, par exemple, pour les candidats doubles, candidats triples, .... je n'ai qu'une seule procedure qui prends un argument N et si N vaut 2 il trouvera les candidats doubles, si N=3, les candidats triples, etc.

Il y a aussi deux autres objectifs que je me suis fixé sur mon solveur qui m'ont fortement contraint dans le codage des méthodes, mais celles la, j'en parlerai apres le défi ...

Bien joué pour la grille 7

**Alcatîz** · 25/10/2009, 16h28

Afin de permettre à tous les candidats de peaufiner leur code, la date limite de rentrée des projets est à présent fixée au 31/12/2009.

Des candidatures de dernière minute sont toujours possibles !

**Chin Tao** · 26/10/2009, 11h03

Bonjour à tous,

Vu l'allongement du délai, je pense participer au tournoi.
Vu mon niveau en programmation (amateur), mon solveur fera surement piètre figure face à celui des autres candidats, mais il sera intéressant d'avoir l'avis argumenté d'un spécialiste sur mon code.
Par contre je partirai d'office avec une pénalité de 5 points, étant incapable de réaliser un programme multi-plateforme (ou alors s'il tourne sous Linux, ce sera vraiment par le plus grand des hasards).

**darrylsite** · 26/10/2009, 20h00

Envoyé par Chin Tao

Par contre je partirai d'office avec une pénalité de 5 points, étant incapable de réaliser un programme multi-plateforme (ou alors s'il tourne sous Linux, ce sera vraiment par le plus grand des hasards).

Ce defi concerne lazarus qui est un compilateur multi-plateforme. A mois que tu utilise des librairies ou instructions specifiques à un os donné, ton code pourra bien etre compilé sous windows, linux et autres.

Sinon, j'aimerais, savoir si j'envoie mon code maintenant est-ce que pourrais-je envoyer une autre version plus tard si jamais je modifiais le code?

**Alcatîz** · 26/10/2009, 20h23

Envoyé par darrylsite

Sinon, j'aimerais, savoir si j'envoie mon code maintenant est-ce que pourrais-je envoyer une autre version plus tard si jamais je modifiais le code?

Absolument, vous pouvez envoyer plusieurs versions successives, la dernière en date sera prise en compte.

**Chin Tao** · 29/10/2009, 09h33

Bonjour Darrylsite, bonjour à tous les autres,

Tant mieux si Lazarus fait tout comme un grand (à priori nulle instruction spécifique). Personnellement, je ne pourrais pas tester la validité de la version Linux.
Donc, suite à cette remarque, j'annonce officiellement ma participation au défi.

Merci.

**Alcatîz** · 29/10/2009, 20h04

Envoyé par Chin Tao

Personnellement, je ne pourrais pas tester la validité de la version Linux.
Donc, suite à cette remarque, j'annonce officiellement ma participation au défi.

Merci, nous en prenons acte. Bonne chance !

**Chin Tao** · 13/11/2009, 10h31

Bonjour Alcatîz, bonjour à tous les autres,

Sur le forum Delphi, il préconise de zipper tous le projet (exe compris).
Pour lazarus aussi ?
Parce que vu la taille des exécutables ça risque pas de faire un peu gros ?