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

Version imprimable

Voir 40 message(s) de cette discussion en une page

15/07/2009, 17h33
FullSpeed

Oeuf ou Poule

D'accord avec toi AKIM l'ordinateur est un e machine logique
et a partir du moment où on s'en sert on est obligé de suivre sa logique, donc de réfléchir et quelque soit le résultat cela sera celui d'un raisonnement
Il est cependant habituel en info de considéré que ne sont pas logiques (dans le sens de la réflexion pour les concevoir) les algos type Brute Forcce. Mais une certaine confusion existe sur les Brutes Force
Pour notre Sudoku un Brute force consisterait a essayé toutes les combinaisons des 81 cases jusqu'à en trouver une qui aille avec les reveles : il faudrait des millénaires de calculs: imagine un nombre de 81 chiffres(128 bits en gros)= !34

Dans certains milieux de la recherche on commence a parler de méthodes naïves Par exemple pour rechercher des nombres premiers a prime abord
on le divise par tous les entiers positifs inférieurs. C'est la méthode naïve
En réalité on commence par éviter tous les nombres pairs, les multiples de 5 et on ne dépasse pas la racine carrée du nombre. C'est toujours la méthode naïve des divisions mais passablement améliorée.
Cette notion de naïve me semble intéressante.

Alors cela ne va pas être facile pour les juges. Je prends un solveur par contrainte:tu pars de la case 1 tu enleves des 9 valeurs possibles celle qui sont dans la rangée, la colonne et la région. Rien que la notion de région est intelligente et nécessite un raisonnement (mémé si on utilise une formule)
Une fois enlevé les valeurs je regarde celles sui reste . Si il y en a je pplace unb offset sur la liste que je sauvegarde......C'est loin d'une logique aveugle et primaire. En essayant les candidats j fais des hypothéses alors le solveur il est quoi?

Enfin nous notre défit s'est d'en écrire un pas de le classifié.
Boris

Salut

Citation:

Envoyé par Félix Guillemot

C'est exactement ce que tu décris : j'utilise deux méthodes pour déduire un révélé à partir d'une case de candidats (celles que tu décris (1 et 2)) et deux méthodes pour réduire le nombre de candidats dans les cases et provoquer l'utilisation des "situations 1 et 2".

J'aime bien ta formalisation des choses, je trouve ça intéressant. Je n'utilise que 2 méthodes pour provoquer 1 et 2 mais peut être quen en ajoutant d'autre, on peut exploser tous les sudokus...

Tu utilises seulement deux méthodes permettant de réduire le nb de candidats ? Je serais curieux de voir quelles sont ces méthodes. Parce qu'avec seulement deux méthodes, on va pas bien loin (il me semble). A moins que ce soit des procedures treeeeeees générales, et la, ok ...

Citation:

Envoyé par Félix Guillemot

Prenons AI escargot à ce stade de résolution :

100007090
030020008
009600500
005300900
010080002
600004000
300000010
041000007
007000300

(au début quoi ! presque me direz vous ;) )

Citation:

Envoyé par Félix Guillemot

C'est précisément là qu'on bloque avec la logique (détrompez-moi sinon).
Y-a-t-il une méthode logique pour avancer à ce stade ?. Ce Défi m'intéresse beaucoup...

Je cherche ca depuis un moment ...
J'étais tombé sur un site sur lequel le type le résoud avec la logique et .............. suspense ........... ben il est bloqué comme toi et il poses 2 hypotheses :? :? ! Si je retrouve le lien, je te le ferais passer ;)

Mais je suis SUR que c'est possible !

Félix Guillemot > pour revenir a ton solveur logique, peux tu me dire simplement si ces grilles sont résolues par la logique avec ton solveur :
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 1ere : 500004200 100020030 090000005 000400000 805196302 000005000 400000060 030070009 007300008 2eme : 020001030 800900001 000060400 009600180 300000007 087003900 006090000 100006008 050300010 3eme : 084010590 056009000 009050040 040500938 000000000 931004070 090040700 000900450 075080360 4eme : 100007090 030020008 009600500 005300900 010080002 600004000 300000010 040000007 007000300
Merci ;) !

