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

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!

---

Je suis moi aussi entièrement d'accord avec mick605 et Franck SORIANO :P
Tu ne peux rien déduire des probabilités observées pour une grille vide pour un choix sur une grille en partie complétée
Dans ton exemple, et toutes choses égales par ailleurs, la probabilité d'avoir 8 est 0.5 et celle d'avoir 7 est 0.5

Citation:

---

Envoyé par mick605

pour un solveur bruteForce, pour chaque case et quelque soit la difficulté, on ajoute une valeur, puis on vérifie la grille !

---

Le pb, c'est que la grille peut être valide alors qu'il n'y a plus de solution, dans cette configuration. Toute la difficulté est à mon sens de hiérarchiser les hypohèses, afin de ne pas faire de calcul redondants, et de n'en oublier aucune :mrgreen:

Ok, je vois qu'on pense tous la meme chose ...

FullSpeed > C'est toi qui pensais que la proba de 78 est plus grande que celle de 87 ? Si c'est pas toi, tu voudrais bien nous dire d'ou tu le sors ? Parce que d'apres ce que j'ai compris de tes posts, cela ne viendrais pas de toi ...

Ton analyse est juste ai niveau des deux dernieres boules
si on reste au niveau des cases
Le but est justerment de se désolidarisé des cases et de les
mettre dans un autre referentiel

Quand tu resoud ta grille les informations de la case vide sont nulles: tu sais juste que le chiffre sera de 1 a 9 . Tu cherches a créer une information en dehors de la case qui te permettra de fixer la valeur
Par exemple tu la replace dans sa région et tu en déduis une valeur

La proba fait pareil mais le résultat n'est- pas sur a 100%
Si tu as tes neuf chiffres et que tu cherches a avoir les diagonales a chaque tirage la proba est de 50-50 et non de 1-9: soit la bille est bonne soit elle est mauvaise. Le nombre n'y change rien. C'est comme au loto les chiffres deja tiré ou pas encore tiré non aucune influenbce sur le numero qui va sortir Que tu tires la



Quand tu arrives a aux derniere tu as ttoujouyrs 1 chance sur deyx de tuirer la bonne Mais je crois que c'st la que tu te trompes: je ne tire pas la bille : je la choisie. Il me reste le 7 et le 8 et çn me demandes de choisçir pas au hasard, a moi. Alors je mets les boules dans un autre référentiel
la région et je cherche un autre criter pour orienté mon choix. Je ne choisie plus la boule je choisi la region. Et la le calcul est bien le bon
si tu titres neuf chiffre la proba s'avoir des diaginales identiques est faible et probablement les disagonaales seront differentes et donc le 8 de la case 7 a peu de chance d'etre bonb. Mais il peu l'etre

Ton analyse est juste ai niveau des deux dernieres boules
si on reste au niveau des cases
Le but est justement de se désolidarisé des cases et de les
mettre dans un autre référentiel

Quand tu resoud ta grille les informations de la case vide sont nulles: tu sais juste que le chiffre sera de 1 a 9 . Tu cherches a créer une information en dehors de la case qui te permettra de fixer la valeur
Par exemple tu la replace dans sa région et tu en déduis une valeur

La proba fait pareil mais le résultat n'est- pas sur a 100%
Si tu as tes neuf chiffres et que tu cherches a avoir les diagonales a chaque tirage la proba est de 50-50 et non de 1-9: soit la bille est bonne soit elle est mauvaise. Le nombre n'y change rien. C'est comme au loto les chiffres deja tiré ou pas encore tiré non aucune influenbce sur le numero qui va sortir Que tu tires la dernière ou la prmier des boules la proba que cela soi-it
le 1 est exactement la meme.

Quand tu arrives a aux dernières tu as toujours 1 chance sur deux de tirer la bonne Mais je crois que c'est la que tu te trompes:
je ne tire pas la bille : je la choisie. Il me reste le 7 et le 8 et on me demande de choisir pas au hasard, a moi. Alors je mets les boules dans un autre référentiel la région et je cherche un autre criter pour orienté mon choix. Je ne choisi plus la boule je choisi la région. Et la le calcul est bien le bon
Si je tire au hasard j'ai de fait une chance sur deux
Mais je ne choisi pas au hasard.
Regardes tes fish eyes quelle est le rythme auquel tu le trouve
dans les grilles et pourtant tu lle cherche


Prends des grilles résolues et regarde les diagonales: tu verras qu'il est tres rare d'avoir l'égalité Mais j'ai trouve beaucoup plus efficace je ne veux pas donner d'info a la concurencve mais de 32160 je suis passer a 3000

