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

**FullSpeed** · 13/08/2009, 10h45

Ayant enfin les mêmes mesure que vous j'ai pu chronométré les exemples
Je vous rappelle que ma solution qualifiée par commodité de brute force n'en est pas un. Il s'agit en réalité de ce que l'on appelle un solveur par contraintes et restrictions
On parle de contraintes pour parler des candidats si ion les a calculés pour la case. Si on parle de uniquement des chiffres(nombre de révélés dans les trois sous ensembles d'appartenance)
Le principe est donc le suivant
je calcule les possibles de la case 1
je positionne le 1 er candidat
je passe alors a la case 2 dont je calcule les candidats en tenant compte de la 1 et je recommence jusqu'à la case 81

Le système recule automatiquement si il n'y a )pas de candidats pour une case. Je croyais cette méthode comme étant la plus rapide mais c'est faux
Par contre je crois que l'implémentation (perfectible surement) est serrée et qu'il sera difficile d'aller SENSIBLEMENT plus vite.
Et on parle bien de millisecondes

Grille 1 : 1,01 millisecondes
Grille 2 : 1.52 millisecondes
Grille 3 : 0.32 millisecondes
EscarG : 0,74 millisecondes
Easte r: 20,0 millisecondes
17-F : 966 millisecondes
17-L : 3.6 millisecondes

Il es sur que le facteur le plus important est le nombre de reveles
Mais il ne fait pas tout comme le montre les deux grilles 17 (moi je les appelle GORDON) Il existe un autre paramètre ,que je tairais pour l'instant, qui entre en ligne
i/e avec la même méthode je passe 17-First de 966 a 550..

Core duo a 2,4 sans treads, D6,XP

Si la routine de calculs des candidats doit rester secrète on peut peut être échanger des chronos pour s'amuser....
Boris

**ShaiLeTroll** · 13/08/2009, 12h44

Je vous rappelle que ma solution qualifiée par commodité de brute force n'en est pas un. Il s'agit en réalité de ce que l'on appelle un solveur par contraintes et restrictions

C'est comme tout le monde, le BruteForce avec restriction ratée durait 21 minutes (des journées si il n'y avait pas eu la restriction ratée) pour First17, avec Restriction Basique -> 4 ms et avec un peu de logique (réduction des candidats), c'est passé à 0.230 ms ... sur P4 3Ghz, D6, XP

Ma Méthode Bourrin c'est exactement ce que tu décrit, voir ICI, ... une simple récursion ...

Le système recule automatiquement si il n'y a )pas de candidats pour une case. Je croyais cette méthode comme étant la plus rapide mais c'est faux

C'était évident, vouloir parcourir entre 60^3 et 54^5 combinaisons possibles, c'est une horreur, même en ajoutant des contraintes qui éliminent 99.99% des combinaisons cela fait tout de même un sacré PathFinding ...

Méthode Bourrin \ + Reduction
1ere : 4.3 ms \ 0.215 ms
2eme : 6.5 ms \ 0.589 ms
3eme : 1.2 ms \ 0.207 ms
EscarG : 3.2 ms \ 2049 ms
EasterM : 94.8 ms \ 63.8 ms
17-F : 48 264 ms \ 0.232 ms
17-L : 14.2 ms \ 0.353 ms

le plus drôle, c'est que ça change, totalement en fonction si l'on a considéré Col puis Row ou Row puis Col dans son tableau ... idem pour le tableau 81, selon sa construction, les temps de recherche s'inverse :

1ere : 35.8 ms \ 0.537 ms
2eme : 7.4 ms \ 0.335 ms
3eme : 1.0 ms \ 0.149 ms
EscarG : 25.2 ms \ 16.5 ms
EasterM : 72.4 ms \ 48.2 ms
17-F : 986 ms \ 0.312 ms
17-L : 1 700 ms \ 0.440 ms

Et l'algo de réduction n'est pas tout à fait optimisé, des itérations inutiles à éliminer ...

**Franck SORIANO** · 13/08/2009, 13h04

Envoyé par FullSpeed

Si la routine de calculs des candidats doit rester secrète on peut peut être échanger des chronos pour s'amuser....

Le problème c'est que les temps sont trop faibles pour être mesurables, et ça ne sert pas à grand chose...

Par exemple, je calcule les candidats de la grille complète pendant l'initialisation de mon algo (+ d'autres choses), le tout en moins de 10 micro secondes.
Ensuite je ne fait plus appel à cette méthode pendant toutes la résolution.
La routine de calculs des candidats a si peu d'effet sur ma solution, que c'est la seule que je n'ai pas chercher à spécialement optimiser...

