Discussion :

[FullSpeed]

Bonjour à tous
Je suis tombé par hasard sur votre défi , defi que je m'etais
lancé il y a quelque temps (2007) , je ne suis ni un pro du sudoku ni de la
programation, mais je crois que le resultat tiens la route. si quelqu'un veut la
macro excel pour test, je la lui fait parvenir.
cette macro peut resoudre en moins d'une demi seconde ( temps que j'estime
désoé je n'ai pas de chrono) tout type de grille 9x9.

p

Si les organisateurs sont d'accord je veux bien te faire le portage en delphi
Moi je trouve sympa la macro excel!
je fais marche ton code en delphi c'est tout pour le reste tu assures
Boris

[ShaiLeTroll]

Fondammentallement, résoudre une grille de Sudoku, ce n'est rien d'autre qu'un problème de recherche de chemin dans un graphe.
Si tu prends directement le bon chemin, tu trouves la solution très rapidement. Si tu prends de multiples détours, les perfs s'effondrent.

Tout à fait, rien qu'en inversant le parcours Col\Row -> Row\Col sur mon algo qui cherche toutes les combinaisons jusqu'à en trouver une bonne pour Escargot AI, eh bien ça passe de 106ms à 1929ms ... juste question de chance ...

[mick605]

p

Si les organisateurs sont d'accord je veux bien te faire le portage en delphi
Moi je trouve sympa la macro excel!
je fais marche ton code en delphi c'est tout pour le reste tu assures
Boris

Euh ... C'est pas terrible comme idée :
C'est comme si vous travaillez a 2, sauf que le défi est (si je ne me trompe pas) individuel. Parce que FullSpeed pourrait s'inspirer des idées de Loulo92, et Loulo92 ne ferait pas tout le défi, mais que la partie algo ...

Ensuite, si Loulo92 ne veut pas participer, ca serait bien qu'il nous montre son solveur apres le défi ...



ShaiLeTroll > C'est vrai qu'il y a souvent une grande part de chance ...

[Franck SORIANO]

Si les organisateurs sont d'accord je veux bien te faire le portage en delphi
Moi je trouve sympa la macro excel!
je fais marche ton code en delphi c'est tout pour le reste tu assures

Euh ... C'est pas terrible comme idée :
C'est comme si vous travaillez a 2, sauf que le défi est (si je ne me trompe pas) individuel. Parce que FullSpeed pourrait s'inspirer des idées de Loulo92, et Loulo92 ne fairait pas tout le défi, mais que la partie algo ...

En effet, je ne vois pas l'intérêt non plus.

Loulo92, si tu veux participer, tu dois porter ta solution en Delpih toi-même. Sinon, une fois le défi terminé, tu pourras effectivement poster ta solution pour ceux qui le souhaitent.

[Franck SORIANO]

Allez, derniers chronos :

Grille 1 : 0.0142 ms
Grille 2 : 0.0997 ms
Grille 3 : 0.0162 ms
Ai-Escargot : 0.0399 ms

On peut encore optimiser, mais je vais m'arrêter là.

[FullSpeed]

C'était juste pour donner un coup de main a Loulo92 pour passer sous Derlphi

Ne t'inquiètes pas Mick pas besoin des idées des autres pour
t'enrhumer: mon problème est plutôt de savoir si tu vas pas nous faire une attaque... ...
Enfin consoles toi : tu as le soleil
Je pense vous donnez des chronos aujourd'hui : je suis perdu dans les micros et mili secondes mais mon fils est la il va me dire. C'est parfois très dur d'avoir le cerveau malade. Pour des micros seconde on divise les secondes par 10 000 ou 100 000?

Frank our la vitesse c'était bien le sens de ma question: on ne trouve pas de méthodes qui permette de limiter le nombre de chemin ou a en imposer un.(Si tu veux une méthode pour générer des grilles vides rapidment demande
Boris

[Franck SORIANO]

Pour des micros seconde on divise les secondes par 10 000 ou 100 000?

Plutôt par 1 000 000.

...une méthode pour générer des grilles vides rapidment ...

Ca c'est vraiment pas compliqué

[FullSpeed]

J'ai donc multiplier paer 1000000

Code :

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

