Ben la en fait, je suis en stage, je suis fatigué et occupé, et donc mon projet avance pas beaucoup. J'espere juste que j'aurais le temps de finir avant la fin du défi...Citation:
Envoyé par FullSpeed
Version imprimable
Ben la en fait, je suis en stage, je suis fatigué et occupé, et donc mon projet avance pas beaucoup. J'espere juste que j'aurais le temps de finir avant la fin du défi...Citation:
Envoyé par FullSpeed
Bonsoir,
J'arrives bien tard pour vous saluer,
Bravo pour ce défi, mais j'aimerais savoir si j'ais bien lu, il sagit de trouver l'Algo et le programmer en Delphi pour résoudre toute grille de Sudoku.
En fait je comprends que tout langage pourraient convenir s'il ont quand même un peut de nerf, Delphi "C" Java etc encore faut'il l' algorithme ...
J'ais tout compris oui ou non :oops: :roll:
Si j'ais bien compris alors je suis un petit peut étonné, :roll: car il faudrait a mon sens courir dans les forums d' universitaires haut de gamme, mathématiciens etc ...
Car il me semble que si nous trouvions cet algorithme, nous aurions résolu des problémes en attente depuis des siécles :oops:
N'empéche que mordu du "C" je vais vous suivre comme si c'était solvable,
Aprés-tout, lorsque je ne sais plus quel postulat fut résolu, la presse se précipite et demande , a l ' inventeur :
"comment avez vous fait" et lui de répondre,
"heu moi je ne savais pas que ce n'était pas possible" :D
Le but, c'est pas forcément de trouver, c'est de chercher ;)Citation:
Envoyé par FoxLeRenard
Et, des algos de résolution de sudoku, ca a déjà été trouvé, pas forcément par la logique.
En mon sens, le plus interressant, c'est pas de recopier des trucs trouvés par d'autres, c'est de creer quelque chose de nouveau !
Je sais pas si le concours est ouvert pour d'autres langages, c'est a voir avec les orgas !Citation:
Envoyé par FoxLeRenard
Il faut trouver une méthode de résolution, mais pas seulement. Le sujet du défi, c'est de faire une appli avec une belle IHM qui permette de saisir les chiffres dans une grille de Sudoku, et en dernier lieu de résoudre la grille.Citation:
Envoyé par FoxLeRenard
Le défi ne porte pas que sur l'algo de résolution du Sudoku (mais si c'est évidemment une part importante du sujet).
Tu peux toujours t'amuser sur ce sujet, mais tu ne pourras pas participer officiellement (ta solution ne sera pas notée et tu ne seras pas classé) car :Citation:
Envoyé par FoxLeRenard
- C'est un Défi Delphi. La solution doit être codée en Delphi.
- Les membres de la rédaction (donc les modérateurs) ne peuvent pas participer.
Ok et merci de ton accueil :DCitation:
Envoyé par Franck SORIANO
Je reste donc et participes a une recherche d'algo, ensuite je regardes coté Delphi qui l'emportera ce sera intéressant ;)
Bon defi a toutes et a tous :ccool:
En fait il existe un certain nombre de méthodes mais le commun des mortels
que nous sommes ne les connait pas et donc on peut en créer ,en réinventant l'eau tiède éventuellement mais cela ne sera pas une copie et la recherche sera elle bien réelle
Ensuite c'est bien d'avoir les algos mais il faut les implanterai et chacun aaura sa solution. Si ta solution ne peut concourir pour des raisons diverses la publication de tes algos et leur implémentation sera enrichissante pour tous.
Il n'st pas juste, me semble-t-il, de dire que pour trouver un nouvel algo il faut etre Bac+7 . les inventions sortent parfois du CNRS mais pas toujours heureusement. C'est le propre du cerveau humain:tout le monde peut avoir une idée qui serve aix autres
Bonne programmation
Boris
Il semblerait que le problème de la vitesse suscite un certain nombre de polémiques. Etant un mordu de vitesse je ne prends pas ses commentaires pour moi, mais je vais essayé d’être l’avocat de la défense :
Il est clair dans le défit que la vitesse jouera un rôle important mais pas primordial. La qualité première d’un solveur reste sa vitesse. L’ IHM venant après
Etat des lieux :
Les solveurs les plus performants du marché sont TOUS des solveurs par contrainte (les candidats pour chaque case).Sur ce site on trouve quelques exemples
Le problème de ces solveurs est le manque de constance du temps de résolution (sujet déjà évoqué) et leur possible effondrement.
Vous avez dit vitesse ?
Il est plus simple de prendre des chiffres
Pour l’utilisateur un solveur agréable a utiliser travaille de l'ordre du dixième de secondes.. Au delà il s’agit de performances qui non pas de répercussions sur l’utilisateur : l’affichage de la réponse étant très ,nettement plus long
Pour un solveur logique le temps de résolution d’un problème difficile est de une a trois secondes sur le machines actuelles (mick605)
Apres on rentre dans le monde de la compétition.
Comme toute compétition on peut la trouver assez vaine : courir le 100 mètres en 9’6 ne change rien au sort des enfants de Bogotta. Mais les compétitions sont souvent le domaine de la recherche
Les performances ne sont plus du tout les mêmes ; un très bon solveur travaille au alentour de 30000 (trente mille), solutions seconde. Les remarquables à 50 000.
(Les sources du solver de GSF sont en C et en ligne. On trouve aussi facilement des sources en espagnol (c’est suffisamment rare pour le signaler))
Au milieu de tout cela vous avons notre défit. Il y aura nécessairement une solution qui sera la plus rapide. Ce n’est pas le but final mais nous aurons aussi celle qui utilise le moins de mémoire, le plus petit code…
Il faudra être bon partout y compris en vitesse.
J’ai bien sur le droit de me tromper dans mon exposé, mes chiffres datent un peu, mais j’espère que cela clarifiera quelques idées dans quelques cerveaux
Boris
Bonjour
Damned !Citation:
Envoyé par Franck SORIANO
Je n'ai pas lu ça dans les objectifs du défi :?
Les méthodes de résolution sont connues, elles sont basées sur l'élimination progressive de "candidats" et si on veut coder toutes ces méthodes, y a déjà un sacré boulot !
Quant à inventer une nouvelle méthode de résolution, ça me semble hors sujet, en tout cas pour participer au défi...
Maintenant, si y a des EINSTEIN parmi les abonnés à ce forum :aie: :mrgreen:
Attention ce n'est pas un concours d'optimisation :nono:Citation:
Envoyé par FullSpeed
La vitesse de résolution sera prise en compte, mais c'est tout. Pour le reste, les solutions seront jugées sur la qualité de leur IHM, leurs fonctionnalités originales, mais surtout sur l'élégance et la qualité du code !
Inutile d'essayer d'économiser le moindre octet en mémoire ou ligne de code.
Oui enfin je n'ai pas dit qu'il fallait trouver une nouvelle méthode. Tu peux très bien utiliser une technique déjà existante, ou basée sur plusieurs techniques existantes.Citation:
Envoyé par OutOfRange
L'important c'est bien d'arriver à coder une solution qui fonctionne !
Alors, j'imagine que tu veux parler de grilles tres difficiles ... Mais je tient a dire que, par la logique, je n'ai aucune grille qui prends plus d'une milliseconde a résoudre. Je tient a souligner que toutes les grilles ne sont pas résolues ...Citation:
Envoyé par FullSpeed
Et si en codant les autres solutions, je dépasse la seconde, ben, ca veut dire qu'il me manque pas mal d'optimisation !! (sans pour autant pousser bien loin)
Bon, faudrait que je le continue, ca fait un moment que je n'y touche pas ! Boulot oblige ...
Ce que je voulais dire c'est que la vitesse n'est pas le but principale
Mais quoique l'on dise ou fasse il y aura forcement un qui sera plus rapide, un plus petit un moins économe MEME si cela n'a pas d'importance
Il est évident que l'on ne demande pas de faire 30000 solutions seconde. Ce n'est pas le but. Si certains y arrivent bravo mais c'est tout.
S' ils arrivent à 1 milion s'est qu'il y a bien des Einstein sur le forum:ccool:
Boris
Ouais, ca je suis d'accord, je voulais juste préciser pour le solveur logique ;) !
Même de grilles comme AI a hypothèse ou alors tu entends justement des grilles sans hypothèses ?Citation:
Envoyé par mick605
Boris
Citation:
Envoyé par FullSpeed
Celles la ne sont pas résoluesCitation:
Envoyé par mick605
C'a y est j'ai compris ce que tu voulais dire !
Il y a de l'espoir peut etre que dans 10 ans si je persévère, je serai programmeur...
Boris
Je pense que si tu arrives à faire un solver logique qui résoud toutes les grilles, aucun autre solver non logique ne pourra être plus rapide, à effort d'optimisation de vitesse égale.Citation:
Mais je tient a dire que, par la logique, je n'ai aucune grille qui prends plus d'une milliseconde a résoudre. Je tient a souligner que toutes les grilles ne sont pas résolues ...
J'en suis arrivé là : Par la logique, mon solver résoud 99% des grilles que l'on trouve, et il met une milliseconde, ou un temps imperceptible pour le moins. J'ajoute : SANS AUCUN EFFORT D'OPTIMISATION DE CODE. Imagine si je l'optimise...
Dans le cas AI Escargot comme certains autres, mes méthodes logiques sont à court (il reste des cases avec 2 candidats ou +).
Donc, je suis obligé de poser une hypothèse et d'explorer un arbre de scenarii, et là ça prend qq millisecondes de plus...
Le fait de construire un arbre d'hypothèses n'est-ce pas là une méthode logique ? : Si je pose transforme un des deux candidats en révélé, alors, etc.
je n'ai actuellement pas le temps de chercher une autre méthode logique mais je pense qu'elle existe. Et ce n'est pas parce que personne ne l'a trouvée qu'elle n'existe pas.
Prenons AI escargot à ce stade de résolution :
100007090
030020008
009600500
005300900
010080002
600004000
300000010
041000007
007000300
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...
Comme on est déjà bien avancé dans le défi Delphi, je précise que ma première phase de résolution par la logique, est composée de 4 méthodes logiques, pas une de +
A priori a lire les régies du SODOKU il n'existe que deux cas dans lesquels on peu renseigner une case: soit la case est la seule de son sous ensemble a
acceptée une valeur donnée; soit la case n'accepte qu'une seule valeur.
Âpres il existe des méthodes qui permettent elles de diminuer le nombre de candidats possibles pour une case donnée et conséquement le but est de provoquer la situation 1 ou 2
FLX quand tu parles de 4 méthodes tu entends 4 cas pour renseigner une case ou 2 de chaque? (il existe des variantes des deux cas avec les paires cachées par exemple)
J'avoue que j'ai hâte de voir vos méthodes car moi je butte sur les parcours incessants des 81 cases.
Boris
Salut à tous,
j'ai envie de dire que n'importe quel algorithme est une méthode logique ou un ensemble de méthodes logiques.Citation:
Envoyé par Félix Guillemot
Est ce que je me trompe?
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".Citation:
Envoyé par FullSpeed
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...
en fait, c'est une question de language. Dans cette discussion, on a pris l'habitude d'appeler méthode logique des techniques de déductions logiques, en opposition avec des algorithmes qui génèrent aléatoirement des nombres par exemple et qui semblent plus rapide... en apparence :)Citation:
Envoyé par Kaféine
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
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
(au début quoi ! presque me direz vous ;) )Citation:
Envoyé par Félix Guillemot
Je cherche ca depuis un moment ...Citation:
Envoyé par Félix Guillemot
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 :
Merci ;) !Code:
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
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 ;) !
Si, mais la encore, un humain va pas poser 18 hypotheses, il en pose 1 voir 2, et apres ...Citation:
Envoyé par Félix Guillemot
: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
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 ...Citation:
Envoyé par FullSpeed
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 :
-->Méthode profonde : 3msCode:
2
3
4
5
6
7
8
9
2eme :
-->Méthode profonde : 5msCode:
2
3
4
5
6
7
8
9
3eme :
-->Méthode profonde : 2msCode:
2
3
4
5
6
7
8
9084010590 056009000 009050040 040500938 000000000 931004070 090040700 000900450 075080360
4eme :
-->Méthode profonde : 70msCode:
2
3
4
5
6
7
8
9
(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 !
Ben oui mais ce n'est pas optimal tout ça...Citation:
Envoyé par ShaiLeTroll
c'est une méthode de bourrin, sans vouloir vexer :ccool:
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 :
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.Citation:
Propreté du code : documentation (commentaires), indentation, modularité, enfin bref : on enlève les moufles .
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 !
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
Dans ma solution, j'en utilise encore moins :mrgreen:Citation:
Envoyé par mick605
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.
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).Citation:
Envoyé par mick605
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...).
Félix tu exagères !Citation:
Envoyé par Félix Guillemot
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 !
La vraie vie ?Citation:
Envoyé par Félix Guillemot
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) ;)
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.Citation:
Envoyé par OutOfRange
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
Code:
2
3
4
5
6
7
8
9
10
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"
J'ai bien compris ca ...Citation:
Envoyé par Félix Guillemot
Moi : Logique seulement en 1.0 millisecondeCitation:
Envoyé par Félix Guillemot
Moi : Resolu seulement par la logique : 1.4 milliseconde.Citation:
Envoyé par Félix Guillemot
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
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 ...)Citation:
Envoyé par Félix Guillemot
Une question : pourquoi cette différence ENORME de temps pour AI Escargot ?
Ah ouais :DCitation:
Envoyé par Franck SORIANO
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 ;)Citation:
Envoyé par Franck SORIANO
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 ...
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
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
D6 sous XP avec un core 2 duo a 2,4 GHTZ et 2 Gigas de RAMCode:
2
3
4
5
6
7
8
9
10
11
Boris
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
Tenez une petite grille sympathique nommée Easter Monster:
C'est une grille à solution unique. Elle est à mon avis aussi complexe (peut-être plus) qu'AI Escargot. :mrgreen:Citation:
100000002
090400050
006000700
050903000
000070000
000850040
700000600
030009080
002000001
@+ Claudius
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
Mais non, bien sûr, tout le monde peut jouer !Citation:
Envoyé par OutOfRange
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...
C'est pas mal, mais moi perso, je ne sais pas ce que sont les CoreCellDummies.Citation:
Code:
2
3
4
5
6
7
8
9
10
Considères-tu ce genre de code comme compréhensible et maintenable :mouarf:, faut peut-être que j'y ajoute des commentaires utiles :roll:
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...
Citation:
Envoyé par mick605
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.