Edit :
Pour l'histoire de logique : quand je dis un solveur logique, c'est un solveur qui se comporte comme un humain en fait. Un humain ne va pas tester toutes les valeurs dans toutes les cases ;) !

Citation:

Envoyé par Félix Guillemot

Le fait de construire un arbre d'hypothèses n'est-ce pas là une méthode logique ?

Si, mais la encore, un humain va pas poser 18 hypotheses, il en pose 1 voir 2, et apres ...

15/07/2009, 19h28
ShaiLeTroll

Citation:

Envoyé par FullSpeed

Alors cela ne va pas être facile pour les juges. Je prends un solveur par contrainte:tu pars de la case 1 tu enleves des 9 valeurs possibles celle qui sont dans la rangée, la colonne et la région. Rien que la notion de région est intelligente et nécessite un raisonnement (mémé si on utilise une formule)

:mouarf: On dirait exactement mon solveur, ce qui ne fonctionne pour les grilles dites "faciles", j'ai pas bossé dessus depuis la dernière fois ... où justement je dois implémenté la suite :

Citation:

Envoyé par FullSpeed

Une fois enlevé les valeurs je regarde celles sui reste . Si il y en a je pplace unb offset sur la liste que je sauvegarde......C'est loin d'une logique aveugle et primaire. En essayant les candidats j fais des hypothéses alors le solveur il est quoi?

Cette technique reste purement logique puisqu'une fois avoir éliminé les cas impossibles, tu tentes des valeurs parmis une liste de valeur possible restante, et au final, tu vas tester toutes les configurations de grilles possibles, ça en fait un paquet, mais heureusement, il est inutile de générer toute la grille pour se rendre compte qu'elle est incorrecte ...
15/07/2009, 19h41
Félix Guillemot
Mick,

Comme je te l'ai expliqué, mon algo se décompose en deux phases :
1) Il essaye récursivement les déductions logiques décrites précedemment

2) Si il n'en vient pas à bout comme ça, il essaye ce que j'appelle la méthode profonde, où il pose une hypothèse, explore un scénario etc récursivement.

1ere :
Code:

1 2 3 4 5 6 7 8 9 500004200 100020030 090000005 000400000 805196302 000005000 400000060 030070009 007300008
-->Méthode profonde : 3ms

2eme :
Code:

1 2 3 4 5 6 7 8 9 020001030 800900001 000060400 009600180 300000007 087003900 006090000 100006008 050300010
-->Méthode profonde : 5ms

3eme :
Code:

1 2 3 4 5 6 7 8 9 084010590 056009000 009050040 040500938 000000000 931004070 090040700 000900450 075080360
-->Méthode profonde : 2ms

4eme :
Code:

1 2 3 4 5 6 7 8 9 100007090 030020008 009600500 005300900 010080002 600004000 300000010 040000007 007000300
-->Méthode profonde : 70ms
(mais c'est AI Escargot ça ?)

Voila, donc les 4 grilles nécessitent l'emploi des hypothèses, ce que j'appelle dans mon propre jargon la méthode profonde.
Tu remarques que même en utilisant ce "patch" qu'est la méthode profonde, et sans optimiser avec un PC de 2005, zéro optimisation, ça carbure...

Imagine si tu trouves la déduction logique qui évite le patch...

Franchement si c'est pas du défi ça !
15/07/2009, 19h44
Félix Guillemot

Citation:

Envoyé par ShaiLeTroll

:mouarf: On dirait exactement mon solveur, ce qui ne fonctionne pour les grilles dites "faciles", j'ai pas bossé dessus depuis la dernière fois ... où justement je dois implémenté la suite :

Cette technique reste purement logique puisqu'une fois avoir éliminé les cas impossibles, tu tentes des valeurs parmis une liste de valeur possible restante, et au final, tu vas tester toutes les configurations de grilles possibles, ça en fait un paquet, mais heureusement, il est inutile de générer toute la grille pour se rendre compte qu'elle est incorrecte ...

Ben oui mais ce n'est pas optimal tout ça...
c'est une méthode de bourrin, sans vouloir vexer :ccool:
15/07/2009, 20h01
Félix Guillemot

Rappel aux participants

En tant que juge, je rappelle qu'il ne suffit pas de pondre un algo qui marche et rapide (attention je n'ai pas dit qu'il ne fallait pas faire des efforts d'optimisation, j'ai dit que ce n'était pas SUFFISANT), le code doit être compréhensible et maintenable, comme indiqué dans les règles :