Envoyé par ShaiLeTroll

Ma Méthode Bourrin c'est exactement ce que tu décrit, voir ICI, ... une simple récursion ...

Le système recule automatiquement si il n'y a )pas de candidats pour une case. Je croyais cette méthode comme étant la plus rapide mais c'est faux

C'était évident, vouloir parcourir entre 60^3 et 54^5 combinaisons possibles, c'est une horreur, même en ajoutant des contraintes qui illimites 99.99% des combinaisons ...

Mon solveur n'est pourtant pas très loin de ça... J'ai juste une subtilité supplémentaire.

**mick605** · 13/08/2009, 13h24

FullSpeed : Le logiciel s'appelle PRo Delphi, j'ai pas le lien sous la main la. Allez sur le forum Outils pour plus d'infos

Franck > Faut pas trop que t'en dises sur ton solveur, ya des trucs qui doivent rester secrets jusqu'a la fin

Shai > En inversant les lignes et les colonnes, tu as réduit tous tes temps ... C'est bizarre non ? Il devrait yen avoir qui augmente ...

**ShaiLeTroll** · 13/08/2009, 14h19

Tient, le sujet Recursivité que j'ai cité précédemment, parle d'une autre Grille difficile "near worst case" (qui est d'une facilité logique effroyable)

Code :

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

Méthode Bourrin \ + Reduction
20 314 ms \ 0.384 ms

Il était fier de ses moins de 5 minutes

, ça va on sauve l'honneur !

si si regarde bien

Code :

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

1
2
3
4
5
6
7
8
9
 
Méthode Bourrin \ + Reduction 
1ere : 4.3 ms \ 0.215 ms     ---> 35.8 ms \ 0.537 ms     === + 31 \ + 0.3 
2eme : 6.5 ms \ 0.589 ms     ---> 7.4 ms \ 0.335 ms      === + 0.9 \ - 0.2
3eme : 1.2 ms \ 0.207 ms     ---> 1.0 ms \ 0.149 ms      === - 0.2 \ - 0.05
EscarG : 3.2 ms \ 2049 ms    ---> 25.2 ms \ 16.5 ms      === + 22 \ + 16
EasterM : 94.8 ms \ 63.8 ms  ---> 72.4 ms \ 48.2 ms      === - 22.4 \ - 15.6 
17-F : 48 264 ms \ 0.232 ms  ---> 986 ms \ 0.312 ms      === + 47 300 \ + 0.80
17-L : 14.2 ms \ 0.353 ms    ---> 1 700 ms \ 0.440 ms    === + 12 \ + 0.9

Ah peut être, que tu n'avais pas compris mon tableau, je donne les temps de la Méthode Bourrin et les temps de la Reduction puis Méthode Bourrin (qui évidemment est plus rapide car moins de candidat), certaines grilles étant résolu juste par logique

**mick605** · 13/08/2009, 14h21

Envoyé par ShaiLeTroll

Tient, le sujet Recursivité que j'ai cité précédemment, parle d'une autre Grille difficile "near worst case" (qui est d'une facilité logique effroyable)

Code :

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

Méthode Bourrin \ + Reduction
20 314 ms \ 0.384 ms

Il était fier de ses moins de 5 minutes

, ça va on sauve l'honneur !

Ouais : pour moi : 0.238 ms ! Comme quoi, la récursivité ne fait pas tout !

Niveau difficulté logique, c'est vraiment simple !

**ShaiLeTroll** · 13/08/2009, 14h30

Mon Algo Bourrin est en Récursif, ce qui n'est pas le cas de la méthode logique, mais ça va le devenir, du moins presque genre A appelle B appelle C qui rappelle A ...

**FullSpeed** · 13/08/2009, 14h37

Quelques chiffres de base:

Sur les 81 case 17 minimum sont révélées
On peut donc dire que l'on a 64 a découvrir
Chaque case pouvant prendre 9 valeurs soit
9^81 valeurs en tout
En réalité quand vous placez des révélés vous diminuez le nombre de candidats par case
Sur 17-Last vous avez une moyenne qui doit se situer au environ de 4,8
Cela vous donnes donc 5^81 combinaisons
Pour info mon solveur fait 12 700 639 essais avant de trouver la soluion

Les contraintes sont par définition bonnes et adaptées: autrement ce n'est pas une contrainte La méthode devient empirique

Shai Il faut faire attention avec le récursif
1- C'est beaucoup plus LENT que l'itératif
5-c'est consommateur de mémoire (si tu as suivi sur un aure site on fait exploser les PC en vingt secondes avec les Tlist et leur tri récursif)
Je dois avoir laissé un code sur ce site concernant le QS non récursif
Mais cela ne doit pas en proscrire l'usage: il faut en connaitre les défauts comme les qualités

Boris

**ShaiLeTroll** · 13/08/2009, 15h44

Mon récursif est très économe en mémoire, et j'utilise une liste chaînée (un truc bien tordu) ... et puis il ne peut pas dépasser 81 niveau d'empilement ...

je devrais pouvoir le passer en itératif assez facilement, je testerais pour voir si c'est plus rapide, mais comme le CALL ne passe qu'un pointeur en paramètre, ça doit pas être énorme ...

**FullSpeed** · 13/08/2009, 17h07

De fait on peut parfaitement contrôler la mémoire
La consommation de memoire étant directement liée au nopmbre de recursions

Pour le CALL il faut quand même savoir qu'un call c'st 4 cycles + 4 du RTN
c'est éventuellement des push. Mais surtout et c'est cela quii coute on appelle le pile ma nager quand on appelle (on empile l'adresse de départ,l es paramètres
on fait le call qui mémorise son adresse dans la pile puis y déclare ses variables locales attention a ta mémoire: ce n'est pas ton paramètre qui bouffe la pile mes tes locales) Et globalement c''est le mécanisme de pile qui coute du temps pas les appels en eux même

On pourrait croire que je suis fâche avec le récursif! On aurait raison: je n'ai jamais réussi a maitriser cette forme de pensée pourtant indispensable dans les jeux comme othello ou puissance 4 J'ai eu toutes les peines du monde a faire un démineur!
Boris

**FullSpeed** · 13/08/2009, 20h34

Envoyé par Félix Guillemot
Et 21 c'est 12 à l'envers...

Je pense avoir retrouve 12 et 21 dans les grilles
mais les non-cartésiens vont encore trouver que la porte n'est ni ouverte ni fermée
Je ne sais pas pourquoi 12 et 21 mais j'ai retrouve les valeurs en fonction du déplacement.
Boris

Il faut combien d'étoiles (ou de plumes) pour avoir une image dans sa signature?

**Andnotor** · 13/08/2009, 23h47

Envoyé par FullSpeed

Il faut combien d'étoiles (ou de plumes) pour avoir une image dans sa signature?

Code :

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

1
2
3
4
5
6
7
8
9
10
11
uses Math;
 
function StarCount :extended;
begin
  Result := Power(SQRT(SQR(9*9) +SQR(81)), 0) -1;
end;
 
procedure TForm1.FormCreate(Sender: TObject);
begin
  ShowMessage(FloatToStr(StarCount));
end;

**mick605** · 14/08/2009, 00h46

Ce qui fait un nombre tres tres grand d'étoiles ... (ou pas) ! Vive l'optimisation !

**FullSpeed** · 14/08/2009, 08h14

Adnotor!
Bis: vive l'optimisation(Power

)

Je suis reparti a chercher les obliges d'un ensemble.
Sans révèler de secret il y a t il une approche préférable?
Boris

**FullSpeed** · 14/08/2009, 09h14

C'est amusant: parmi les 40000 grilles j'en ai pris quelqueunes au hasard

il se trouve que la 17L ,qui pose des problemes aux soilveurs, est en rtealité la seule de la collection

Par curiosité avez vous trouv" pourquoi?

Boris

**ShaiLeTroll** · 14/08/2009, 10h49

Parce que la combinaison de la solution est à la fin de l'arbre ?

**OutOfRange** · 14/08/2009, 11h04

Salut tout le monde

Il semble que la plupart d'entre nous, pour ne pas dire la quasi-totalité on codé une méthode force brute qui balaye la totalité des combinaisons possibles pour en extraire la seule valide...
Et bin pas moi !

En fait je combine hypothèses et résolution logique :
Quand la 1ère résolution logique échoue, je liste les cases à 2 puis 3 candidats et je choisis une hypothèse. Je relance une résolution logique et émets si nécessaire d'autres hypothèses jusqu'à résolution et en cas de grille erronée, si 1 des hypothèses choisies n'est pas la bonne, je fais marche arrière et choisis l'hypothèse suivante (2 par ex pour une case à 2 candidats), etc.
Cette façon de faire me paraissait plus "noble"
ça marche, sauf pour certaine grilles, qui bouclent à l'infini, par ex AIE
Je ne sais pas encore pourquoi
En revanche EM et NWC sont résolues sans pb
Je pense aussi que cette méthode est plus lente, à en croire les chronos annoncés

Damned, je viens de donner la recette pour gagner le défi

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

OUtOfRange > Pour tout te dire, je voulais faire un truc du meme genre que toi, c'est a dire poser une hypothese et resoudre au max, puis poser l'hypothese inverse et résoudre au max, et garder ce qui est commun aux deux grilles ... Je suis d'accord que c'est mieux qu'un brute force ... Mais j'ai laissé tomber parce que je n'avais aucune idée de comment proceder

!

Allez, envoie des chronos !

Edit : Ah ouais, j'avais pas remarqué que les initiales de AI Escargot, c'est AIE ! Je pense que c'est un signe

Envoyé par FullSpeed

C'est amusant: parmi les 40000 grilles j'en ai pris quelqueunes au hasard

il se trouve que la 17L ,qui pose des problemes aux soilveurs, est en rtealité la seule de la collection

Par curiosité avez vous trouv" pourquoi?

Boris

Ils gardent le meilleur pour la fin ...

**OutOfRange** · 14/08/2009, 15h48

Envoyé par mick605

j'ai laissé tomber parce que je n'avais aucune idée de comment proceder

!

La solution que j'ai adoptée consiste à enregistrer les hypothèses successives dans des record, sans oublier bien sûr de sauvegarder la configuration de la grille avant chaque hypothèse pour la récupérer en cas de besoin
ça tient sur 63 lignes !

Envoyé par mick605

Allez, envoie des chronos !

Euh là je sais pas si je dois

Mon solveur c'est pas un TGV, même en pure résolution logique

Pour tout dire, je me suis fixé comme objectif de ne pas dépasser un temps ressenti comme instantané pour l'utilisateur... ça me paraît pertinent par rapport aux consignes du défi donc si ça ne dépasse pas disons 0,2 secondes

J'ai juste essayé de bien gérer les problèmes de mémoire en utilisant des pointeurs pour mes records, ce qui m'a en effet permis de diviser certains temps par 2

En voici quelques uns
17_1 = 1,794 ms logique pure
17_2 = 2,895 ms logique pure
EM = 75,553 ms avec hypothèses
EM2 = 72,758 ms avec hypothèses
NWC = 3,187 ms logique pure

autres exemples (grilles "niveau 9")

Code :

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

= 30,649 ms avec hypothèses

Code :

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

= 30,294 ms avec hypothèses

**mick605** · 14/08/2009, 16h15

Envoyé par OUtOfRange

Euh là je sais pas si je dois
Mon solveur c'est pas un TGV, même en pure résolution logique
Pour tout dire, je me suis fixé comme objectif de ne pas dépasser un temps ressenti comme instantané pour l'utilisateur... ça me paraît pertinent par rapport aux consignes du défi donc si ça ne dépasse pas disons 0,2 secondes

Oui c'est sur, mais franchement, on ne va faire aucune remarque a propos de tes temps, apres tout, c'est loin d'etre le seul but du défi ... Non, c'est plutot si on peut se conseiller, tu vois.

"La solution consiste à enregistrer les hypothèses successives dans des record, sans oublier bien sûr de sauvegarder la configuration de la grille "
Je pense que c'est ca qui est long dans ton solveur par hypotheses, c'est l'enregistrement des grilles : est ce que tu pourrais, par exemple, faire une methode qui "restaure la grille" si on lui dit : enleve cette hypothese ? Si oui, je pense que tu peux gagner beaucoup de temps ... Parce qu'une grande partie des hypotheses est juste normalement. (apres simplification d'une grille, il reste souvent 3-4 candidats par case. Pendant la pose d'hypotheses, ce nombre réduit. 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

) !

Et franchement, tes temps ne sont pas mauvais du tout !

Sinon, tes deux grilles sont bien dures ! Mon solveur logique n'arrive pas a les resoudre ... On verra avec le BruteForce !

Franck > Regarde :

Envoyé par Franck SORIANO

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 !

Tu dis :
"En plus de cette façon, la boucle s'arrête dès que tous les candidats ont été traités !"
Mais le temps qu'on gagne grace a ca n'est il pas perdu avec ce test : "(Candidats<>0)" ? Parce qu'il me parait long a traiter ...

Ca ne serait pas plus rapide ca :

Code :

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

1
2
for V:=0 to 8 do
  if C and (1 shl V) <> 0 then ....

J'ai laisser tomber le type ensemble (set of) !

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

Delphi

Discussions similaires

Partager

Partager