1
2
3
4
5
6
7

  QueryPerformanceFrequency(frequency64);
  QueryPerformanceCounter(startTime64);
  Boris_Solver(pb);
  QueryPerformanceCounter(endTime64);
  elapsedSeconds := (endTime64 - startTime64)*1000000/frequency64;

Et pour Escargot j'obtiens

391,403472900391 donc a priori 391 microsecondes
soit beaucoup plus que les logiques.
Boris

[Kaféine]

Grille 1 : 0.0142 ms
Grille 2 : 0.0997 ms
Grille 3 : 0.0162 ms
Ai-Escargot : 0.0399 ms

On peut encore optimiser, mais je vais m'arrêter là.

Impressionnant ces chronos ! j'en ai la chair de poule...

Allez vas y continu l'optimisation, j'adhère à ton fan club

[Franck SORIANO]

J'ai donc multiplier paer 1000000

Code :

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

1
2
3
4
5
6
7
  QueryPerformanceFrequency(frequency64);
  QueryPerformanceCounter(startTime64);
  Boris_Solver(pb);
  QueryPerformanceCounter(endTime64);
  elapsedSeconds := (endTime64 - startTime64)*1000000/frequency64;

Et pour Escargot j'obtiens

391,403472900391 donc a priori 391 microsecondes
soit beaucoup plus que les logiques.
Boris

C'est bien ça. Donc tu résouds AI-Escargot en 0.3914 ms.

soit beaucoup plus que les logiques

Tu veux dire beaucoup moins que les logiques non ?
Tous ceux qui ont annoncés des temps avec un solveur logique étaient à plus.

Allez vas y continu l'optimisation, j'adhère à ton fan club

Le problème maintenant c'est que toutes les optims auxquelles je pense passent par de l'assembleur, ou sont complètement illisibles ou inconpréhensibles.
Mais il y aurait moyen de gagner pas mal à coups de SSE. Quand on peut faire 16 calculs en parallèle en une seule instruction ça accélère forcément.

[FullSpeed]

Moins vite c'était que toi: pour moi tu as un logique.
Mais je me trompe peu être?

Moi se qui m'interresse en realité c'est qu'une fois le défis fait on pourra s'amuser a échanger nos codes: moi je parie que tu amelioreras le mien et que j'amélliorerai le tien.
C''est pour moi l'optimisation est un probleme d'imagination et de vécu et deux individus on forcement imagination et vecu propres

(Serieux ton million de grilles en 3 secondes c'est quand meme balaise
meme si je me moques gentiment)

Boris

[ShaiLeTroll]

Je ne joue pas dans la même catégorie que vous pour les Chronos, mais j'avance, j'ai pris une grille nécessitant une Méthode Bourrin (Essaye tous les chemins cohérents possibles) après la Résolution Simple (elimination des candidats par logique), je l'ai faite à la main, et j'ai trouvé 2 idée d'algo (en fait des techniques humaines d'une simplicité !) je viens d'implémenter la première idée

P4 3Ghz
1ere : 430 ms -> 63 ms
2eme : 44 ms -> 7 ms
3eme : 9 ms -> 1.3 ms
je parle en millisecondes ... et non en µs ...

Pour "AI Escargot" et "Easter Monster", cela ne change pas grand chose, ... il faut implémenter la 2eme idée pour que cela avance ...


EDIT : j'ai affiné ma Méthode Bourrin avec les nouveautés ajouté dans la Résolution Basique ...

1ere : 430 ms -> 63 ms -> 7 ms
2eme : 44 ms -> 7 ms -> 3 ms
3eme : 9 ms -> 1.3 ms -> 0.7 ms
4eme : 1 860 ms -> 5.8 ms (AI Escargot)
5eme : 12 360 ms -> 169 ms (Easter Monster)
1ère Grille 17 de FullSpeed : 12 minutes -> 226 ms
Dernière Grille 17 de FullSpeed : 25 minutes -> 15ms

Vous notez que la 1ère est plus lente à résoudre ... que AI Escargot, une histoire de chance, ... la grille de solution se trouve plus tôt dans l'arbre que pour celle de la 1ère ... toujours l'histoire du Lucking Path Finding !