Boris

Citation:

---

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.

---

Je n'ai jamais dit cela ou alors je me suis mal exprimé


cet événement se réalise est déjà faible

C'est de cela dont je parle

J'ai oublie de répondre pour la complexité
Prenons un nombre et on cherche a savoir si iul est premier
Nous utiliserons la methode des divisions
789 est-il premier?
La méthode naïve est de le diviser par tous les nombres qui le precedent
nous allons donc faire 788 calculs (ici des divisions)
Si nous faisons grandir 789 le nombre de calcul augmente en meme temps

Code:

---

1 2 3

for i:=1 to 788 do if 789 mod i=0 then pas premier

---

A cote mick a coder mais a lui on ne la lui fait pas ; on a pas besoin de tester les nombres pairs

Code:

---

1 2 3 4 5 6

i:=3 repeat if 789 mod i=0 then pas premie i:=i+2, Until i>789,

---

La le calcul n'a pas changé de complexite mais c'est le nombre qui a baise
A ce momenr on a Frank qui arrive :D . Ce que tu as fait mick est
tres bien mais tu est encore a l'école ou en fac et tu n'as pas tout vu
Car en réalité tu n'as pas besoin de tester tous les nombres > 788
tu peux t'arrêter à la racine carré 28 donc

Code:

---

1 2 3 4 5 6

i:=3 repeat if 789 mod i=0 then pas premie i:=i+2, Until i>28,

---

en fait avec cet algo nous effectuons toujours le meme
calcul (modulo) mais 14 fois seulement

