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

Citation:

---

Envoyé par Félix Guillemot

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...

---

Là tu viens juste de nous redire, d'une autre façon, la règle de base du sudoku, à savoir 1 seule valeur par ligne
Quelle que soit la configuration de ta grille, la somme des 3 éloignements fera toujours 12 (régions A/D, B/E, C/F) vu que le 6 par ex ne peut figurer qu'une seule fois dans une ligne...
On pourrait dire aussi que l'éloignement moyen (ligne 2 à ligne 5) vaut 4 et quelle que soit la façon de disposer les 6 valeurs, la somme des éloignements sera toujours égale à 3 fois l'éloignement moyen :mrgreen:
Même raisonnement avec les régions excentrées
L'éloignement moyen est de 7 (ligne 2 à ligne 8) et 3x7=21

Y'en a à qui le repos ne vaut rien ;)

Citation:

---

Envoyé par Félix Guillemot

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

---

Et les huîtres, c'est 13 à la douzaine ;):mrgreen:

Je suis d'accord avec OutOfRange (qui ne nous donne pas beaucoup d'infos sur son solver :ccool:). C'est normal que la somme soit constante ...
Tu as un chiffre en ligne 1,2,3 (*) et 4,5,6 (**) ... quelque soit la config, tu auras tout le temps la somme des différence entre les elements (**) et (*) constante ;) !!

Citation:

---

Envoyé par Félix Guillemot

Mick n'a pas encore trouvé le Da Vinci Code

---

A la recherche éternelle du Graal ...

Citation:

---

Envoyé par Félix Guillemot

]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.

---

Je ne sais pas si c'est de ca que tu parles, en tout cas, c'est un bon melange de grilles difficiles. C'est en fait les quelques grilles que je t'avais donné pour savoir si tu les resolvais par logique, plus quelques unes de 17 de FullSpeed. Les voila :

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76

Grille 1 : 500004200 100020030 090000005 000400000 805196302 000005000 400000060 030070009 007300008   Grille 2 : 020001030 800900001 000060400 009600180 300000007 087003900 006090000 100006008 050300010   Grille 3 : 084010590 056009000 009050040 040500938 000000000 931004070 090040700 000900450 075080360   Grille 4 (AI Escargot) : 100007090 030020008 009600500 005300900 010080002 600004000 300000010 040000007 007000300   Grille 5 (Easter Monster) : 100000002 090400050 006000700 050903000 000070000 000850040 700000600 030009080 002000001   Grille 6 (1ere de la liste 17 de FullSpeed) : 071000000 000080600 000400000 000100072 800050000 000000000 040702000 600000850 000000300   Grille 7 (derniere de la liste 17 de FullSpeed) : 079000600 000100400 000200000 000000750 400300000 100000000 060080000 000090010 000000023

---

FullSpeed a toujours du mal avec ses pieces jointes ...Je crois que ton fichier est trop gros ...
Pour ton programme, ca m'étonnerais que ca ait un rapport avec la carte graphique ... Je n'ai pas testé le dernier que tu nous as envoyé par flemme (et ouais, ya pas d'exe ... :oops: )

Citation:

---

Envoyé par FullSpeed

Si cela ne t'ennuie pas tu regardes la methode TKillerW.paint
et tu precidse

Code:

---

WITH KILLERW.CANVAS do

---

---

ça fait strictement la même chose, au pixel près :?

Citation:

---

Envoyé par mick605

Je suis d'accord avec OutOfRange (qui ne nous donne pas beaucoup d'infos sur son solver)

---

Ce n'est pas pour préserver un quelconque secret de fabrication :(
J'ai codé un certain nombre de méthodes logiques de résolution
Candidats Uniques
Jumeaux
Interactions
Candidats Identiques
Groupes Mélangés
XWing
XYWing

Mais avec ça je ne viens pas à bout des grilles les + costaudes :(

Je commence tout juste à me pencher sur la 2ème phase: force brute :aie:
Mais je bloque un peu, pour l'instant j'en suis qu'à force demi-sec :mouarf:
J'essaie de tirer mon épingle du jeu en peaufinant une IHM sympa
je sais, c'est petit, mais on fait ce qu'on peut ;)