Le plus drôle, c'est quand je désactive la Résolution Basique en lançant la Méthode Bourrin directement

Résolution Basique + Méthode Bourrin \ Méthode Bourrin
1ere : 7 ms \ 10 ms
2eme : 3 ms \ 14 ms
3eme : 0.7 ms \ 3 ms
4eme : 5.8 ms \ 7 ms (AI Escargot)
5eme : 169 ms \ 207 (Easter Monster)
1ère Grille 17 de FullSpeed : 226 ms \ 10 613 ms
Dernière Grille 17 de FullSpeed :15 ms \ 31 ms

Les Temps ne sont pas très éloignés, sauf dans un cas ... c'est tout de même bien étrange ...

EDIT 2

J'ai débarrassé mon code de toute l'approche logique et aussi des artifices que je trouvais sympa qui était possible avec l'approche logique et réduit au strict minimum à la Méthode Bourrin (finalement pas si Bourrin), c'est elle que j'ai vais affiné à partir de maintenant ...

[Franck SORIANO]

C'est bien, c'est un net progrès !

Nouvel algorithme, la recherche du chemin est basé sur des statistiques :
Grille 1 : 0.0957
Grille 2 : 0.0508
GRille 3 : 0.0194
AI-Escargot : 0.1131

En principe, avec cet algo, les perfs devraient surtout dépendrent du nombre de révélés.
Cette version n'est pratiquement pas optimisée !

[ShaiLeTroll]

Tu veux rire encore, ... je viens de diviser les temps par deux, juste en n'utilisant pas l'opérateur diviser

1ere : 4.3 ms
2eme : 9.4 ms
3eme : 1.4 ms
4eme : 3.3 ms (AI Escargot)
5eme : 92.2 ms (Easter Monster)
1ère Grille 17 de FullSpeed : 4 612 ms
Dernière Grille 17 de FullSpeed :13.9 ms

Reste à apporter une touche de logique à cette Méthode Bourrin pour espérer réduire un peu les temps ... la clé étant de savoir à quel moment, il est inutile de continuer ...

J'ai de la marge ... j'ai encore en moyenne bon facteur 100 par rapport au temps de Franck SORIANO ... en fait rien que l'initialisation de mon arbre et sa libération durent déjà 100µs (0.1 ms) donc aussi long que toutes la résolution AI-Escargot ... je me demande ce que tu as écrit comme code pour avoir une telle rapidité, j'avoue, je n'y comprends rien !

Franck SORIANO, on pourrait avoir tes temps sur Easter Monster, et sur les Grille 17 de FullSpeed, pour comparer ...

EDIT
Pour Mémoire
1ere à 4eme Grille : Voir ICI
5eme Grille : Voir ICI
Grille 17 de FullSpeed : Voir ZIP

[Franck SORIANO]

Tu veux rire encore, ... je viens de diviser les temps par deux, juste en n'utilisant pas l'opérateur diviser

Tu peux faire la même chose en évitant les multiplications.