Arrive le Boris avec sa technique (qu'il voudrait bien de sioux) pour dalculer la primarité. En fait le modulo dure 60 cycles(doc Intel) alors qu'une addition dure 1. Donc si on remplace l'a division par une addition on influe la sur le calcul lui même
Je vous passe le changement mais (s'il y en a que cela interesse il est dispo)
Alors on modifie le code. Et la pour voir le gain on regartde combien on fait d'addition (contre les 14 modulos)
Et la on compte que l'on fait 1000 adidtions
Donc Frank fait 14 modulos a 60 soit 840 cycles
Boris lui fait 1000 additions a 1 soit 1000 cycles

Il n'y a pas de discussion: les algos donnent tous les deux la meme resulrtat mais celui, qui a la plus grandecomplexite(la div) est
plus efficace que celui de complexité moindre
(D'autant plus qu'il est aisé d'améliorer l'algol de Franc et diminuer le nombre de calcul
A quoi cela sert?
Par exemple dans ce cas on pourrait analyser la situation et se diree que sur un processeur RISC la division prends moins de temps et qu'il vaut mieux se porter vers un calculateur IBM avec Poser PC que vers des Blues geens Milti core . Il se trouve que les additions sont a croissance constante (dans notre exemple) et on peut donc les mettre à la sauce RUSC

Ce sont c'est deux aspects que la complexite veut 'représenter'
J'espère ne pas avoir dis trop de sottise et eclairé un peu ta lanterne
Boris

Je me suis mal exprime: l'idee est de moi elle ne vient pas d'un autre site ou autre esprit

Je maintiens que la proba est juste!
si on s'en remets au hasard vous avez raison les deux cases on exactement la mime probabilité de sortir. Mais on ne parle pas de hasard
on parle de choisir .
Moi j'estime que si place le huit en case 7 je vais obtenir une configuration
de la REGION qui a lieu 1 fois sur 11 aloprs que si je place le 7 je vais obtenir une configuration qui a lieu 1 fois sur 1,02
Je ne touche pas a la case 7. Dans l'exemple elle n'a que deux possibilités mais elle pourrait en avoir plus cela ne changerai Le traitement ne consiste pas a valider le 7 mais a dire que le 8 est peu probable. A toi de voir ce que tu en fait mais les chiffres sont la

La méthode que j'ai utilisé pour mon solveur est qualifiée de Brrute Force en opposition avec des soldeurs logiques. Là du coup la méthode n'est pas de moi elle est connue depuios des lustres comme les logiques . Par contre j'ai essayé d'en faire une implémentation speed...

C'est une convention enrtre nous. La methode des possibles n'est pas un brute force: c'est a dire que je n'essaye pas les !81 (en gros) solution les unes apres les autres et je ne vérifie pas a chaque fois si la solution est bonne: je vais mime te faire une confidence; je n'ai pas de routine de vérification de solution.
En réalité mon logiciel n'a qu'une seule procédure: le calcul des possibles d'une case et c'est tout. Statistiquement mon logiciel calcul et recalcule les possibles en moyenne 3 fois par case donc il m'est facile de donner la charge exacte du programme
il faut mettons un 10 000 de seconde pour calculer les candidats
il y a en gros 60 cases qui ne soient pas des revéles donc 180 appels en gros de ma procédure a 1/ 10 000 de seconde cela me donne donc...... :D
(En fait je ne traite pas toutes les cases, je ruse et je ne fais pas les 60(81-reveles).
Tu verras...

Boris

Il n'y a pas un matheux sur le site pour nous aidez?

En fait il y a une façon très simple de comprendre que les événements 78 et 87 ont la même probabilité : intervertir deux chiffres dans une grille de sudoku donne une grille valide. Donc sans autre information 78 ou 87 c'est la même chose.

Citation:

---

En fait il y a une façon très simple de comprendre que les événements 78 et 87 ont la même probabilité : intervertir deux chiffres dans une grille de sudoku donne une grille valide. Donc sans autre information 78 ou 87 c'est la même chose.

---

Deux choses: si tu prends une grille pleine et que tu intervertis
deux cases la grille n'est plus bonne.


Secundo je n'ai jamais prétendu que les proba soient différentes entre deux cases
Il ne s"agit pas de tirer une bille dans un sac le problème est le suivant

Il existe 362880 possibilités pour arranger neuf chiffre s
dans ces 362880 il en existe 32160 qui on des 'diagonales' égales et donc 310000 qui ne les ont pas. Et j'affirme qu'il y a plus de chance sur un tirage de neuf d'avoir des diagonales différentes que semblables: pas que c'est impossible ou je ne sais quoi je dis que majoritairement on aura des diagonales différentes plus souvent

Boris

On en fait l'usage que l'on veut mais c'est une réalite
C'est la que je demande l'avis d'un matheux pas sur un tirage ou tout le monde est d'accord.

Je crois que tu confonds probabilités et statistiques.

Sovitec.

PS : Quand je disais intervertir 2 chiffres c'est dans toute la grille, pas juste entre 2 cases.

PPS : Les probas et les stats ne sont pas ma spécialité, mais à la base je suis un matheux.

Salut

Alors, j'écris un méga pavé pour expliquer a FullSpeed que son raisonnement est faux ... Accrochez vous !! :ccool:

Citation:

---

Envoyé par FullSpeed

Il existe 362880 possibilités pour arranger neuf chiffres. Dans ces 362880, il en existe 32160 qui on des 'diagonales' égales et donc 310000 qui ne les ont pas. Et j'affirme qu'il y a plus de chance sur un tirage de neuf d'avoir des diagonales différentes que semblables : pas que c'est impossible ou je ne sais quoi je dis que majoritairement on aura des diagonales differentes plus souvent.

---

... et tu en déduis ...

Citation:

---

Envoyé par FullSpeed

Si tu tires neuf chiffres, la proba d'avoir des diagonales identiques est faible, et probablement les diagonales seront differentes, et donc le 8 de la case 7 a peu de chance d'etre bon

---

Bon je vais te prouver que ton raisonnement est absolument faux :
Premierement, pourquoi choisis tu l'évenement : "les diagonales sont égales" ?
J'imagine que ce n'est sans trop de raisons particulieres ...
Tu as une proba que ce soit juste : 32160/362880 = 8,9 % (1) .... => (implique) config "87"
Tu as une proba que ce soit faux : 330720/362880 = 91,1 % (2) .... => config "78"
Et tu déduis donc que lorsque il reste deux chiffres manquant, on a plus de chances d'avoir (2) de vrai ... et donc d'être largement dans la configuration "78" (91,1 > 8,9)

Donc, en gardant ton raisonnement, je change simplement d'évenement. Je prends celui qui dit : "les chiffres sont disposés de la maniere suivante 162/534/789"
J'ai une proba que ce soit juste : 1/362880 = 0.0003 % (1) .... => config "78"
J'ai une proba que ce soit faux : 362879/362880 = 99,9997 % (2) .... => config "87"
Et j'en deduis donc que lorsque il reste deux chiffres manquant, on a plus de chances d'avoir (2) de vrai ... donc d'etre dans la configuration "87" (99,9997 > 0.0003)

Voila un beau raisonnement par l'absurde : on a P78>P87 et P87>P78 ...
P78 = proba d'etre dans la config 78
P87 = proba d'etre dans la config 87

Citation:

---

Envoyé par FullSpeed

On en fait l'usage que l'on veut mais c'est une realite
C'est la que je demande l'avis d'un martheux pas sur un tirage ou tout le monde esd'accord.

---

Je pense qu'on n'a pas besoin d'un "matheux" pour te prouver que tu as tord ... En plus, on est tous un peu matheux ... Mais si tu trouves un matheux, demande lui !

Citation:

---

Envoyé par FullSpeed

Mais je crois que c'est la que tu te trompes:
je ne tire pas la bille : je la choisie. Il me reste le 7 et le 8 et on me demande de choisir pas au hasard, a moi. Alors je mets les boules dans un autre référentiel la région et je cherche un autre criter pour orienté mon choix. Je ne choisi plus la boule je choisi la région. Et la le calcul est bien le bon

---

Tu parles de "choisir" ... Mais grace a quoi choisis tu ? Deux réponses a ca :
1) Les probas : elles sont égales donc ca ne va pas
2) Ton intuition : Elle est mauvaise :D Ca arrive a tout le monde d'avoir une intuition qui foire et en etre persuadé : Moi par exemple, j'ai comme intuition que toutes les grilles peuvent etre résolues par la logique ... Je me trompes peut etre, mais j'en suis persuadé !

Citation:

---

Envoyé par FullSpeed

C'est comme au loto les chiffres deja tiré ou pas encore tiré non aucune influence sur le numero qui va sortir

---

Alors la c'est une tres grossiere erreur !!!

Exemple :
On appelle P la proba que le nombre "12" (Aveyron !!!!!) sorte : on a alors P=1/60 (ya bien 60 boules au loto ?)
Hors, on sort une boule, qui n'est pas 12 ...La proba de sortir P au prochain est de P=1/59 ...
on sort une autre boule, qui n'est pas 12 ...La proba de sortir P au prochain est de P=1/58 ...
....
....
....
On sort 56 autres boules, toujours pas de 12 ... La proba de sortir P au prochain coup est P=1/2 (il reste 2 boules dans le panier)
On sort une autre boule, pas le 12 ... (on a pas eu de chance, depuis le début ...). La proba de sortir 12 au prochain est de P = 100%

Je viens de te démontrer que les nombres tirés ont une grande influence sur le numero qui va sortir !!!

Citation:

---

Envoyé par FullSpeed

Je me suis mal exprime: l'idee est de moi elle ne vient pas d'un autre site ou autre esprit

---

Alors c'est toi qui a faux :D

Et je viens d'avoir une idée : pour te PROUVER que tu as faux. Et la, ca m'étonnerais fortement que tu trouves une raison.

Utilises un solveur qui trouve toutes les grilles. Modifie le et demandes lui de te montrer toutes les solutions de cette grille :

Code:

---

1 2 3 4 5 6 7 8 9

162000000 534000000 .09000000 000000000 000000000 000000000 000000000 000000000 000000000

---

Demande lui aussi de compter le nombre de fois ou le "." est un 7, et le nombre de fois ou le "." est un 8. Je peux te garantir que les chiffres ne seront pas seulement "a peu pres égaux", mais strictements égaux.

Bon, on va arrêter là le discours sur les probabilités avant que ça ne dégénère :cry:
C'est un défi sur la programmation, pas sur les mathématiques.

De toute façon, peu importe que ce soit vrai ou pas. C'est une heuristique comme une autre après tout.

pire ane que celui qui ne veut pas comprendre :D

Est que oui ou non il existe plus de combinaison avec des diagonales egales quie différents

Je vais vous démontrez que vous avez tord

Je met 9 boules numérotées de 1 a 9 dans un sac
et je vous parie un million d'euros que si on tire les neuf billes consécutivement elles ne seront pas en ordre croissant
Vous pariez vous qu'elle le seront. Qui joue avec moi?
Boris

C"est cela que je dis et affirme on a plus de chance que les diagonales soient différentes qu'égales. Et que donc quand je complété une diagobalmes j'evite la valeur si elle est disponile qui dera quee les
diagonales soient egale
J'ai choisi les diagonales un peu au hasard mais j'ai trouve beaucoup mieux depuis. Le but est de trouver une disposition qui ne soit pas unique mais qui arrive rarement.

Alors? Qui joue avec moi?
Boris

Citation:

---

Envoyé par Franck SORIANO

Maintenant, je suis obligé de donner les miens (Machine 4 fois plus rapide que celle de Félix) :
Grille 1 : 0.0483 ms
Grille 2 : 0.2921 ms
Grille 3 : 0.0336 ms
Grille 4 : 0.0689 ms (il fait chaud, le PC va lentement. Habituellement c'est plutôt 0.0630 ms pour celle là :mrgreen:)

---

J'ai entrepris de rédiger une description détaillée de ma solution avec toutes les étapes de son élaboration, puis de son optimisation.
Ca m'a ammené à la ré-écrire entièrement.
Et finalement, je suis arrivé à un résultat différent.
Version non multi-threadée :

Grille 1 : 0.0153 ms
Grille 2 : 0.1288 ms
Grille 3 : 0.0212 ms
AI-Escargot : 0.0450 ms

Mais j'ai un problème pour faire les mesures des temps : Le processeur est constamment en économie d'énergie. Du coup, il tourne à 2 GHz au lieu de 2.66 GHz :mouarf:

Citation:

---

Envoyé par FullSpeed

Je vais vous démontrez que vous avez tord

Je met 9 boules numérotées de 1 a 9 dans un sac
et je vous parie un million d'euros que si on tire les neuf billes consécutivement elles ne seront pas en ordre croissant
Vous pariez vous qu'elle le seront. Qui joue avec moi?
Boris

---

J'ai dit on arrête.
Qui plus est, si on se mettait dans le même cas de figure que tes diagonales, c'est à dire qu'on prenait le pari sachant que la 1, la 2, la 3, la 4, la 5, la 6 et la 7 sont déjà sorties dans cet ordre, ça pourrait te coûter très cher !

Citation:

---

Version non multi-threadée :
Grille 1 : 0.0153 ms
Grille 2 : 0.1288 ms
Grille 3 : 0.0212 ms
AI-Escargot : 0.0450 ms

Mais j'ai un problème pour faire les mesures des temps : Le processeur est constamment en économie d'énergie. Du coup, il tourne à 2 GHz au lieu de 2.66 GHz :mouarf:

---

C'est toujours impressionnant : mais je commet peut etre une erreur de lecture quand tu écris 0.0450 ms il faut lire 450 millisecondes
ou 0 milliseconde , 0450 ?
Boris

Il faut lire 45 microsecondes (en fait maintenant c'est même 40).

C'est vraiment de la perf. J'ai hate de voir si je ne peux pas
t'emprunter une ou deux techniques.
J'ai cependant un doute. Non pas sur tes chiffres mais sur la difference
entre eux

Citation:

---

Grille 1 : 0.0153 ms
Grille 2 : 0.1288 ms
Grille 3 : 0.0212 ms
AI-Escargot : 0.0450 ms

---

Tu as un rapport de 3 par exemple entre la 2 et l'escargot
Hors , je me suis déjà exprime dessus, les solveurs sont souvent tres performants et s'effondrent sur certaines grilles
As tu pu analyser la raison des ecarts? i/e sont-ils controlables ou
trop aléatoires?

Je trouve aussi assez surprennant que personne n'ait abordé la création de carré latins. 'pas des problemes mais des grilles remplies)
C'est souvent dans le debat. Ce n'est pas tres complique et chacun y va de sa methode...
Boris

Citation:

---

Envoyé par FullSpeed

Tu as un rapport de 3 par exemple entre la 2 et l'escargot
Hors , je me suis déjà exprime dessus, les solveurs sont souvent tres performants et s'effondrent sur certaines grilles
As tu pu analyser la raison des ecarts? i/e sont-ils controlables ou
trop aléatoires?

---

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.
Comme je l'ai dit précédemment, selon le paramétrage que j'applique à mon solveur, il sera plus rapide avec certaines grilles et plus lents avec d'autre, car il recherchera les chemins différemments.

Mais j'ai en tête un autre algo complètement différent (guidé par les probabilités) qui devrait résoudre les grilles avec plus de constance. Mais je pense que sa vitesse de résolution sera beaucoup moins élevée (encore que...).

Citation:

---

Envoyé par FullSpeed

Je trouve aussi assez surprennant que personne n'ait abordé la création de carré latins. 'pas des problemes mais des grilles remplies)
C'est souvent dans le debat. Ce n'est pas tres complique et chacun y va de sa methode...
Boris

---

Ben la génération de carrés latin n'est qu'un cas particulier du solveur. Il suffit de démarrer à partir d'une grille vide...
Ma dernière version, génère et mémorise 1 000 000 de carrés latins en 3 secondes.

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.

Citation:

---

Envoyé par Loulo92

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.

---

Salut !

Tu pourrais traduire ton code en delphi et participer au défi ! Vas y ! Plus on est de fous, plus on rit ... :D