Citation:

---

Envoyé par OutOfRange

Ce n'est pas pour préserver un quelconque secret de fabrication
J'ai codé un certain nombre de méthodes logiques de résolution
Candidats Uniques
Jumeaux
Interactions
Candidats Identiques
Groupes Mélangés
XWing
XYWing

---

Pas mal ! (il me semble qu'il te manque a coder des fonctions simples, alors que tu as déja codé des difficiles :roll: ). C'est quoi Groupe Mélangés ?

Citation:

---

Envoyé par OutOfRange

Mais avec ça je ne viens pas à bout des grilles les + costaudes

---

Un exemple ?

Citation:

---

Envoyé par OutOfRange

Je commence tout juste à me pencher sur la 2ème phase: force brute
Mais je bloque un peu, pour l'instant j'en suis qu'à force demi-sec
J'essaie de tirer mon épingle du jeu en peaufinant une IHM sympa
je sais, c'est petit, mais on fait ce qu'on peut

---

Pas du tout, ca fait partie du défi ! Il me tarde vraiment de voir comment tu as codé ces méthodes, pour voir si on est parti de la meme facon ...

Enfin, je te poses ces questions, c'est pas forcé de répondre, c'est juste pour se tenir a jour de ce qu'il se fait, sans partir dans les details ...

Citation:

---

Envoyé par mick605

il me semble qu'il te manque a coder des fonctions simples

---

Si tu penses à un truc du genre candidat seul (il n'y a qu'un seul candidat possible dans une case) pour moi ça ne fait pas partie des "méthodes" de résolution, c'est un aboutissement : la grille est résolue quand justement il n'y a plus qu'un seul candidat dans toutes les cases
Mais si tu penses à autre chose que j'aurais zappé, je suis preneur d'info ;)

Citation:

---

Envoyé par mick605

C'est quoi Groupe Mélangés ?

---

http://www.mots-croises.ch/Manuels/S...s_melanges.htm

Exemple de grille non résolue par la logique

Citation:

---

084010590
056009000
009050040
040500938
000000000
931004070
090040700
000900450
075080360

---

Sur ce vu l'heure tardive, je vais aller me plonger dans les bras de Morphée
Bonne nuit

Citation:

---

Envoyé par OutOfRange

Si tu penses à un truc du genre candidat seul (il n'y a qu'un seul candidat possible dans une case) pour moi ça ne fait pas partie des "méthodes" de résolution, c'est un aboutissement : la grille est résolue quand justement il n'y a plus qu'un seul candidat dans toutes les cases

---

Pareil !

Citation:

---

Envoyé par OutOfRange

Mais si tu penses à autre chose que j'aurais zappé, je suis preneur d'info ;)

---

Je me doutes, mais bon, faut garder des trucs secrets quand meme (pour l'instant je vois pas quoi d'autre)

Citation:

---

Envoyé par OutOfRange

http://www.mots-croises.ch/Manuels/S...s_melanges.htm

---

C'est a ca que je pensais quand je disais des méthodes simples manquantes ...

Citation:

---

Envoyé par OutOfRange

Exemple de grille non résolue par la logique

Code:

---

1 2 3 4 5 6 7 8 9

084010590 056009000 009050040 040500938 000000000 931004070 090040700 000900450 075080360

---

Sur ce vu l'heure tardive, je vais aller me plonger dans les bras de Morphée
Bonne nuit

---

Re - Pareil !
Allez, Bonne nuit ! :ccool:

Ayant je crois réglé le problème des solveurs dit Brut Force
Par essence plmus rapides que les logiques
(le temps de raisonnement)
je vais prendre mes essais sur les logiques mais la barre est haiute

Franck peux tu nous donner tes tesmps(sans tricher pour AI)

Je remercie ceux qui cherche mon problème graphique: il m'est venu une autre idée: j'utilise les grandes polices dans affichage cela provoque parfois de
débordements peut être est ce le cas?

Boris
mick: sur quel fichier j'ai encore m....?

J'ai vu que vous mettiez des images dans vos message
Comment les intègre-t-on: On me demande l'adresse d'un serveur.

