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

bonjour le vacancier

Quand je parles de génération de problèmes il faut pouvoir donner
le nombre de révélés et ou le niveau de difficulté. A priori personn ne l'a fait: sauf toi peut etre

Le GROS probleme c'est que chacun cree ses propres niveaux de dfficulté en fonctiuon de ses criters. Il n'y a pas de regle.
Nous en avions déjà parle la réalisation est assez simple c'est l'automatisation qui pose problème


Mais bonne nouvelle: tu as ecris un générateur? C'est hors sujet! Un candidat de moins:ccool::ccool:

Boris

Citation:

---

Envoyé par FullSpeed

Mais bonne nouvelle: tu as ecris un générateur? C'est hors sujet! Un candidat de moins:ccool::ccool:

---

Euh ... pas du tout ! Il ajoute ses propres fonctionnalités !

D'ailleurs Pascal, tu en est ou de ton solveur logique ? Tu parlais de X-Wing, ect, mais les as tu codées ? Vu que tu as déja donné ta solution, est ce que tu peux la modifier ? Tu as quelques temps de ton solveur ? Peux tu me dire si tu résoud les 4 grilles (enfin 3 et AI ...) que j'ai données dans un post précédent par la logique seulement ?

Désolé de te poser autant de questions, mais t'es un des rares a faire un solveur logique (ou alors ils se cachent ...) Enfin, t'es pas obligé de répondre ...

J'ai plutot l'impression inverse: plus de soldeur 'humain' qu'informatique'
Enfin on verra aux résultats

Boris

Yeah !
Quelques améliorations sur mon solver :

Citation:

---

Envoyé par mick605

1ere :

Code :
500004200
100020030
090000005
000400000
805196302
000005000
400000060
030070009
007300008

Moi : Logique seulement en 1.0 milliseconde

---

--> Amelioration : 683 µs
Edit : Amelioration : 630 µs

Citation:

---

Envoyé par mick605

2eme :

Code :
020001030
800900001
000060400
009600180
300000007
087003900
006090000
100006008
050300010

Moi : Resolu seulement par la logique : 1.4 milliseconde.

---

-->Amelioration 1.1 milliseconde
Edit : Amelioration : 990 µs

Il me manque quelques améliorations, je vais les faire ;) !

Continue on fera de toi un programmeur !!!!!
Je suis impressionné: rien que le temps de calculer les possibles et la microseconde est passée...
Une question sut les soldeurs logiques;
vous travaillez enparttant d'une case précise ou vous cherchez a appliiquez une technique ey vous regardez s'il y a des cases concerneees?

Bien qu'ayant choisi une autre vboix je cherche quand meme de la logiquie

Boris

Citation:

---

Envoyé par FullSpeed

Je suis impressionné: rien que le temps de calculer les possibles et la microseconde est passée...

---

Tu veux dire milliseconde ??

Citation:

---

Envoyé par FullSpeed

Une question sut les solveurs logiques;
vous travaillez en parttant d'une case précise ou vous cherchez a appliiquez une technique ey vous regardez s'il y a des cases concerneees?

---

Pour moi, j'ai choisi de faire la méthode la plus rapide et la plus simple (de mon point de vue) ...
Je t'en dirai pas plus. En tout cas, le truc c'est de faire la méthode qui t'inspire le plus. A mon avis, ya une de tes deux possibilites qui est tres dure a mettre en oeuvre.

Pour moi la;solution la plus silmple est de chercher la disposition surle
la grille et de voir quelles sont les cases concernée: j'ai commence par programmer un solveur logique!
Je ne suis confronter aus XWing and co

Mais les choses changent et les gens trouvent des approchesq differentes.
Et actuellement si je pouvais analyser a partir d'une case cela m'interezse.
Mais j'attendrais les résultats du defi

Je suis actuellement sur le choix des hypothese pour voir s'il existe une approche qui donne ls mémés résultats quelque soit la grille de depart.
Les résultats montrent pou l'instant un alea parfait er
Le problème est quand réalité il n'y a aucune méthode qui permette utilisere une probabilité <> de neuf. Mme quand on réduit les candidats on ne change rien a ceux qui restent et quand tu choisies quelque soit le nombre de candidats la probabilité de trouver le bonne solutioon est la meme
on n'en sort pas

162
534
009 On ne peut pas savoir si c'est 78 ou 87 si ce n'est en utilisant les autres case pour limiter mle choix mais pas le modifier A moins que...
Boris