Citation:

Propreté du code : documentation (commentaires), indentation, modularité, enfin bref : on enlève les moufles .

Replacez vous dans la vraie vie : vous effectuez une prestation chez un client, vous codez le solveur et vous partez. Le code doit être maintenable, compréhensible pour celui qui viendra derrière vous.
Si les développeurs ont mauvaise presse aujourd'hui et que les grilles de tarifs sont basses, c'est principalement parce qu'ils sont considérés comme des pisseurs de lignes, des ouvriers en bleu de travail de l'informatique, une population dont je suis le défenseur (voir mon bouquin).

L'exercice du défi consiste entre autre à repérer des bons développeurs, qui ne sont pas (mais doit-on le répéter sans cesse) des "rain-man" du code, mais des gens ouverts, qui comprennent les besoins des utilisateurs, ont conscience qu'ils fabriquent des outils que ces mêmes utilisateurs utilisent, que le code est un patrimoine qui se partage, que l'on doit s'exprimer en bon Français.

Show me what you can do !
15/07/2009, 20h18
FullSpeed

Chrono

Je suis un peu surpris par les temps que vous donnez:
On utilise la même milli seconde?
A priori il faut au moins une foiis balayer les 81 cases et calculé le nombre de candidats afin de savoir s'il est seul ou obligés
J'avoue ne pas être capable de faire cela dans la microseconde
On peut voir? (un peu)
Perso j'ai fini le solveur lui meme, j'attaque l'IHM
(Pas si bourrin que cela mais 81 proc et 81 repeat quand meme!

Boris
15/07/2009, 20h37
Franck SORIANO

Citation:

Envoyé par mick605

Tu utilises seulement deux méthodes permettant de réduire le nb de candidats ? Je serais curieux de voir quelles sont ces méthodes. Parce qu'avec seulement deux méthodes, on va pas bien loin (il me semble). A moins que ce soit des procedures treeeeeees générales, et la, ok ...

Dans ma solution, j'en utilise encore moins :mrgreen:
En fait, je vais parfois même jusqu'à commencer à poser des hypothèses alors qu'il reste des cases "évidentes" (un seul candidat possible) qui pourraient être remplies avant.

Citation:

Envoyé par mick605

Mais je suis SUR que c'est possible !

A mon avis, tu t'avances bien vite... Je ne vois pas pour quelle raison une grille devrait forcément se résoudre par la seule logique (disons sans poser d'hypothèse).

Maintenant si on se place dans le strict context du défi, je peux te garantir qu'il n'est pas possible de résoudre n'importe quelle grille par la pure logique. Ceci pour une raison toute simple : La logique ne peut pas résoudre les grilles à solutions multiples. Certes ce n'est plus une grille de Sudoku, mais ce type de grille n'est pas interdit dans le cadre de ce défi !

Après évidemment, dès que tu acceptes l'idée de poser des hypothèses, tu peux résoudre n'importe quoi puisque l'algorithme peut dégénérer en British museum (ou brute force si vous préférer...).

Citation:

Envoyé par Félix Guillemot

1ere :
-->Méthode profonde : 3ms

2eme :
-->Méthode profonde : 5ms

3eme :
-->Méthode profonde : 2ms

4eme :
-->Méthode profonde : 70ms

Félix tu exagères !
Ce n'est pas le moment de dévoiler ta solution :aie:

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:)