Citation:

---

Envoyé par FullSpeed

J'ai vu que vous mettiez des images dans vos message
Comment les intègre-t-on: On me demande l'adresse d'un serveur.

---

Fastoche :D
dans le cadre options supplémentaires, tu cliques sur [gérer les pièces jointes] puis [parcourir] (ton DD)

Citation:

---

Là tu viens juste de nous redire, d'une autre façon, la règle de base du sudoku, à savoir 1 seule valeur par ligne

---

Certes, mais on pourrait dire cela de toutes les méthodes de déduction logique.
Toute déduction logique repose sur les règles fondamentales du Sudoku : puisque le chiffre ne peut pas être là (à cause des règles), il est là.
Cela ne remet en rien en cause le fait que c'est une méthode de déduction logique comme une autre.
C'est comme si je te disais : "j'ai remarqué que dans les régions A et B j'ai un 5, eh bien dans la région C je sais sur quelle ligne il est"
Tu me dirais que je viens de te redire les règles d'une autre façon.
N'empêche que personne n'a jamais parlé de ces éloignements ou de similitudes barycentriques des grilles de Sudoku.
Il faut se méfier de ce qui parait évident ou que l'on croit savoir depuis toujours, c'est un frein à l'investiguation et là la recherche.

Citation:

---

Envoyé par Félix Guillemot

Certes, mais on pourrait dire cela de toutes
Il faut se méfier de ce qui parait évident ou que l'on croit savoir depuis toujours, c'est un frein à l'investiguation et là la recherche.

---

Entièrement d'accord avec toi:
Petit exemple d'obscurantisme scientifique

Si vous voulez retrouvez deux nombres depuis leur produit vous devez diviser la racine carrée du produit par tous les nombres premiers inférieurs
a cette racine. Cela relève de la Lapalissade.

Tant que vous ne trouverez pas plus simple vous jouerez au Donquichotte
en essayant d'établir la liste de NP pour apppliquer cette méthode: Tout le monde sait bien comment tu fais.

Mais en réalité il y a une grosse difficulté: on ne sait pas faire la liste des nombres premiers de grande taille (plusieurs centaines de chiffres)
Comme on a mis la charrue avant les bœufs on ne s'intéresse plus a l'énumération des NP et cela dure depuis des siècles: Eratosthène qui reste la référence s'était bien avant JC. On peut peut être faire mieux avec 2000 ans de technologie?

On tombe sur un autre frein à la recherche
Newton a mis au point une méthode pour extraire la racine n éme d'un nombre. Si jamais vous chercher une autre méthode vous avez le droit a : Vous vous prenez pour un génie plus fort que Newton et tous les mathématiciens qui lui on succéder. Et malheureusement la faculté elle même est en première ligne. Alors que finalement vous n'avez fait que comme Félix vous avez observé et remarqué une particularité. Cela résout un problème vieux de 3000 ans ? Ce n'est pas le problème de Félix: il voulait juste gagner le defit!

Tiens juste pour rire: Si on écrivait en crible plus efficace et rapide que celui d'Eratosthène. Je prends les inscriptions! En si mettant tous on devrait faire mieux que les bouliers d'Eratosthène. Et a l'issue on présenterait le résultat aux scientifiques. Je suis sur que l'on aurait des surprises.

Boris

Citation:

---

Envoyé par Félix Guillemot

Il faut se méfier de ce qui parait évident ou que l'on croit savoir depuis toujours, c'est un frein à l'investiguation et là la recherche.

---

Entièrement d'accord

Mais à mon sens, au cas particulier, cette façon de réécrire les règles du SUDOKU (le fait que la somme des éloignements est toujours 12 ou 21) est redondant et n'apporte strictement rien de plus.
Je m'explique...
Il est vrai que quand je dis ça, je mets cette méthode (des éloignements) en concurrence avec celle qui consiste à éliminer les candidats indésirables dans chaque case
Prenons un exemple simple avec cet extrait de grille (4 régions ABDE)

Citation:

---

200|000
000|020
000|000
--------
002|000
000|000
000|002

---