Bon, si tu veux tous mes temps, ça donne (avec l'algo 1, optimisé) :

g1 : 0.0143
g2 : 0.1020
g3 : 0.0161
g4 : 0.0403 (AI-Escargot)
g5 : 0.6474 (Easter Monster)
g6 : 0.0428 (17-1 du zip)
g7 : 0.0520 (17-dernière du zip)

[FullSpeed]

Je vois que vous utilisez les exemples 17 qu zip
Il faut faire attention car en realite les grilles sont TRIEES
et vous n'avez que les premières dispositions: révélés en bas
mais dans les dernières c'estr l'inverse
Ainsi la collection n'est pas aleatoire'e et pour rechercher des
des causes de ralentissement dans les grilles il ne faut pas se baser dessus de trop

SI vous le désirez, le fichier fait 6 mégas, je peux vous faire un extrait
plus représentatif. J'ai les outils pour le faire mais il faut que cela
intéresse

Boris

[FullSpeed]

Shai

Tu veux rire encore, ... je viens de diviser les temps par deux, juste en n'utilisant pas l'opérateur diviser

Le remplacement des operateurs est une des premières optimisations:
Les deux ennemis de la vitesse sont le div et le mod( s'est pareil=
En prenant les docs intel on le voit tout de suite

En fait les temps sont ceux la
Divi Mod 60
Mult 02
Add Sub 01

pour vérifier

Code :

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

1
2
3
4
5
 
for :=1 to 100000 do
 z= Random(i)+i
for :=1 to 100000 do
 z= Random(i)*i

tu prends les temps et tu regardes!
Autre technique
Tu remplaces tes boucles par des repeat:
Le prédicateur de branchement sera heureux et un repeat
fait n test là où un for en fait n+1

Un autre ennemi juré est le STRCopy : a=b est d'une lenteur sénatoriale
Aller tant qu'on y ait: autre ennemi jure ( calcul des candidats...)
le Concat. Tu essayes

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
 
A: string;
A:='';
for i:=1 ro 100 do
  if odd(i) then A:=A+Chr(I);
////////////////////////////
A[0]:= Chr(255);
J:=0;
I:=1;
Repeat
  if odd(i) then 
   begin
    inc(j)
    A[j]:=chr(i);
   end;
inc(i);
until I>100;
A[0]:= Chr(j);

Surprise. C'est le concat est le responsable: il appelle le memory manager...

Par contre l'inversion des boucles n'est pas utile: le compilateur le fait tout seul et très bien
Shai: tu te souviens du tri? Très utile....

Frank j'ai jeté un œil moi aussi sur les SEE et j'ai étudie quelques codes d'optimisation

Le SEE ne semble valable que si une de tes vatiables fait au moins 16 caractères ou alors il faut peut etre maitriser parfaitement
Les routines prennent le soin de tester la longueur et il y a au moins deux traitements>16 et <16 Pour le Sudokua mon avis c'est trop

Boris

PS: c'est etrange la premiere balise QUOTE ne fonctionne pas????

[Edit Cl@udius]
[QUOTE]Texte... [/quote]

[ShaiLeTroll]

Pour le QUOTE, mets les deux dans la même casse ...

Sinon, la division, oui je savais que c'était lent, ... Je n'ai pas de multiplication dans le code critique, juste à la fin dans la procédure de contrôle ...

Pour le Concat de String, tu peux chercher, ma fonction Explode est conçu pour ce problème avec l'agrandissement de tableau (aussi lent que l'agrandissement de chaine), ou ma fonction ReduceStr ... mais c'était bien valable pour D6 ... mais depuis que le Memory Manager a changé, le temps de réallocation des tableaux dynamiques a été divisé facilement par 100 ...
Mais comme je n'utilise pas de String, je sais qu'il n'y a rien à changé la dessus ...

l'optimisation de mon code doit passer par une réduction des candidats possibles ... je dois reprendre ma Méthode Logique et réduire le nombre de balayage dans le tableau, je refaisais bêtement toute la grille, alors qu'il suffit de balayer les zones affectées par la dernière résolution, rien que cela devrait améliorer ...

[FullSpeed]

Quand je vois le mot dynamique je m'enfuie en courant..
Bonjour le memory manager!
Mais c'est parfois bien utile surtout quand on n'aime pas la recursion.

Sans voir ton code : la routine qui coute cher c'est la recherche de candidat

On va peut être m'accuser de favoritisme (j'aime bien Shai) mais pour les recalcules il faut avoir mémorisé pour chaque case sa colonne, sa rangee et sa région et tu ne remets a jour que ces cases la ... Tu vas beaucoup plus vite mais c'est moins bien de passer de 1 à 81. Quand on valorise une case en réaliité cela influe directement sur 25 cases mais sur 55 indirectement(voir trio..
Je n'ai jamais mesure l'impact exact sur le résolution
Boris

UIn boulot d'avenir: correcteur de fautes de Boris...

[mick605]

Sans voir ton code : la routine qui coute cher c'est la recherche de candidat

J'ai une idée pour ca que j'ai mis en place dans mon code logique, et qui fonctionnerait super bien en brute force ! Je vous la donnerai apres le défi !

Pour l'histoire de mod et div ... FullSpeed, pourrais tu me donner les "docs intel" ?? Qu'est ce que c'est exactement ? Ca pourrais m'interresser ... bien que je ne sois pas sur de modifier mon code ...