Par contre, je ne vous en dirais pas plus sur la méthode que j'utilise. Bon aller si, cette version est multi-threadée (mais honêtement, j'ai honte de la façon dont je l'ai multi-threadée).
Il faut bien que le défi conserve un peu de son mystère !
15/07/2009, 21h42
OutOfRange

Citation:

Envoyé par Félix Guillemot

En tant que juge, (...)
Replacez vous dans la vraie vie : vous effectuez une prestation chez un client, vous codez le solveur et vous partez. Le code doit être maintenable, compréhensible pour celui qui viendra derrière vous.
Si les développeurs ont mauvaise presse aujourd'hui et que les grilles de tarifs sont basses, c'est principalement parce qu'ils sont considérés comme des pisseurs de lignes, des ouvriers en bleu de travail de l'informatique, une population dont je suis le défenseur (voir mon bouquin).

La vraie vie ?
Moi ma vraie vie professionnelle elle est à des gigaoctets de la moindre ligne de code !
Ce défi ne s'adresse-t-il qu'aux pro des algos ? :cry:
Faut-il faire un soft commercialisable ???
Pas grave, je proposerai quand même mon prog des week ends pluvieux et des soirées sans téloche :mrgreen:
Signé : un vieil autodidacte passionné (mon premier ordi c'était un Amstrad 464 avec 48 Ko de mémoire vive - j'ai bien dit - et sauvegarde périlleuse de fichiers séquentiels sur cassette) ;)
15/07/2009, 22h08
Franck SORIANO

Citation:

Envoyé par OutOfRange

Ce défi ne s'adresse-t-il qu'aux pro des algos ? :cry:
Faut-il faire un soft commercialisable ???
Pas grave, je proposerai quand même mon prog des week ends pluvieux et des soirées sans téloche :mrgreen:

Bien sûr que non. Toute participation est la bienvenue. Que tu sois professionnel, étudiant, ou simple bricoleur du dimanche, du moment que tu proposes une solution en Delphi et que tu respectes les règles du Défi.

D'ailleurs, j'ai comme un doute que la majorité des developpeurs Delphi soit composée de prestataires (ou d'indépendants ;)) qui travaillent en mission chez un client.

Citation:

Envoyé par Félix Guillemot

En tant que juge, je rappelle qu'il ne suffit pas de pondre un algo qui marche et rapide..., le code doit être compréhensible et maintenable, comme indiqué dans les règles
Code:

1 2 3 4 5 6 7 8 9 10 {* ----------------------------------------------------------------------------- Accesseur de CoreCellDummies ------------------------------------------------------------------------------ } function TSudokuSolver.GetCoreCellDummies(ACore: Integer; ACol, ARow: Byte): TByteDynArray; begin if FCoreStored then Result := BuildCellDummies(PSudokuSolverDataStruct(FCores.Items[ACore])^, ACol, ARow) else Result := CellDummies[ACol, ARow]; end;
Considères-tu ce genre de code comme compréhensible et maintenable :mouarf:, faut peut-être que j'y ajoute des commentaires utiles :roll:

Si c'était pour le boulot, dans un projet que j'aime bien (avec un Chef de Projet que j'aime bien aussi), je prendrais soin à découper le plus que possible, à ne pas utiliser directement des TList mais d'en hériter pour un typage fort de chaque list (idem pour les TObjectList) et une facilité de lecture (pas de ^, de Cast, de As, ... en dehors des accesseurs des dites listes), je m'occupe de mon sudoku un petit peu le soir (au bureau, pas ordi à la maison, pour le moment j'y ai consacré 7h, pas trop le temps de tout faire beau, une fois que ça fonctionnera, je ferais mieux), là je suis content, j'ai vu où bloque mon algo, je peux donc bosser moi aussi ma résolution "profonde" ...

Franck SORIANO,Ces Temps sont impressionnants, pour le moment, mon Solver ne résoud pas ces Grilles, mais pour la Phase "Simple" c'est entre 150µs et 225µs pour résoudre une Grille Facile ou Normale, et c'est entre 15µs et 150µs que l'algo s'arrête si la Grille est Difficile et que ça doit passer à la Phase "Profonde"

16/07/2009, 02h12
mick605
Citation:

Envoyé par Félix Guillemot

Mick,

Comme je te l'ai expliqué, mon algo se décompose en deux phases :
1) Il essaye récursivement les déductions logiques décrites précedemment