Je peux déduire de ta théorie des éloignements, que l'éloignement entre les 2 des régions C et F est 12-(4+5)=3
Mais ça je le sais déjà vu que les seules lignes qui acceptent le candidat 2 en régions C et F sont les lignes 3 et 5 (éloignement 3 !)
On pourrait multiplier les exemples, on verrait que les possibilités qu'une valeur soit dans telle ou telle case seraient les mêmes avec les 2 méthodes

Citation:

---

Envoyé par FullSpeed

mick: sur quel fichier j'ai encore m....?

---

Citation:

---

Envoyé par FullSpeed

Si cela intéresse en PJ quelques miliiers de grilles

---

Voila !

Citation:

---

Envoyé par FullSpeed

J'ai vu que vous mettiez des images dans vos message
Comment les intègre-t-on: On me demande l'adresse d'un serveur.

---

J'ai pas fait comme OutOfRange : J'ai ajouté une piece jointe, et j'ai envoyé le message. Ensuite j'ai ouvert l'image, j'ai récupéré l'URL, j'ai édité mon message en ajoutant les balises [IMG]. Voila !

Felix Guillemot > Je suis d'accord, mais coder ta méthode deviendrait plus difficile que les autres methodes, car elle ne repose pas sur la meme logique (enfin, je pense pour moi) ... En gros, faudrait coder une méthode qui renvoie les lignes de chaque chiffre, rien que cette méthode doit etre assez lente ... Mais je suis sur qu'en partant sur d'autres bases, par exemple, la position de chaque chiffre dans la grille, on pourrait creer ta méthode. On verra ca apres le défi.

Bon, sinon, je suis en train de réécrire entierement mon solveur, pour le rendre plus propre, plus rapide, plus simple, et pour me permettre de coder plus facilement de nouvelles méthodes. Je viens juste d'apprendre a me servir de pointeurs ... :)

Citation:

---

Envoyé par FullSpeed

Franck peux tu nous donner tes tesmps(sans tricher pour AI)

---

Je les ai déjà donnés.

