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

J'aimerais savoir si un ensemble E est inclus (entierement) dans un de ces ensembles la : [1,4,7], [2,5,8] ou [3,6,9] , Mais j'aimerais ne pas le coder en "dur" !
Et donc j'aurais trouvé une technique, mais pour cela, il faudrait que je puisse multiplier un ensemble par un facteur constant (sans passer toutes les valeurs, si possible !




Voici les grilles :

Code:

---

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

---

Citation:

---

Envoyé par mick605

J'aimerais savoir si un ensemble E est inclus (entierement) dans un de ces ensembles la : [1,4,7], [2,5,8] ou [3,6,9]

---

Ca c'est pas difficile :

Code:

---

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

type MySet = set of byte;   var E : MySet; TestSet1, TestSet2, TestSet3 : MySet; EstInclus : boolean; begin TestSet1 := [1, 4, 7]; TestSet2 := [2, 5, 8]; TestSet3 := [3, 6, 9];   E := [1]; // C'est l'ensemble que tu testes, tu mets ce que tu veux.   EstInclus := (Set1*TestSet1 = Set1 ) or (Set1*TestSet2 = Set1) or (Set1*TestSet3=Set1);

---

Rien de plus simple !

En fait, il ne faut pas oublier les opérateurs sur les ensembles. Le multiplicateur * permet de calculer l'intersection de deux ensembles. Donc si A*B=A ça veut dire que A est entièrement inclus dans B.