Pour une foiis que l'on a du soleil : il fait beau dans l'Aveyron?

Citation:

---

Envoyé par FullSpeed

Pour moi la;solution la plus silmple est de chercher la disposition surle
la grille et de voir quelles sont les cases concernée: j'ai commence par programmer un solveur logique!
Je ne suis confronter aus XWing and co

---

Et alors ? Concluant ?

Citation:

---

Envoyé par FullSpeed

Mais les choses changent et les gens trouvent des approchesq differentes.
Et actuellement si je pouvais analyser a partir d'une case cela m'interezse.
Mais j'attendrais les résultats du defi

---

Et bien, tu n'as qu'a la coder ;)

Citation:

---

Envoyé par FullSpeed

Je suis actuellement sur le choix des hypothese pour voir s'il existe une approche qui donne ls mémés résultats quelque soit la grille de depart.

---

Bouh hypotheses ;) :ccool:
Que veux tu dire par la ?

Citation:

---

Envoyé par FullSpeed

162
534
009 On ne peut pas savoir si c'est 78 ou 87 si ce n'est en utilisant les autres case pour limiter mle choix mais pas le modifier A moins que...

---

Haha ... Mystere

Citation:

---

Envoyé par FullSpeed

Pour une foiis que l'on a du soleil : il fait beau dans l'Aveyron?

---

Je suis pas en aveyron la, je suis a Toulouse. Ouais il fait beau !

Citation:

---

Envoyé par mick605

Et alors ? Concluant ?

Pas trop je n'ai pas trouver d'enchainement correct entre toutes les methodes et mes implementations ne sont peut etre pas assez veloces à la base

Et bien, tu n'as qu'a la coder ;)
C'est ce que je regarde et c'est pour cela que je pose des quesions!!
Mais en realité il semblerzit que Frank a seulement deux methodes
spécialement veloces

Bouh hypotheses ;) :ccool:
Que veux tu dire par la ?
Quand tu es bloqué en logique tu choisi de valider une case au 'hasard' et de la considérer comme bonne.
Je n'utilise pas mais cela sert normalement avec les contrtaintes
Haha ... Mystère: pas pour tout le monde !
Je suis pas en aveyron la, je suis a Toulouse.
Ouais il fait beau !

---

Par curiosité: tu ne réponds pas bien sur si tu ne veuix pas
mais est-ce que tu as une idée de la complexité de ton algo?

Boris

Citation:

---

Envoyé par FullSpeed

Par curiosité: tu ne réponds pas bien sur si tu ne veuix pas
mais est-ce que tu as une idée de la complexité de ton algo?

Boris

---

Euh ... Je sais pas avec quoi comparer ... Mais je dirais qu'il est assez complexe, enfin, c'est difficile a estimer. Je dirais que le plus dur dans mon algo, c'est les idées, et pas trop la maniere dont je les met en oeuvre ;)

Citation:

---

Envoyé par Kaféine

Salut à tous,

