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

**mick605** · 11/08/2009, 12h29

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 :

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

**Franck SORIANO** · 11/08/2009, 13h23

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 :

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
 
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...

**mick605** · 11/08/2009, 14h18

Envoyé par Franck SORIANO

Ca c'est pas difficile :

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
 
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 :

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

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 ...

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 ?

**ShaiLeTroll** · 11/08/2009, 15h02

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 :

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

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 ...

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 :

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

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

**FullSpeed** · 11/08/2009, 17h41

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

**ShaiLeTroll** · 11/08/2009, 18h27

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 :

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

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

**mick605** · 11/08/2009, 19h28

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 :

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

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

(la boucle n'est pas effectuée, mais quand meme !

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 :

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

1
2
3
4
5
6
  for i:=1 to 9 do
  if i in C then
  begin
 
 
  end;

**Franck SORIANO** · 11/08/2009, 23h16

Envoyé par mick605

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.
Au final c'est très lent, il faut mieux gérer l'ensemble à la main, genre :

Code :

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

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 !

**mick605** · 12/08/2009, 01h31

Envoyé par Franck SORIANO

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 :

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

Code :

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

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

!

**FullSpeed** · 12/08/2009, 09h04

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

**ShaiLeTroll** · 12/08/2009, 11h12

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 ...

**FullSpeed** · 12/08/2009, 14h27

Code :

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

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

**mick605** · 12/08/2009, 14h51

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

)

**ShaiLeTroll** · 12/08/2009, 19h09

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)

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 ...

**mick605** · 12/08/2009, 19h18

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 ...

**Franck SORIANO** · 12/08/2009, 19h27

Envoyé par FullSpeed

Code :

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

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

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.

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.

**ShaiLeTroll** · 12/08/2009, 20h37

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 ...

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

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

Code :

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

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 :

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

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é

455 µs > 370 µs

**FullSpeed** · 13/08/2009, 07h51

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

**ShaiLeTroll** · 13/08/2009, 10h20

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 ...

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

Delphi

Discussions similaires

Partager

Partager