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

A toi de faire les mesures ;)

Mais je peux te dire que côté performances, il doit être possible de faire deux fois plus rapide que le for que tu as écrit.

Citation:

---

Envoyé par OutOfRange

autres exemples (grilles "niveau 9")

Code:

---

1 2 3 4 5 6 7 8 9

800000001 000701000 016502930 090030070 400000006 020050010 087403560 000806000 900000007

---

= 30,649 ms avec hypothèses

Code:

---

1 2 3 4 5 6 7 8 9

007000800 830105042 020809030 100000007 080307020 003010400 090502070 005030200 000401000

---

= 30,294 ms avec hypothèses

---

Avec Reduction Logique de Base + Combinatoire, ce sont des grilles faciles !
1ère = 0.212 ms
2eme = 0.650 ms
Problablement à solutions multiples !

Peux importe si Col\Row ou Row\Col ... cela ne change pas grand chose

Citation:

---

Envoyé par ShaiLeTroll

Avec Reduction Logique de Base + Combinatoire, ce sont des grilles faciles !
1ère = 0.212 ms
2eme = 0.650 ms
Problablement à solutions multiples !

---

Non, solution unique pour les deux ! Meme remarque que toi, c'est pour ca que j'ai vérifié ... Combinatoire = Brute Force non ?

Voila, en supprimant les types sets of !!

Grille 1 : 0,236 ms > 0.184 ms
Grille 2 : 0,455 ms > 0.268 ms
Grille 3 : Prochainement dans les salles
Grille 4 : Prochainement dans les salles
Grille 5 : Prochainement dans les salles
Grille 6 : 0,210 ms > 0.197 ms
Grille 7 : 0,222 ms > 0,201 ms

Citation:

---

Envoyé par mick605

Donc je dirais que la moitié des hypotheses posées sont justes , donc la moitié de tes grilles sauvées n'ont pas besoin de l'etre :ccool: ) !

---