Par contre attention, les ensembles sont plutôt lents en Delphi. Il existe un moyen de faire la même chose très facilement et de façon très efficace (j'en dis pas plus... ;)), sans utiliser les ensembles bien sûr...

Citation:

---

Envoyé par Franck SORIANO

Ca c'est pas difficile :

Code:

---

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

type MySet = set of byte;   var E : MySet; TestSet1, TestSet2, TestSet3 : MySet; EstInclus : boolean; begin TestSet1 := [1, 4, 7]; TestSet2 := [2, 5, 8]; TestSet3 := [3, 6, 9];   E := [1]; // C'est l'ensemble que tu testes, tu mets ce que tu veux.   EstInclus := (Set1*TestSet1 = Set1 ) or (Set1*TestSet2 = Set1) or (Set1*TestSet3=Set1);

---

Rien de plus simple !

En fait, il ne faut pas oublier les opérateurs sur les ensembles. Le multiplicateur * permet de calculer l'intersection de deux ensembles. Donc si A*B=A ça veut dire que A est entièrement inclus dans B.

---

Merci, mais ce n'est pas ce que je cherche : sinon il existe quelque chose d'encore plus simple :

if (E<=[1,4,7]) or (E<=[2,5,8]) or (E<=[3,6,9]) then

Ce que je cherche a faire, c'est a CALCULER ces ensembles de référence, c'est a dire par exemple :

Code:

---

1 2 3

Result:=[] for i:=0 to 2 do Include(Result,i*3+1)

---

Mais sans faire ce calcul, plutot en faisant un truc genre [0,1,2]*3+1 de maniere a ce que ca donne [1,4,7]. J'aimerais en fait savoir si il est possible de faire des calculs sur des ensembles ...
Quel est l'avantage ? On peut changer le 3 et le 1 avec les valeurs que l'on veut ...

Citation:

---

Envoyé par Franck SORIANO

Par contre attention, les ensembles sont plutôt lents en Delphi. Il existe un moyen de faire la même chose très facilement et de façon très efficace (j'en dis pas plus... ;)), sans utiliser les ensembles bien sûr...

---

Tu parles d'un champ de bit ?

Un Ensemble (set of) c'est déjà un Champ Bit, chaque bit indiquant si la valeur est présente (256 max sur 32 Octets)

sinon, utiliser le Byte, c'est vraiement un perte de temps ... toutes les opérations sont faites inutiles sur 32 octets contre 2 octets pour 1..9

Code:

---

1 2	type MySet = set of 1..9;

---

au lieu d'avoir des appels de sous méthode d'ensemble, c'est directement du and/or ...

Citation:

---

Envoyé par mick605

L'évolution de tes temps m'étonnera toujours ;) Elle est coriace cette 1ere grille de FullSpeed !!

---

Je suis parti de loin ... si je viens d'ajouter un peu plus de logique, toujours la gestion de base du Sudoku (les candidats uniques comme le 1 en C3, R8 de Escargot), je suis loin d'imaginer vos histoires d'éloignements ou de statistiques auxquelles je ne pige pas grand chose ...

Code:

---

1 2 3 4 5 6 7

1ere : 2.8 ms 2eme : 4.1 ms -> 0.6 ms 3eme : 0.8 ms -> 0.2 ms 4eme : 2.0 ms (AI Escargot) 5eme : 65.4 ms (Easter Monster) 1ère Grille 17 de FullSpeed : 3 396 ms -> 140 ms Dernière Grille 17 de FullSpeed : 9.9 ms -> 7.4 ms

---

Shai
Cela te calmera quand je t'aurais envoyer la doc promise

a =1 1 cycle avec a byte
setbit(a,3) mini 4 cycles

Les bits sont devenus beaucoup trop onéreux;on les remplace sans souci par des 'cardinal' (unsigned 32)

Pour les ensembles il n'y a en a pas qui testeraient pour le sodoku des fois..

Boris

Citation:

---

Envoyé par FullSpeed

Shai
Cela te calmera quand je t'aurais envoyer la doc promise

---

Je n'ai pas besoin d'être calmé, ... je ne crois pas avoir dit grand chose de choquant en parlant d'utiliser un Set de plus petite taille, suffit de lire code ASM généré ... entre un CALL _SetIntersect et un AND, il n'y a pas photo non ?

EDIT : J'avais oublié de mettre un "Result := True", ... Grr ... Mon algo logique finalement résoud les Grilles 17, ... bon à l'attaque des deux autres horreurs !

Code:

---

1 2 3 4 5 6 7

1ere : 2.8 ms -> 0.275 ms 2eme : 4.1 ms -> 0.594 ms 3eme : 0.8 ms -> 0.212 ms 4eme : 2.0 ms (AI Escargot) 5eme : 65.4 ms (Easter Monster) 1ère Grille 17 de FullSpeed : 3 396 ms -> 0.230 ms Dernière Grille 17 de FullSpeed : 9.9 ms -> 0.360 ms

---

Citation:

---

Envoyé par ShaiLeTroll

Un Ensemble (set of) c'est déjà un Champ Bit, chaque bit indiquant si la valeur est présente (256 max sur 32 Octets)

---

C'est pour ca que je lui demandais ;) (voir une discussion de OutOfRange ya environ 1 mois)

Edit : AAAaaaarrrgh ! c'est quoi ca !

J'ai défini un type TChiffre :0..9 . J'ai un autre type : set of TChiffre.

Et quand je fais :

Code:

---

1 2 3 4

for I in C do begin ... end;

---

avec I de type TChiffre et C de type set of TChiffre , i prends toutes les valeurs de 0 a 16 8O :? (la boucle n'est pas effectuée, mais quand meme ! :mur: POURQUOI ca ne s'arrete pas a 9 !! (surtout que cette structure, je l'ai utilisé souvent)

Est ce que c'est plus rapide de faire ca :

Code:

---

1 2 3 4 5 6

for i:=1 to 9 do if i in C then begin     end;

---

Citation:

---

Envoyé par mick605

avec I de type TChiffre et C de type set of TChiffre , i prends toutes les valeurs de 0 a 16 8O :? (la boucle n'est pas effectuée, mais quand meme !

---

TChiffre peut prendre 10 valeurs différentes. Il faut donc 10 bits pour représenter l'ensemble. Delphi l'encode sur un mot de 16 bits, donc lorsque tu fais la boucle, il teste tous les bits du mot pour voir s'il faut faire la boucle ou pas.
Au final c'est très lent, il faut mieux gérer l'ensemble à la main, genre :

Code:

---

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

var Candidats : word; c : integer; begin Candidats := (1 shl 3) or (1 shl 1); // juste une petite init. c := 0; while (Candidats<>0) do begin if (Candidats and 1)<>0 then ... // c fait parti de l'ensemble représenté par Candidats inc(c); Candidats := Candidats shr 1; end;

---

Tu fais juste 1 AND, et 1 SHR. Malheureusement, Delphi ne sait pas enchaîner les calculs, donc il faut aussi faire le test Candidats<>0 et (Candidats and 1)<>0. Mais codé en assembleur, on peut économiser les tests !


En plus de cette façon, la boucle s'arrête dès que tous les candidats ont été traités !

Citation:

---

Envoyé par Franck SORIANO

Citation:

---

Envoyé par Moi !

avec I de type TChiffre et C de type set of TChiffre , i prends toutes les valeurs de 0 a 16 (la boucle n'est pas effectuée, mais quand meme !

---

TChiffre peut prendre 10 valeurs différentes. Il faut donc 10 bits pour représenter l'ensemble. Delphi l'encode sur un mot de 16 bits, donc lorsque tu fais la boucle, il teste tous les bits du mot pour voir s'il faut faire la boucle ou pas.

---

C'est ce que je me disais aussi ! Mais je comprends pas que Delphi qui essaye toujours d'optimiser ait laisser passer ca ... Pour ton idée, je vais me pencher sur la question ... Faut que j'apprenne déja a me servir de tout ca ... Mais je rechigne a le faire, parce que je ne sais pas si ca va vraiment raccourcir les calculs, alors que c'est sur que ca va rendre illisible mon code :?

Mais je reprends la derniere question :

Citation:

---

Est ce que c'est plus rapide de faire ca :

Code:

---

1 2 3 4 5 6

for i:=1 to 9 do if i in C then begin     end;

---

---

Edit : Youhou !!

Ca a du bon de réécrire son code :

Grille 1 : 0,630 ms > 0,236 ms
Grille 2 : 0,990 ms > 0,455 ms
Grille 3 : Prochainement dans les salles
Grille 4 : Prochainement dans les salles
Grille 5 : Prochainement dans les salles
Grille 6 : ??? > 0,210 ms
Grille 7 : ??? > 0,222 ms

LOGIQUE SEULEMENT
Pour les 3 du milieu, je n'ai pas réécrit mon solveur bruteForce, donc pas de résultats ;)
Pour ce qui est des grilles 17, elles ne me posent pas trop de problemes (ce sont les plus rapides a résoudre)

Petit truc aussi : en affichant les étapes, on met seulement 0,1 ms de plus, contre 12 ms avant ;) !

Question basique

Peut-n gérer l'ordre dans un ensemble
par exemple j'ai
[1,4,2,5,3]
[5,1,2,8,7]
et déterminer que le 2 est le troisième élément de chaque ensemble
ou que l'intersection des deux ensembles me donne le 2
Merci
Boris

un Ensemble n'a pas d'ordre en Delphi, puisque ce n'est qu'un Champ Bit indiquant si Element présent ou non présent ... utilise des tableaux ...

Code:

---

1 2 3 4 5 6 7 8 9 10

QueryPerformanceFrequency(frequency64); QueryPerformanceCounter(startTime64);   for i:=1 to 81 do j0:=J0*i;   QueryPerformanceCounter(endTime64); elapsedSeconds := (endTime64 - startTime64) / frequency64; Form1.Caption := FloatTostr(elapsedSeconds*1000000)+ ' µs';

---

Juste pour ce code il me repond entre 0,7 et 1,1 µs
Et chez vous?
Il semble difficile de faire un solveur en moins d'une µ seconde!

En fait mon solveur trouve 1500 Sudoku a la seconde de l'ordre du millième de seconde et j'ai 'serré les boulons'.
Comment faite vous avec les logiques ?
J'utilise D6
Boris

Pour ma part, mon solveur met environ 0.25 MILLIsecondes (ms) et pas MICROsecondes (µs). Les temps que j'ai donné ne sont pas en µs !!

(Pour la grille du début, elle met 0.05 ms 8-) )

Citation:

---

Envoyé par mick605

Pour ce qui est des grilles 17, elles ne me posent pas trop de problemes (ce sont les plus rapides a résoudre)

---

Effectivement, par mon Pseudo "BruteForce" (Méthode Bourrin), c'était la misère mais depuis que j'ai ajouté un peu de logique, comme elles sont faciles, elles sont résolu juste par Logique ... d'où l'amélioration de temps ... tu as raison, la précision Logique \ PathFinding est importante

1ere : 0.275 ms (Brute)
2eme : 0.594 ms (Brute)
3eme : 0.212 ms (Brute)
4eme : 2.0 ms (AI Escargot) (Brute)
5eme : 65.4 ms (Easter Monster) (Brute)
6eme : 0.230 ms (1ère Grille 17 de FullSpeed) (Logique)
7eme : 0.360 ms (Dernière Grille 17 de FullSpeed) (Logique)

Citation:

---

Envoyé par FullSpeed

Il semble difficile de faire un solveur en moins d'une µ seconde!

---

Je suis comme Franck SORIANO , j'ai aussi un temps
d'initialisation de l'algo entre 7µs et 17µs, alors dur de faire moins d'une seule µs ... surtout que l'on commencera à avoir du mal à mesurer les temps, ...

Moi, j'essaye que ça tourne en moins d'une milli-seconde ...

(Pour la grille du début, ça met 0.09 ms pour ma part ...)

Sinon, pour la boucle *i, tu peux aussi donner le type des variables ... cela peut influer, cela fait 0.65µs et quelques pointes à 0.85µs ...

Par contre, dans mes temps, je ne sais pas quoi prendre en compte :
Il y a des calculs qui sont indépendants de la grille ... Est ce que je dois en tenir compte ? Et par exemple, le temps de charger le fichier texte est il pris en compte ? J'en sais trop rien ...

Sinon, je sens que je vais "laisser tomber" le temps pour essayer de résoudre les grilles par la logique ... Parce que je pense que j'arrive dans une zone ou si je veux résoudre par la logique, ca sera plus long que résoudre par brute force ... Mais je me suis lancé le défi de résoudre par logique, donc c'est ce que je vais faire !

Shai > Ouais, en fait les 17, c'est loin d'etre les plus dure niveau logique ... Niveau BruteForce par contre ...

Citation:

---

Envoyé par FullSpeed

Code:

---

1 2 3 4 5 6 7 8 9 10

QueryPerformanceFrequency(frequency64); QueryPerformanceCounter(startTime64);   for i:=1 to 81 do j0:=J0*i;   QueryPerformanceCounter(endTime64); elapsedSeconds := (endTime64 - startTime64) / frequency64; Form1.Caption := FloatTostr(elapsedSeconds*1000000)+ ' µs';

---

Juste pour ce code il me repond entre 0,7 et 1,1 µs
Et chez vous?

---

En fait, avec ce code on mesure surtout le temps nécessaire pour lire les compteurs de performances.
Si j'enlève la boucle, je suis à 0.6 µs, avec c'est 0.7 et avec une boucle jusqu'à 810, c'est 0.9

Citation:

---

Envoyé par mick605

Par contre, dans mes temps, je ne sais pas quoi prendre en compte :
Il y a des calculs qui sont indépendants de la grille ... Est ce que je dois en tenir compte ?

---

Si tu dois les faire à chaque résolution : oui. Si tu peux les faire une fois pour toute, voir même mettre les résultats en constante : Non.

Citation:

---

Envoyé par mick605

Et par exemple, le temps de charger le fichier texte est il pris en compte ?

---

Non, sinon on mesurerait la vitesse des disques plutôt que celle du solveur.

Citation:

---

Envoyé par Franck SORIANO

En fait, avec ce code on mesure surtout le temps nécessaire pour lire les compteurs de performances.
Si j'enlève la boucle, je suis à 0.6 µs, avec c'est 0.7 et avec une boucle jusqu'à 810, c'est 0.9

---

tu as une faible diff, mon écart est bien plus grand

Sans boucle : 0.34 µs à 0.45µs
Boucle 81 : 0.65 µs à 0.85 µs
Boucle 810 : 3.08 µs à 3.32 µs

Ton processeur est plus lent pour le Tick, mais bcp plus rapide pour la multiplication que le mien, ce qui n'est pas surprenant, si tu as un Core 2 Bidule ... leur fréquence étant bcp plus basse que celle des P4 mais leur archi est nettement meilleure ...

Comme je le disais déjà avant, on arrive à la limite théorique de QueryPerformanceCounter qui est de 0.2 µs (200 ns), et sur le P4 3Ghz du Bureau, je suis au mieux à 0.34µs (340ns) aujourd'hui, ça dépend de la météo ... mais parfois, cela grimpe, suffit que le systeme à un truc à faire, et la précision chute ...

Bon, je viens de me rendre compte que cette méthode :

Code:

---

1 2 3 4 5 6

for i:=1 to 9 do if i in C then begin     end;

---

est environ 1/3 plus rapide que :

Code:

---

1 2 3 4 5

for i in C do begin     end;

---

Utilisez donc celle d'en haut ;) . Pour le savoir, je me suis servi d'un logiciel que j'ai trouvé ya pas longtemps : Pour cela, allez faire un tour du coté du forum Outils ;) Je vous le conseille fortement !

Grace au logiciel, j'ai tres légerement réduit mes temps d'environ 5-10 µs.
ya que la grille 2 que j'ai largement amélioré :roll:
455 µs > 370 µs

Mick : tu peux etre plus precis;v et donner le nom et eve,ntuellement l'url
Merci
Le pirate malouin

En D6, la seconde syntaxe n'existe même pas, sinon, les ensembles, j'ai essayé, ben c'est plus lent qu'un bon vieux "array of boolean", en D6 toujours ...