2) Si il n'en vient pas à bout comme ça, il essaye ce que j'appelle la méthode profonde, où il pose une hypothèse, explore un scénario etc récursivement.

J'ai bien compris ca ...
Citation:
Envoyé par Félix Guillemot

1ere :

Code:

1 2 3 4 5 6 7 8 9 500004200 100020030 090000005 000400000 805196302 000005000 400000060 030070009 007300008

-->Méthode profonde : 3ms
Moi : Logique seulement en 1.0 milliseconde
Citation:
Envoyé par Félix Guillemot

2eme :

Code:

1 2 3 4 5 6 7 8 9 020001030 800900001 000060400 009600180 300000007 087003900 006090000 100006008 050300010

-->Méthode profonde : 5ms
Moi : Resolu seulement par la logique : 1.4 milliseconde.
Citation:
Envoyé par Félix Guillemot

3eme :

Code:

1 2 3 4 5 6 7 8 9 084010590 056009000 009050040 040500938 000000000 931004070 090040700 000900450 075080360

-->Méthode profonde : 2ms

4eme :

Code:

1 2 3 4 5 6 7 8 9 100007090 030020008 009600500 005300900 010080002 600004000 300000010 040000007 007000300

-->Méthode profonde : 70ms
(mais c'est AI Escargot ça ?)
Les deux dernieres ne sont pas résolues avec la logique ... (j'avais pas vu pour la derniere :mrgreen:)

Citation:

Envoyé par Félix Guillemot

Voila, donc les 4 grilles nécessitent l'emploi des hypothèses, ce que j'appelle dans mon propre jargon la méthode profonde.
Tu remarques que même en utilisant ce "patch" qu'est la méthode profonde, et sans optimiser avec un PC de 2005, zéro optimisation, ça carbure...

Imagine si tu trouves la déduction logique qui évite le patch...

Franchement si c'est pas du défi ça !

Hehe ... Je t'ai donné quelques grilles de la plus simple a la plus dure niveau méthode de résolution qui m'ont bien fait galerer au debut (et qui me font toujours galerer d'ailleurs) ... Et tu vois, logique seulement !! Il me manque a trouver pour la 3eme (la 4eme on verra plus tard ...)

Une question : pourquoi cette différence ENORME de temps pour AI Escargot ?

Citation:

Envoyé par Franck SORIANO

Dans ma solution, j'en utilise encore moins [de méthodes logiques]
En fait, je vais parfois même jusqu'à commencer à poser des hypothèses alors qu'il reste des cases "évidentes" (un seul candidat possible) qui pourraient être remplies avant.

Ah ouais :D

Citation:

Envoyé par Franck SORIANO

A mon avis, tu t'avances bien vite... Je ne vois pas pour quelle raison une grille devrait forcément se résoudre par la seule logique (disons sans poser d'hypothèse).

Je sais pas ... Une intuition ... Je me dis que, pour trouver AI Escargot, ils ont pas placé des chiffres au pif et vérifié l'unicité ensuite ... A mon avis, ils les ont placé en vérifiant "quelque chose" a chaque fois. Mais le "quelque chose", c'est quoi ? Et a mon avis, si on fait la méthode inverse de ce "quelque chose", ben on pourrait la résoudre ;)

Je sais pas si j'ai été bien clair ...

OutOfRange > A la vue de mon age, tu peux en déduire que pour moi, la vie professionnelle, ben elle en est meme pas au début ;)

Bon sinon, j'ai une petite idée pour mon solveur qui, je pense, va réduire le temps de résolution d'un tiers minimum ...
16/07/2009, 08h10
OutOfRange

Question aux organisateurs

Bonjour