Oui sûrement
Le pb est que lorsque j'émets une hypothèse, par définition, je ne sais pas si cette hypothèse est la bonne :?
Supposons une case avec 2 candidats 7 et 8 ça fait donc 2 hypothèses
Supposons que toutes mes hypothèses successives jusque là soient les bonnes
Si je choisis 7 pour cette case et que la bonne valeur est 8, si je n'ai pas sauvegardé ma grille avant ce choix erroné, je ne peux pas revenir à cette dernière configuration correcte. Il faudrait alors reprendre depuis le début :aie:
Je n'ai donc pas d'autre solution que de sauvegarder toutes les grilles :(

Mon cher OutOfRange

Ton amour immodéré du choix entre deux valeurs a 50-50 t'a conduit vers des des choux cornéliens: 7 ou 8? Rassures toi je ne te donnerais pas une démarche qui tue pour les hypothèses: je la garde pour moi.
Par contre quand tu poses tes hypothèses tu n'as AUCUN besoin de SAUVEGARDER la situation.
On partage tout les deux un élément d'IHM identique. Sers-t-en!
Pour info quand tu dois faire une hypothèse il ne faut pas te soucier du nombre de candidats des cases: En réalité plus ta case a de candidat plus son importance est grande :ccool:

Boris

Citation:

---

Envoyé par OutOfRange

Oui sûrement
Le pb est que lorsque j'émets une hypothèse, par définition, je ne sais pas si cette hypothèse est la bonne :?
Supposons une case avec 2 candidats 7 et 8 ça fait donc 2 hypothèses
Supposons que toutes mes hypothèses successives jusque là soient les bonnes
Si je choisis 7 pour cette case et que la bonne valeur est 8, si je n'ai pas sauvegardé ma grille avant ce choix erroné, je ne peux pas revenir à cette dernière configuration correcte. Il faudrait alors reprendre depuis le début :aie:
Je n'ai donc pas d'autre solution que de sauvegarder toutes les grilles :(

---

Ben justement, il faudrait qu'a partir de la grille avec hypothese, tu puisses retrouver la grille sans hypothese ...

Citation:

---

Envoyé par OutOfRange

si je n'ai pas sauvegardé ma grille avant ce choix erroné, je ne peux pas revenir à cette dernière configuration correcte(

---

La sauvegarde de la grille peut être ultra-rapide et dépend uniquement de la façon dont tu codes tes cellules ;). C'était ma première approche et je n'étais que ~0.8 ms plus lent sur AIE.

Mon cher FullSpeed

Citation:

---

Par contre quand tu poses tes hypothèses tu n'as AUCUN besoin de SAUVEGARDER la situation.
On partage tout les deux un élément d'IHM identique. Sers-t-en!

---

Je ne vois vraiment pas... peut-être à cause de l'heure avancée ;)

edit_________________________

Citation:

---

Envoyé par Andnotor

La sauvegarde de la grille peut être ultra-rapide et dépend uniquement de la façon dont tu codes tes cellules . C'était ma première approche et je n'étais que ~0.8 ms plus lent sur AIE.

---

Je ne sauvegarde pas des cellules de grille mais des set of (et oui j'ai choisi les ensembles dès le début pour les opérations qu'ils permettent et même si je pense de plus en plus que ce n'était pas le bon choix question rapidité je ne vais pas tout refaire maintenant) :aie:

Citation:

---

Envoyé par Andnotor

je n'étais que ~0.8 ms plus lent sur AIE

---

Je n'ai donné aucun temps pour AIE, vu que pour l'instant je ne la résioud pas !

Citation:

---

Envoyé par OutOfRange

Je ne sauvegarde pas des cellules de grille mais des set of

---

Alors c'est là où tu perds du temps. Sauvegarder/restaurer la grille complète serait plus rapide.

Je n'ai pas donné de temps non plus, mais juste que ~0.8ms de différence pour ce défi me paraissait négligeable ;).

Salut les passionnés du chrono...

Juste un détail : quand on départagera la partie rapidité (parce que quand même, on va bien prendre en compte ce critère :mouarf:), no choisira un set de grilles diverses genre que personne n'a fait : pas de AIEscargot, etc.
Sinon c'est trop facile, certains vont orienter leus algos en fonction des grilles pour "concilier".
Je vous dis ça parce que je vous lis...

Une chose aussi : vous semblez souvent opposer les méthodes entre elles...pourquoi ne pas le combiner ? La méthode est un ensemble de méthodes.

Je dis ça, je dis rien...

Je ne pense pas que l'o, oppose les méthodes. On a choisi au hasard en fonction de nos caractères...
Tout le monde essaye d'avoir l'implémentation la plus satisfaisante et a la fin on verra quelle est, entre autre, la pus rapide.On sera sur que les autres méthodes ont été implémentées avec sérieux.
Mais comme je le disait a Frank même la version la plus rapide sera optimisable : Deux personnes qui regardent le même objet ne voient pas la même chose
(Sauf les jumeaux mais c'est un autre debat) Je travaille sur les ecarts moyen mais je n'ai pas encore trouvé comment m'en servir...

Boris

Citation:

---

Envoyé par Félix Guillemot

Une chose aussi : vous semblez souvent opposer les méthodes entre elles...pourquoi ne pas le combiner ? La méthode est un ensemble de méthodes.

---

Exactement, j'ai commencé par un algo logique qui s'est vu limité à une résolution des grilles "faciles" et "moyennes", ensuite, je suis passé à la Méthode de Bourrin par Combinatoire (ou Brute Force pour ceux qui ont amené ce terme, même si cela me semble usurpé...), j'ai réussi à joindre les deux ... maintenant, je dois réécrire la phase logique pour réduire le nombre d'itération,, j'aimerais que les deux méthodes soient lancé par la même méthode de récursion (même si les CALL ralentissent, c'est plus la gueule du code qui m'intéresse dans ce cas)

Pour afficher mon sudoku j'utilise 81 Labels
Après les avoir fabriqués dans l'EDI je les range dans une table de labels ainsi;

Code:

---

1 2 3

for j := 1 to 81 do ST[j] := TLabel(generew.FindComponent('St' + inttostr(j)));

---

Mes labels s'appellent st2,st2,st3...
Cela fonctionne mais n'est pas très propre
aussi je voudrais n'en créer qu'1 dans ma forme
puis de faire 80 instances du premier

Je ne me souviens plus de la syntaxe

Code:

---

1 2	St[1]:=TLabel(Create(St1));

---

Mais j'ai un stack overflow

Merci
Boris

Hey, de retour de vacances !

Bon ben ca avance je vois ... Pour ma part je vais me lancer dans le brute force !

FullSpeed > Aucune idée :oops: ... Ah si ... StringGrid ?? :mrgreen:

Ilm est couirant en informatique de manipuler des champs de bits et sprecioalemen,t en Pascal avec les ensembles
Qur ce tread Franck et Shai on donné des pistes
C'est incontestablement la methode de Franck qui est la plus rapide
Mais pourquoi.

La raison est simple: avec une boucle de 0 a 312par exemplme vous allez parcourir 32 fois la boucle quelque soit la valeur testée
Avec la méthode de Frank vous arrêtez la boucle des que vous n'avez plus de bits positionnés ainsi votre valeur est 1 vous ne ferez qu'un teste alors que la boucle en fera 32

Une seule modification semble opportune sur le code: le remplacement du hile par un repeat

Code:

---

1 2 3 4 5 6 7 8

A00:=85; // on choisi une valeur quelconque I02:=0; repeat if odd( A00) then Inc(A01); A00:=A00 shr 1; Inc(I02); // pour avoir la valeur until A00=0;

---

La raison n'est pas de logique mais de hard: le responsable est le prédicateur de branchement

A chaque itération le pipe lne va généré un defaut de prédiction car il aura
décide de faire un while au lieu du traitement. En se rendant compte de l'erreur il va vider les étages préparatoires et recommencer

C'est pratiquement la seule possibilité ogfterte au programmeur d'influer sur les prédictions.
Comment ca marche?

En réalité dans le pipoe line on surveille les instruction JMP,JZ,JNE..; les branchements
Ensuite on regarde dans quel sens va le saut JMP+X ou JMP -X
Seuls les sauts arrière sont retenus. On regarde alors leur portée; si elle est faible le prédicateur considère que l'onn est dans une boucle et que donc on va prendre ce saut

Avec un while le test se trouve en tète de votre code avec un saut arriere de petite portée aussi le prédicateur va le prendre
mais il aura faux car il faut effectuer le code du while

Le gain n'est pas automatique ni systematique mais cela ne coute
rien de mettre des repeat

Boris

Désolé pour les fautes et les envois intempestifs mais la maladie est spécialement active aujourd'hui

FullSpeed > Est tu sur que cette méthode est plus rapide ?

Parce que, prenons le cas ou la valeur vaut [1]. Avec le test a Franck, on va tester la premiere valeur (1 action), puis on va tester si la valeur vaut 0, et donc on va passer tout les bits pour voir si chaque bit vaut 0 ... (32 actions)
On arrive avec 33 actions, tandis que passer tout les bits une fois et verifier ceux qui sont "allumés" ne prendrait que 32 actions ...

Prenons le cas ou la valeur vaut [2,3] Avec le premier test, on teste la premiere valeur (1 action), on teste si c'est nul (on va dire 32 actions, meme si je pense qu'il y en a bcp moins), on teste la deuxieme valeur (une action), on teste si c'est nul (32 actions), et donc on finit avec 66 actions, contre 32 en passant tout les bits ...

C'est pour ca que je pense que cette méthode est plus lente. Apres, si quelqu'un veut bien se donner la peine de faire des mesures ... (en tout cas, je ne changerai pas mon code, question de lisibilité)

Frank pourrait te repondre mais il doit etre en vacances....

Tu te trompes sur le nombre de test

Code:

---

1 2 3 4 5 6 7 8

A00:=85; // on choisi une valeur quelconque I02:=0; repeat if odd( A00) then Inc(A01); A00:=A00 shr 1; Inc(I02); // pour avoir la valeur until A00=0;

---

Si tu prend A00=1 000000000000000001

epeat
if odd( 1) then Inc(A01); <======== C'est le cas
A00:=A00 shr 1; <===== A devient 0000000000000
Inc(I02); <= tu dis une foid
until A00=0; <=== c''st le cas tu sors

Tu n'as fait qu'un serul test pour une valeur en 32 bvits

Maintenant A00:= 1000000000100
repeat
if odd( 1) then Inc(A01); <======== C'est pas e cas
A00:=A00 shr 1; <===== A devient 10000000001
Inc(I02); <= tu dis une foid
until A00=0; <=== c'e'stpas le le cas

A va prendre les valeurs suivantes:
100000000010
10000000001
1000000000
100000000
..
10
1
0

Tu n'auras fait que 13 indurations au lieu des 32
Le chrono est neutre et il donne le replat vainqueur sans discussion
Pour le sodoku la différence est petite du fai que les e,nsembles font 8
donc on gagne peu mais on gagne surtout que plus tu avances dans ta résolution moins tu as de candidats

on peut ruser un petit peu avec un test

si par exemple tu a seulement le 9 donc A00= 100000000

Code:

---

1 2 3 4 5 6 7 8

A00= 100000000 repeat if odd( A) then Inc(A01); <======== C'est pas e cas A00:=A00 shr 1; <===== A devient 10000000001 Inc(I02); <= tu dis une fois de plus until A00=0; <=== c'e'stpas le le cas

---

Il est plus rapide de commencer à 9 et d'arriver à 1
on remplace le shr par un shl et le tour est joué
pour ne pas pénaliser a00=1 il suffif d 'un test

Code:

---

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

A00= 100000000 if A00>254 then // le bit 9 begin // de gauche a droite :deuxieme ruse de breton A00 est sur 32 bits mais on veut le neuf A00:=A00 SHL 32-8 repeat if odd( A) then Inc(A01); <======== C'est pas e cas A00:=A00 shl 1; <===== SHL Inc(I02); <= tu dis une fois de plus until A00=0; <=== c'est pas le le cas end else begin // de droite à gauche repeat if odd( A) then Inc(A01); <======== C'est pas e cas A00:=A00 shr 1; <===== A devient 10000000001 Inc(I02); <= tu dis une fois de plus until A00=0; <=== c'est pas le le cas end;:

---

C'est cela l'optimisation pas d'astuce spécifique mais une étude précise des données et de leur flux

Moi j'ai fini mon 'brute force' et je suis pasé au logique
cela me rappelle quelqu'un avec des StringGrids

Boris

Salut,

Je participe a ce defi mais avec lazarus dans la section pascal. Je viens de finir la premiere version de mon programme, de ce fait j'aimerais savoir si mon algo peut resoudre les grilles les plus compliquees du monde. J'aimerais donc savoir si vous avez des liens ou je peux trouver de telles grilles.

Autre chose, comme j'ai fait mon programme en poo pure, je me demande finalement si une version procedure ne sera pas plus rapide, parce que si on doit compter en plus le temps de creation et de destruction des classes, aussi l'appel multiple des methodes, je me dis que la poo sera pas beaucoup plus lente.

Aussi, je vois que vous utiliser de l'assembleur dans vos code alors je me demande, celui qui introduit de l'assembleur dans son code pour l'optimisation ne sera pas penalise par rapport a celui qui programme en pascal pur.

Bonjour.

Pour ce qui est des grilles, de nombreuses ont été données au fil des pages de ce topic, notamment en page 2.

Pour ce qui est de l'assembleur nous ne prévoyons de pénaliser ceux qui l'utilisent par rapport à ceux qui ne l'utilisent pas dans le principe. Néanmoins, encore une fois, la vitesse d'exécution ne sera pas un facteur déterminant le choix du vainqueur.

Note cependant que le défi Pascal n'est pas mutualisé avec le défi Delphi (même si c'était voulu qu'on lance le même sujet ;)). Le défi Pascal suit ses propres règles qui ne sont peut-être pas forcément les mêmes que celles du défi Delphi. Je t'invites à te rapprocher de l'équipe Pascal pour plus de renseignements. ;)