En fait, je ne triche pas complètement pour AI. Shail a déjà fait remarquer que les perfs pouvaient changer du tout au tout selon qu'on parcourt la grille dans le sens ligne/colonne ou colonne/ligne.
J'ai seulement ajusté l'ordre de parcour des cases (qui ressemble d'ailleurs à un ordre aléatoire) pour que mon solveur résolve AI le plus rapidement possible. Et d'ailleurs, ça a également profité à certaines autres grilles.

Citation:

---

Entièrement d'accord avec toi:
Petit exemple d'obscurantisme scientifique

---

Merci pour ton soutien. Moi je suis un fidèle de Descartes, et je me méfie donc des convictions. Ma théorie des éloignements soulève à mon avis plus de questions que cela. Une réponse expéditive en disant que cela n'apporte rien est à mon avis trop rapide.
Moi je crois que ça mériterait d'être creusé, mais bon, j'avoue que je n'ai pas trop le temps là maintenant.
C'est une piste que je donne, chacun en fait ce qu'il en veut.
Une remarque tout de même : lorsque j'ai le choix entre deux lignes et que le premier choix entraine un élognement de 2 et l'autre de 4, il y a à mon avis plus de probabilité pour que le 4 l'emporte. Ce genre de raisonnement pourrait mener à une algo pseudo intuitif qui conduit plus rapidemenent vers les solutions, plutôt que d'essayer au pif un scénario. IA...
Je dis ça je dis rien...

Citation:

---

Ce n'est pas le problème de Félix: il voulait juste gagner le defit!

---

Là par contre, tu te trompes complètement Boris.
J'ai proposé ce défi et tente de l'animer en tant que rédacteur sur le site.
Le but est de créer une émulation, et de s'amuser autour d'un thème qui me parait intéressant. Apparemment, je ne me suis pas trompé sur ce point.
Mon SusokuSokver est compilé depuis Janvier 2009, je ne l'ai pratiquement pas retouché depuis, défi ou pas.
Je n'ai aucune véléité de gain dans ce jeu, d'abord parce que je ne suis pas un participant mais celui qui propose une idée, ensuite parce que gagner ou perdre n'a aucune importance pour moi. Je ne gaspillerai aucune énergie à vouloir prouver que je suis le plus fort, ce qui est une cause futile et perdue d'avance (il y a tjs plus fort que soi).
Par contre, en tant qu'entrepreneur qui a de nombreux clients qui travaillent dans l'environnement Delphi, je cherche à repérer les bons éléments...
Dans ce cadre, il est normal que je ne sois pas uniquement focalisé sur les nano secondes.

Citation:

---

Envoyé par Félix Guillemot

C'est une piste que je donne, chacun en fait ce qu'il en veut.

---

Tout a fait, c'est pour cela qu'il serait interressant en fin de défi de réunir toutes ces pistes !

Citation:

---

Envoyé par Félix Guillemot

Une remarque tout de même : lorsque j'ai le choix entre deux lignes et que le premier choix entraine un élognement de 2 et l'autre de 4, il y a à mon avis plus de probabilité pour que le 4 l'emporte.

---

Hum ... On ne va pas repartir dans la discussion des probas, mais la proba d'avoir un éloignement de 2 et un eloignement de 4 est égale (dans ta config exacte ci dessus) ... Je n'en dirai pas plus ! Si tu veux en discuter, on va en MP pour pas pourrir le forum !

Citation:

---

Envoyé par Félix Guillemot

Citation:

---

Envoyé par FullSpeed

Ce n'est pas le problème de Félix: il voulait juste gagner le defit!

---

Là par contre, tu te trompes complètement Boris ...........

---

+1

Mick605 à écrit :
Mais alors quel est l'avantage d'un tableau de 81 cases sur un tableau 9*9 ?

Comme j'avais commencé par l'interface de remplissage des révélés, j'avais pensé à présenter ma grille à l'écran avec des TLabel auxquels j'avais associé pour chacun un numéro d'ordre de 1 à 81 par l'entremise de leur propriété Tag . Ainsi, l'affichage de la grille écran à partir de mon array de bytes en RAM (grille) était ultraspeed (avec la possibilité de jouer sur les polices des captions et les fonds de labels...) en plus la gestion des clics de souris sur les cases devenait ultra-aisée : TLabel cliqué -> numéro de case -> ligne/colonne/secteur...

Je n'avais pas commencé la partie solveur, mais j'avais dans l'idée d'associer à chaque case de la grille un array [1..9] plein au départ de toutes les possibilités qui devaient ensuite s'anéantir les unes après les autres au fur et à mesure de l'algorithme de vérification (ligne/colonne/secteur) pour finalement arriver à une seule solution par case... C'était la méthode logique main-crayon-cervelle de mon épouse... et elle était assez rationnelle. Mais elle m'avait fait remarquer que pour ce qu'elle désignait par "diaboliques", il était parfois impossible de la continuer sans faire d'hypothèses sur quelques cases que la logique ne pouvait déterminer a priori... Donc on devait finir sur du brute force pour quelques cases seulement...

Mais... mon épouse n'est plus là et je n'aime surtout plus le Sudoku. Et ma voie de réflexion n'était peut-être pas la meilleure.

Citation:

---

Envoyé par Rekin85

Mick605 à écrit :
Mais alors quel est l'avantage d'un tableau de 81 cases sur un tableau 9*9 ?

Comme j'avais commencé par l'interface de remplissage des révélés, j'avais pensé à présenter ma grille à l'écran avec des TLabel auxquels j'avais associé pour chacun un numéro d'ordre de 1 à 81 par l'entremise de leur propriété Tag .

---

Je ne sais pas ce que vous avez tous contre la pauvre StringGrid, mais bon :mouarf: !

Citation:

---

Envoyé par Franck SORIANO

Je les ai déjà donnés.

---

Pardon du dérangement...

Les temps publies tiennent sont donc avec ton reglage automatique
du sens de parcours.


Boris

Citation:

---

Comme j'avais commencé par l'interface de remplissage des révélés, j'avais pensé à présenter ma grille à l'écran avec des TLabel auxquels j'avais associé pour chacun un numéro d'ordre de 1 à 81 par l'entremise de leur propriété [B]Tag

---

C'est horrible ça !