Vu que tout le monde se tire la bourre sur les temps de résolution...
et vu que la rapidité sera un des éléments pris en compte
et vu que je n'ai pas le temps de me mettre à l'assembleur :aie:
Quel est le temps raisonnable à ne pas dépasser pour une grille selon son niveau
Mon solveur est loin d'être une formule 1 :(
Et j'ai encore pas mal de méthode à coder, même si j'ai quelques pistes pour éviter des boucles inutiles

Multitread

Franck tu poses le problèmes des treads
Celles ci font parties integrante de Dephi donc leur usage est surement autorisé
Le problème se pose avec les multi coeur
Ta tread a de forte chance de se retrouver sur un coeur inactif
et la en toute honnêteté tu vas te servir de plusieurs processeurs
et fausser les chronométrage.
De plus on peut integrer dans l'algo la notion de partage et trouver un algo que le hard fera aller plus vite
Boris

PS tu donnes quelques chronos (quio ne revelen-t rien de ta méthode
Pourrais tu donner la technique de chronometrage que tu utilise?
Je crois avoir le meme pros que toi C'est juste pour parler de la meme chose

Moi je fais comme cela
Code:

1 2 3 4 5 6 7 8 9 10 11 procedure TGenereW.BSolveClick(Sender: TObject); var j: integer; begin chrono := gettickcount; for j := 1 to 10 do //je fais varier le 10 pour avoir 1000 en resultat Bf_Solver(pb);// soit une seconde Generew.Caption := IntTostr(((gettickcount) - chrono)); affiche_Quoi(Solution); end; pro
D6 sous XP avec un core 2 duo a 2,4 GHTZ et 2 Gigas de RAM
Boris

16/07/2009, 09h16
FullSpeed

AI EsCaegeot

Mick

Voila comment a priori les joueurs résolvent Ai
Ils sont bien sur obligés de faire des hypothèses
Le problème est de savoir laquelle

Il a plusieurs méthodes mais la plus 'efficace' est celle la: tu cherche sur le grille le sous-ensembles qui a le moins de candidat pour AI c'est C3 . Donc ils posent arbitrairement 2 en case 3 puis passent en C12,C39....
C'est un EXEMPLE la méthode n'est pas obligatoire ou systematique .

Boris
16/07/2009, 10h57
Cl@udius

Tenez une petite grille sympathique nommée Easter Monster:

Citation:

100000002
090400050
006000700
050903000
000070000
000850040
700000600
030009080
002000001

C'est une grille à solution unique. Elle est à mon avis aussi complexe (peut-être plus) qu'AI Escargot. :mrgreen:

@+ Claudius
16/07/2009, 11h08
ShaiLeTroll

Ouch, pour l'algo que j'ai prévu, je confirme c'est bien un "Monstre", à la fin de la résolution simple, il ne reste que des Triplets de Candidats alors que sur AI Escargot, il reste encore des Paires à résoudre ...

Remplace GetTickCount par QueryPerformanceCounter, car il y a souvent 15-16ms qui se perdent dans la nature avec GetTickCount ce qui n'arrive pas avec QueryPerformanceCounter
16/07/2009, 12h16
Félix Guillemot

Citation:

Envoyé par OutOfRange

La vraie vie ?
Moi ma vraie vie professionnelle elle est à des gigaoctets de la moindre ligne de code !
Ce défi ne s'adresse-t-il qu'aux pro des algos ? :cry:
Faut-il faire un soft commercialisable ???
Pas grave, je proposerai quand même mon prog des week ends pluvieux et des soirées sans téloche :mrgreen:
Signé : un vieil autodidacte passionné (mon premier ordi c'était un Amstrad 464 avec 48 Ko de mémoire vive - j'ai bien dit - et sauvegarde périlleuse de fichiers séquentiels sur cassette) ;)

Mais non, bien sûr, tout le monde peut jouer !
Mais le but du jeu est de proposer une solution qui tiens la route tant au niveau des performances, de l'interface, de la façon dont c'est fait, etc.
bref, voir les règles.
Je voulais juste dire que programmer en professionel aujourd'hui, c'est respecter une certaine hygiène de code, mais ceci est autre débat...

Citation:
Code:

1 2 3 4 5 6 7 8 9 10 {* ----------------------------------------------------------------------------- Accesseur de CoreCellDummies ------------------------------------------------------------------------------ } function TSudokuSolver.GetCoreCellDummies(ACore: Integer; ACol, ARow: Byte): TByteDynArray; begin if FCoreStored then Result := BuildCellDummies(PSudokuSolverDataStruct(FCores.Items[ACore])^, ACol, ARow) else Result := CellDummies[ACol, ARow]; end;
Considères-tu ce genre de code comme compréhensible et maintenable :mouarf:, faut peut-être que j'y ajoute des commentaires utiles :roll:
C'est pas mal, mais moi perso, je ne sais pas ce que sont les CoreCellDummies.
j'utilise aussi la langue anglaise dans les noms de procs etc, je pense que c'est le mieux dans ce monde et pour rester dans les standards.
Par contre, tu pourrais dire rapidement ce que fait ta fonction, commenter la déclaration du TByteDynArray.
je dis ça comme ça...

16/07/2009, 12h35
Félix Guillemot

Citation:

Envoyé par mick605

J'ai bien compris ca ...

Moi : Logique seulement en 1.0 milliseconde

Moi : Resolu seulement par la logique : 1.4 milliseconde.

Les deux dernieres ne sont pas résolues avec la logique ... (j'avais pas vu pour la derniere :mrgreen:)

Hehe ... Je t'ai donné quelques grilles de la plus simple a la plus dure niveau méthode de résolution qui m'ont bien fait galerer au debut (et qui me font toujours galerer d'ailleurs) ... Et tu vois, logique seulement !! Il me manque a trouver pour la 3eme (la 4eme on verra plus tard ...)

Une question : pourquoi cette différence ENORME de temps pour AI Escargot ?

Ah ouais :D

Je sais pas ... Une intuition ... Je me dis que, pour trouver AI Escargot, ils ont pas placé des chiffres au pif et vérifié l'unicité ensuite ... A mon avis, ils les ont placé en vérifiant "quelque chose" a chaque fois. Mais le "quelque chose", c'est quoi ? Et a mon avis, si on fait la méthode inverse de ce "quelque chose", ben on pourrait la résoudre ;)

Je sais pas si j'ai été bien clair ...

Pour moi, en tout cas, c'est tout à fait clair !!!
Je dois dire que je suis bluffé par ta maturité de réflexion à 18 ans !
Ton raisonnement est excellent, tu viens de redécouvrir un concept labyrinthique. Il est clair que si tu pars du coeur du labyrinthe, tu vas trouver la sortie alors qu'en passant par l'entrée, c'est plus complexe évidemment, ce n'est pas qu'une intuition, tu l'as raisonnée.

Ce n'est pas une intuuition pour moi, c'est une quasi certitude (disons que je laisse 0.0001% de chance au cas où :)) : Si un sudoku n'a qu'une solution, il DOIT pouvoir être résolu avec une méthode logique, et c'est précisément là qu'il y a un enjeu dans ce défi.

C'est normal qu'on avance dans le raisonnement au fil des semaines...

Imaginez que Mick trouve LA méthode logique qui manque pour vaincre AI Escargot et qu'ensuite on optimise le tout avec Full Speed ou Franck, je crois qu'on tient là un bel article, et je vous promets d'en faire la promotion !

Déjà, tu as prouvé que les grilles 1 et 2 étaient résolues par la logique, et tu as battu mes temps, ce qui me semble normal.
C'est très bien ça.

Pourquoi AI Escargot 70ms ?

Ce n'est certainement pas par hasard que c'est la grille dite la plus dure du monde !

Pour reprendre ce qu'écrivait Franck : je ne compte pas les grilles à plusieurs solutions dans celles qui devraient être résolues par la logique. J'ai oublié de le préciser, même si le solver doit les prendre en charge.

C'est l'alliance de la méthode avec le talent d'optimisation qui fera le meilleur solver, avec tous les pré-requis en plus.

Voir 40 message(s) de cette discussion en une page