voici une version relativement stable que j'ai appelé Mini Sudoku codée en utilisant des fonctions de l'API windows uniquement (pour voir si j'en étais capable). Entre nous c'est plutôt galère. A défaut de rapidité au moins c'est un petit executable.

Ctrl + C pour copier
Ctrl + V pour coller
Ctrl + R pour Résoudre
Ctrl + E pour Effacer

pour tous ces raccourcis, la fenêtre doit avoir le focus en cliquant gauche dessus (c'est galère mais bon je sais pas encore le faire autrement)

Evidemment il est pas fini et il a des bugs connus comme par exemple il y a un 'c' lors du coller de la grille et je sais pas encore d'ou il vient :\

---

Je viens de retester ton jeu, il est bien, mais ya quelques bugs :

Pour tout tes raccourcis, tu n'as pas besoin d'appuyer sur Ctrl pour les activer.
Si t'appuies vite sur les touches du clavier, tu peux le faire planter ;) :aie:
Quand tu doubles clique dans une cellule, et que tu entres une valeur, ca ne la garde pas en mémoire ...

Sinon ca va, ca gere !

Tu vas faire un petit tour sur Wylky

Grossomodo c'est une évaluation de la complexité du traitement luyi meme et son évolution si tu fais augmenter les nombres

Par exemple la décomposition, en facteur premier est de complexite de la division Racine der N car le nombre des calculs et leurt complexité evoluent comme la racine du nombre

Cela permet d'évaluer le nombre de traitements et leur complexite

Pour le sudoku on peut par exemple dire pour une case le traitement est de 20 test et qu'on l'effectue 22 fois. Ainsi on peut comparer des solutions en précisant le nombre de calculs et leur complexité

dans 162
354
009 Il est mathématiquement calculer que la proba que la solution est 78 est supérieur a celle de 87. Pourquoi a t on avis ?

Je profites du weekend end pour faire des petites digressions
Boris

Citation:

---

Envoyé par FullSpeed

Tu vas faire un petit tour sur Wylky

Grossomodo c'est une évaluation de la complexité du traitement luyi meme et son évolution si tu fais augmenter les nombres

Par exemple la décomposition, en facteur premier est de complexite de la division Racine der N car le nombre des calculs et leurt complexité evoluent comme la racine du nombre

Cela permet d'évaluer le nombre de traitements et leur complexite

Pour le sudoku on peut par exemple dire pour une case le traitement est de 20 test et qu'on l'effectue 22 fois. Ainsi on peut comparer des solutions en précisant le nombre de calculs et leur complexité

---

Ok j'y vais !
Edit : Euh ... T'as pas un lien ?

Citation:

---

Envoyé par FullSpeed

dans 162
354
009 Il est mathématiquement calculer que la proba que la solution est 78 est supérieur a celle de 87. Pourquoi a t on avis ?

---

Parce que l'ordi qui a créé cette grille place surement les chiffres dans l'ordre, et donc plutot 78 que 87 ?? Non serieux, j'en sais rien. De toutes facons, je ne travaille pas avec des probas ... Mais si tu veux bien me le dire, curiosité oblige ...

Citation:

---

Envoyé par mick605

Ok j'y vais !
Edit : Euh ... T'as pas un lien ?

http://fr.wikipedia.org/wiki/Th%C3%A...es_algorithmes

---

Citation:

---

Non serieux, j'en sais rien. De toutes facons, je ne travaille pas avec des probas ... Mais si tu veux bien me le dire, curiosité oblige ...

---

%C3%A9orie_de_la_complexit%C3%A9_des_algorithmes[/URL]
[/QUOTE]

Moi non plus c'esrt pour cela que j'en parle
162
534
009

On parle bien de proba pas de certitude.

Si tu prends la région avec les neuf valeurs
et que tu calcule les diagonales
1+3+9 = 13 2+3=5 si tu place le huit tu auras 23+3+8=13
et tes deux diagonales sont egale . Or la provba d'avoir deux diagonales semblables est faible (32000 sur 363000)
L'exemp^le sort de escargot: essaye avec R2 cela marche aussi
Il faudrait faire une étude pour de savoir si dans les grilles de Sudoku on a de diagonales semblables. Car si on n'en a pas cela deviebdrait une methode de réduction de candidats

Il existe un certain nombre d'analyses de ce genre: par exemple il est rare d'avoir deux trio identiques sur le meme grille
Boris

Tiens, je trouvais bizarre que personne n'ait encore eu l'idée de guider la recherche à l'aide des probabilités.

J'ai une solution en tête qui pourrait donner de très bon résultats. En moyenne, elle devrait même être meilleure que ma solution actuelle !

Je ne sais pas ce que cela peu donner au final mais il est certain que dans cerrtains cas le recours aux probas doit pouvoir servir

De manière constant dans un Sudoku tu as une proba 1-9 (colonnes, chiffres
possdible.... J'ai fait des etudes perso et le verdict est formel; parfaite reparttion a chaque fois entre les possibilités
D'ou l'idee qu'il faut chercher d'autre rapport de proba

Dans l'exemple donné
Le nombre de rangée possible est !9 soit 362880
la proba de base est donc 362880/9 = 40320
La proba des diagonales identiques est de 32000 (Parmi les 362880 il y en a seulement 32 000 (j'ai compte)8O)
Pratiquement je pense que l'on doit pouvoir s'en sezrvir pour trier les candidats d'une case en les classant par proba croissante

On pourra essayer après le défi on aura le temps et tout le monde popurra y aller de ses robas perso. C'est juste un problème d'imagination.


Boris

Citation:

---

Envoyé par FullSpeed

Moi non plus c'esrt pour cela que j'en parle
162
534
009

On parle bien de proba pas de certitude.

Si tu prends la région avec les neuf valeurs
et que tu calcule les diagonales
1+3+9 = 13 2+3=5 si tu place le huit tu auras 23+3+8=13
et tes deux diagonales sont egale . Or la provba d'avoir deux diagonales semblables est faible (32000 sur 363000)

---

Euh ... Je suis pas d'accord !
La proba dont tu parles est faite pour une région (9*9) VIDE ... Hors, quand tu es dans cette config, tu as déja des chiffres qui obligatoirement modifient les probas : pour ton exemple, il n'y a plus 363000 possibilités de finir ta région. Il n'y en a que 2, dont une ou les diagonales sont égales. La proba est donc de 1 sur 2 ... et toujours le meme probleme ...

Citation:

---

Envoyé par FullSpeed

L'exemple sort de escargot: essaye avec R2 cela marche aussi

---

Hasard ?

Citation:

---

Envoyé par FullSpeed

Il faudrait faire une étude pour de savoir si dans les grilles de Sudoku on a de diagonales semblables. Car si on n'en a pas cela deviebdrait une methode de réduction de candidats

Il existe un certain nombre d'analyses de ce genre: par exemple il est rare d'avoir deux trio identiques sur le meme grille
Boris

---

Non plus, la tu parles d'une grille vide ...
Enfin, c'est toi qui raisonne ca ou bien ca viens d'un site ? si c'est d'un site, je voudrais le lien stp ...


En parlant de lien, comment veux tu que je détermine la complexité de mon algo avec le lien wikipedia ?? Ca serait un brute force, encore ... Mais la ...

Citation:

---

Envoyé par FullSpeed

Je ne sais pas ce que cela peu donner au final mais il est certain que dans cerrtains cas le recours aux probas doit pouvoir servir

---

Ouais, la je suis d'accord, mais pas dans ces applications que tu viens de décrire ... Plutot dans un cas comme ca :
Par exemple, supposons qu'un 8 puisse aller dans 3 cases différentes, et que sur ces 3 possibilités, deux d'entres elles obligent un autre chiffre (un 4 par exemple) a etre dans une case ... Ben le 4 aura une proba 2fois plus élevée d'aller la que dans une autre case ...

Oula, j'espere ne pas vous avoir perdu ... (l'exemple n'est pas exactement juste ;) )

En réalité j'ai généré les 362880 combinaisons
de 9 chiffres
123456789...987654321
ensuite j'ai regarde combien avait des diagonales égales
32610 cela signifie donc que si tu prends les neuf chiffres aleatoirement tu as une chance sur 32 000 que tu es des diagonales semblables
et donc 1 chance sur 300000 que les diagonales différente:
si je dois choisir au hasard je parie sur les diagonales différentes donc je ne prends pas j'enlève le 8 Je ne suis pas sur de gangner mais j'ai plus de chance qu'a pile ou face!

C'est le principe de la proba : on essaye de forcer le hasard: C'est exactement ce que l'on fait quand on fait un XWing ou autre: on essaye de trouver une raison formelle pour éliminer un candidat. Mais les probalites ne s'appellent pas les certitudes! Autrement c'est pareil
Pour le lien c'est bien toi qui m'en a demandé un?
Pour info je peux te dire très exactement combien je fais de calculs et de quelle complexité pour une case.
Ainsi on peut dire que tel ou tel algo demande demande X calcul et que chaque calcul a une complexité Y se qui donne a la fin un temps final X calcl de W temps= XW.. Je pense que c'est comme cela que les juges feront: la technique est classique

Boris
Excuses les envois intempestifs mais ils sont du a ma maladie
Il doit y avoir une combinaison de touches pour envoyer et je dois la faire sans me rendre compte(j'ai une sorte d'Alzeimer)

Citation:

---

Envoyé par FullSpeed

En réalité j'ai généré les 362880 combinaisons
de 9 chiffres
123456789...987654321
ensuite j'ai regarde combien avait des diagonales égales
32610 cela signifie donc que si tu prends les neuf chiffres aleatoirement tu as une chance sur 32 000 que tu es des diagonales semblables
et donc 1 chance sur 300000 que les diagonales différente:
si je dois choisir au hasard je parie sur les diagonales différentes donc je ne prends pas j'enlève le 8 Je ne suis pas sur de gangner mais j'ai plus de chance qu'a pile ou face!

---

Non ! Je suis d'accord sur tes chiffres, mais pas sur la méthode a appliquer ! C'est comme si tu disais : on a 9 balles dans une urne : 8 noires et 1 blanche. On tire dans l'ordre 9 balles.

On appelle P l'évenement "Sortir la blanche en 8eme" (par exemple)
Je suis d'accord qu'au final, on a une proba de P égale a 1/9.

Supposons maintenant que nous avons tiré 7 balles, toutes noires. (il reste donc 1 de chaque) D'apres ton raisonnement, vu que la proba de P est faible, la chance de sortir la blanche au prochain coup (donc au 8eme) serait plus faible que l'autre ... Or, il reste deux balles, une blanche et une noire. La proba de tirer l'une ou l'autre est indépendante de tout : de P, des balles tirées avant... etc

Maintenant, faisons analogie avec le sudoku : les balles noires représentent les chiffres différents de 1,2,3,4,5,6,7,9, et la balle blanche, c'est le 8. Les 7 balles sorties sont les 7 chiffres déja placés, 1,2,3,4,5,6,9. P peut etre ta proba d'avoir les diagonales égales, P correspond en fait a une configuration spéciale du systeme. Et ce que je viens de te montrer, c'est que placer les elements qu'il manque est indépendant de P.

Citation:

---

Envoyé par FullSpeed

C'est exactement ce que l'on fait quand on fait un XWing ou autre: on essaye de trouver une raison formelle pour éliminer un candidat.

---

Non, le X-Wing est basé sur des certitudes ...

Citation:

---

Envoyé par FullSpeed

Pour le lien c'est bien toi qui m'en a demandé un?
Pour info je peux te dire très exactement combien je fais de calculs et de quelle complexité pour une case.
Ainsi on peut dire que tel ou tel algo demande demande X calcul et que chaque calcul a une complexité Y se qui donne a la fin un temps final X calcl de W temps= XW.. Je pense que c'est comme cela que les juges feront: la technique est classique

---

Ouais, je voulais un lien, mais je pensais que le lien serait du genre : "si votre prog fait ca, on peut dire que" ...
Qu'entends tu par "un calcul" ?

Code:

---

1 2	1+1 (((X+y) mod 3)*12+z div 2=21) and Result

---

Comment déterminer Y ?
Pour un BruteForce, c'est assez simple ...
Pour un solveur logique, si la grille est simple, le solveur effectuera certains calculs, si c'est dur, elle en effectuera d'autres. Mais toutes les techniques ne font pas le meme nombre de calculs, alors que pour un solveur bruteForce, pour chaque case et quelque soit la difficulté, on ajoute une valeur, puis on vérifie la grille !

Voila !

Citation:

---

Envoyé par FullSpeed

Si tu prends la région avec les neuf valeurs
et que tu calcule les diagonales
1+3+9 = 13 2+3=5 si tu place le huit tu auras 23+3+8=13
et tes deux diagonales sont egale . Or la provba d'avoir deux diagonales semblables est faible (32000 sur 363000)

---

Je suis du même avis que mick605 par rapport aux diagonales. En fait, tu as un événement "La somme de la diagonale vaut 13" (n'importe laquelle).

La probabilité que cet événement se réalise est déjà faible. Le fait qu'il se soit réalisé une première fois n'a aucun effet sur sa prochaine réalisation.

C'est comme dire qu'il y a autant d'homme que de femme, qu'à chaque naissance tu as une probabilité de 0.5 que le bébé soit un garçon. Mais puisque dans la famille, le premier né était un garçon, le deuxième a de grandes chances d'être une fille.
Ou encore, de dire que la probabilité de gagné deux fois au loto est quasi nulle, donc si tu as gagné une première fois, tu n'as plus aucune chance de gagner à nouveau...

Citation:

---

De manière constant dans un Sudoku tu as une proba 1-9 (colonnes, chiffres
possdible.... J'ai fait des etudes perso et le verdict est formel; parfaite reparttion a chaque fois entre les possibilités
D'ou l'idee qu'il faut chercher d'autre rapport de proba

---

En fait, je ne pensais pas utiliser les proba pour prédire la valeur d'une cellule, mais plutôt pour estimer le risque de se tromper lorsqu'on émet une hypothèse.
Je m'arrête là parce que j'ai déjà quasiment donné mon nouvel algo.