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

**ShaiLeTroll** · 30/07/2009, 19h49

Envoyé par FullSpeed

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

Ben, maintenant, je n'ai vraiement plus de recherche de candidat, j'ai un calcul qui génère les grilles possibles cohérentes en balayant chaque possiblité ... c'est un algo bête* et méchant ...
*pas trop bête non plus, il ne vas pas tenter deux fois la même valeur dans une zone évidemment (c'était la faille de la précédente version qui duraient plusieurs minutes ...)

Pour la mémorisation des positions, je te confirme que c'est ce que j'utilise dans ma Méthode Bourrin (d'où la suppression de la division

), ce que je n'avais pas fait dans la Méthode Logique (avec boucle Col\Row et multiplication), ... c'est pour cela que je repards du Bourrin et que je l'affine par logique ... bon j'avance pas beaucoup, je dois y bosser 2-3h par semaine au bureau ...

En fait, je vais tout bêtement reécrire le tout premier algo de base d'Elimination Logique mais en l'écrivant comme la Méthode Bourrin, je devrais gagner 90% du temps perdu à boucler sur des éléments qui ne sont pas impactés ...

**Franck SORIANO** · 30/07/2009, 20h45

Finalement, en cherchant à optimiser mon algo 2, j'ai pensé à une nouvelle optim pour l'algo 1 :

g1 : 0.0142
g2 : 0.0888
g3 : 0.0164
g4 : 0.0360 (AI-Escargot)
g5 : 0.5882 (Easter Monster)
g6 : 0.0373 (17-1 du zip)
g7 : 0.0508 (17-dernière du zip)

Ce n'est peut-être pas très visible, mais ça donne un gain de 10% une fois sur deux.

**FullSpeed** · 30/07/2009, 22h11

Ce n'est peut-être pas très visible, mais ça donne un gain de 10% une fois sur deux.

Il y a un moment où les % coutent sueur et trannspiration
10 c'est du boulot:

Shai
Pour les docs intel il n'y a pas de souci mais c'est assez succint en realite;:
Instruction Nbr de cycle - latence 1 et 2 et indicateurs. Je vais te faire un scan. Pour les routines de calcul s'est impressionnant: Sur les Nombres premiers tu passes de deux mois à une journée!!!

Boris

Je dois dire que moi comme je ne travaille pas je ne compte pas
mes heures et j'ai du temps

**mick605** · 31/07/2009, 00h48

Bon, je viens de coder une méthode de résolution BruteForce ... Je ne laisse pas tomber la logique, mais je pense que je devrais de toutes facons en coder une ... Il est tres lent, et il bugge souvent ... Normal, c'est vraiment vite fait ... Et j'ai rajouté seulement 42 lignes de code pour la résolution

Pour le temps passé sur le solveur, ben j'ai pas trop de temps ... donc attendez au moins en aout pour la fin du défi

!!

**Franck SORIANO** · 31/07/2009, 20h05

Pour le fun,

j'ai ajusté le paramétrage de l'algo 1 pour qu'il soit le plus efficace possible sur AI-Escargot ! (d'accord, ça s'appelle tricher lorsqu'on détecte le bench).

Ca donne le résultat suivant :
g1 : 0.0614 ms (soit + 0.0472)
g2 : 0.0871 ms ( - 0.0017)
g3 : 0.0249 ms ( + 0.0085)
g4 : 0.0142 ms ( AI-Escargot - 0.0218)

g5 : 0.1025 ms ( - 0.4857)
g6 : 0.1518 ms ( + 0.1145)
g7: 0.0707 ms ( + 0.0199)

C'est marrant de voir que ça n'a pas tellement dégradé les autres grilles, mais que ça a considérablement amélioré Easter Monster !

On commence aussi à voir apparaitre le temps d'initialisation de l'algo : 0.0100 ms !

**FullSpeed** · 31/07/2009, 21h45

Juste pour rire regarder le zip...
Boris

**mick605** · 03/08/2009, 00h10

C'est quoi ? un générateur de grilles 25*25 ? Ca gere... Mais ca doit etre galere a résoudre a la main une grille comme ca !

En tout cas chez moi, les chiffres et les cases sont completement décalées ...

**FullSpeed** · 03/08/2009, 08h58

Oui c'esrt un generateur de griles 25*25
mais pas de problemes.

Ce que tu me dis suir les chiffres est interressant et je l'ai deja rencontre
sans etre capavble de trouver pourquoi

En realite les cases sont des TLabels et le quadrillage est relatif au premier label;
Cela fonctionne parfaitement dans un certzin nombrte de cas mais pas dans tous

Aurais-tu un peu de temps pour regarder car chez moi cela marche.

(Je pense que c'est un problem de grandes polices ou de ce genre

Boris

**mick605** · 03/08/2009, 15h08

Voila ce que ca donne chez moi ! Tu devrais utiliser une StringGrid pour l'affichage ...

La fenetre est également coupée en haut (voir image)

**Paul TOTH** · 03/08/2009, 17h26

pour le fun, voici ma contribution...il est loin d'être parfait, ne résout pas grande chose, mais bien que ce soit une animation Flash il est entièrement codé en Pascal

Sudoku.swf

**Kaféine** · 03/08/2009, 17h50

sympatique !

**mick605** · 03/08/2009, 22h29

Paul Toth > Ca gere ! Tu aurais pu rajouter un bouton pour vider la grille

Tu participes au défi ?

**FullSpeed** · 04/08/2009, 09h29

Je joins un petit projet sous D6
qui affiche une fenêtre et un quadrillage
Cela fonctionne parfaitement chez moi mais il y a des configs ou cela ne fonctionne pas correctement: l'origine de la grille n'est pas bonne
Il ne s'agit pas de contourner mais de compendre pourquoi

Plus il y aura de gens a essayer plus j'ai de chance de trouver la raison
Merci à tous
Boris

Windows XP pack 2
Écran plat LG 19 pouces
Carte Graphique Nvidia

**Paul TOTH** · 04/08/2009, 12h00

Envoyé par mick605

Paul Toth > Ca gere ! Tu aurais pu rajouter un bouton pour vider la grille

Tu participes au défi ?

je ne suis pas certain d'avoir le temps d'implémenter un tant soit peu de méthodes des résolutions par logique...l'approche brutale ne m'intéresse pas

là il se contente de vérifier l'unicité par ligne/colonne/case...ça ne va pas bien loin

**OutOfRange** · 04/08/2009, 12h33

Salut FullSpeed

Voilà ce qui s'affiche chez moi
carte ATI RADEON XPRESS 200 series
xp pack 2
reso 1280x1024

**Félix Guillemot** · 04/08/2009, 16h59

Salut les Sudokumen !

Je rentre de vacances et je viens de lire vos posts depuis mon départ.
Je vois que la tendance est toujours à la compet de vitesse...

Mick n'a pas encore trouvé le Da Vinci Code et Franck terrorise la population avec son chrono...

Petit à petit, on a vu deux types de méthodes s'affronter : logique et force brute, aujourd'hui, elles sont clairement annoncées.

Tout le monde s'amuse en tout cas et ça c'est une réussite

J'ai cru comprendre qu'il y avait une série de grilles de tests (suggérée par Full Speed ?).
ça serait bien de figer cette liste une bonne fois pour toute et de la centraliser.

Tiens, au fait, truc etonnant que j'ai trouvé en cherchant un jour, je ne sais pas si quelqu'un l'a déjà trouvé.
C'est pas simple par écrit.
Je pensais le garder pour moi, mais je vous fait cette révélation, je pense que certains ici vont s'y intéresser

Soit une grille de Sudoku.
Elle est divisée en 9 régions.

ABC
DEF
GHI

Soit d1 la distance entre deux chiffres identiques (c et c') situés respectivement dans les régions A et D
On appelle distance, le nombre de lignes parcourues pour aller de c à c' en comptant les lignes contenant c et c'

Exemple avec des 6 :

1--060050000
2--500000600
3--000600500
4--005000006
5--000506000
6--600000005
7--056000000
8--000005060
9--000060050

Les deux 6 des régions A et D sont éloignés de 6
Les deux 6 des régions B et E sont éloignés de 3
Les deux 6 des régions C et F sont éloignés de 3

La somme des 3 éloignements fait 12

Les deux 5 des régions A et D sont éloignés de 3
Les deux 5 des régions B et E sont éloignés de 5
Les deux 5 des régions C et F sont éloignés de 4

La somme des 3 éloignements fait 12 !

Je prends n'importe quel chiffre, ça fait toujours 12...
ça marche aussi en colonnes...

Ce n'est pas fini :

Les deux 6 des régions A et G sont éloignés de 7
Les deux 6 des régions B et E sont éloignés de 7
Les deux 6 des régions C et I sont éloignés de 7

La somme des 3 éloignements fait 21

Je prends n'importe quel chiffre, ça fait toujours 21...
ça marche aussi en colonnes...

Cette règle part de l'observation que la grille de Sudoku est un système équilibré : il y a une répartition des "masses" par les chiffres.
Si deux chiffres sont proches dans deux régions (A et D par exemple), il est probables qu'ils seront éloignés dans les régions B et E à cause de la règle observée précédemment.
Il y a peut être moyen d'implémenter à partir de cette logique...

En tout cas, je trouve cette observation troublante. Je n'y aurais pas pensé si je n'avais pas regardé le problème différemment, avec un autre oeil ou sous un autre angle, comme vous voudrez...

Et 21 c'est 12 à l'envers...

**FullSpeed** · 04/08/2009, 17h35

Envoyé par OutOfRange

Salut FullSpeed

Voilà ce qui s'affiche chez moi
carte ATI RADEON XPRESS 200 series
xp pack 2
reso 1280x1024

Je pense que s'est un probleme de canvas
Si cela ne t'ennuie pas tu regardes la methode TKillerW.paint
et tu precidse

Code :

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

1
2
 
WITH KILLERW.CANVAS do

Pour essayer de forcer le port graphique. Il ne doit pas avboir le bon sur certaines cartes..

merci

**FullSpeed** · 04/08/2009, 17h57

Pour les grilles
en realite j'ai une collection dont j'ai fournis un extrait

Mais pour tester les solveurs elle ne va pas: toutes les grilles ont les memes dispositions
Il serait peut être intéressant d'avoir un référentiel
qui mélange les difficultés, les dispositions
Le seul défaut est que les grilles sont des 17 teveles
Il faudrait que j'en,recherche d'autres
Mais comme cela n'avait pas l'air d'intercesseur

je ne me sui pas plongé dans mes archives
Boris

**Paul TOTH** · 04/08/2009, 18h24

Envoyé par FullSpeed

Je pense que s'est un probleme de canvas
Si cela ne t'ennuie pas tu regardes la methode TKillerW.paint
et tu precidse

Code :

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

1
2
 
WITH KILLERW.CANVAS do

Pour essayer de forcer le port graphique. Il ne doit pas avboir le bon sur certaines cartes..

merci

oooohh ! c'est quoi un port graphique m'sieur ? en quoi le code que tu donnes le force-t-il ?

**FullSpeed** · 04/08/2009, 20h42

Envoyé par Paul TOTH

oooohh !
c'est quoi un port graphique m'sieur ?
en quoi le code que tu donnes le force-t-il ?

Vieux reliant de Macintosh et de GrafPort!

On doit appeler cela le contexte graphique
par exemple si tu as un ecran cache dans lequel tu veux
dessiner tu diriges tous les ordres vers lui et non vers l'ecran
Pour un objet PC on parle du canvas

Donc poiur dessiner dans une fenetre precises tu dis que tu
vas l'utiliser en précisant Canvas.Pen ou canvas.brush assez classiquement

en utilisant with j'économise l'écriture de
MaForm.Canvas pour chaque ordre graphique

Mais j'ai regarder le code et je crois que je mérite une flagellation en place publique:
Il dessine bien dans la bonne fenêtre le bon quadrillage mais pas au bon endroit: Eh Boris si tu positionnais le crayon avant de t'en servir?
Juste avant l'instruction Rectangle tu ne rajouterais pas un Moveto(0,0)

A mon avis la prochaine tournée est pour moi...

Pour la petite histoire l'erreur n'a pas lieu chez moi sans doute parce que je n'utilise pas les fenêtres Windows de base(Thème dans propriété affichage)
Boris

Si cela intéresse en PJ quelques miliiers de grilles

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

Delphi

Discussions similaires

Partager

Partager