Articles :
Création d'un système de chat en Pascal
Programmes :
Défi Pascal 2011 - Mon Tetris
Défi Pascal 2010 - Mon système de chat
Défi Delphi 2009 - Mon Sudoku Solver
Retrouvez mes différents projets sur ma page personnelle.
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
Si j'ais bien compris alors je suis un petit peut étonné, 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
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"
Le but, c'est pas forcément de trouver, c'est de chercher
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 !
Articles :
Création d'un système de chat en Pascal
Programmes :
Défi Pascal 2011 - Mon Tetris
Défi Pascal 2010 - Mon système de chat
Défi Delphi 2009 - Mon Sudoku Solver
Retrouvez mes différents projets sur ma page personnelle.
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.
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 :
- 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.
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
Papy
Nul ne pourra jamais vous empêchez d'être libre.
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
Papy
Nul ne pourra jamais vous empêchez d'être libre.
Bonjour
Damned !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
Choisir, c'est renoncer...
Attention ce n'est pas un concours d'optimisation
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.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 ...
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 ...
Articles :
Création d'un système de chat en Pascal
Programmes :
Défi Pascal 2011 - Mon Tetris
Défi Pascal 2010 - Mon système de chat
Défi Delphi 2009 - Mon Sudoku Solver
Retrouvez mes différents projets sur ma page personnelle.
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
Boris
Papy
Nul ne pourra jamais vous empêchez d'être libre.
Ouais, ca je suis d'accord, je voulais juste préciser pour le solveur logique !
Articles :
Création d'un système de chat en Pascal
Programmes :
Défi Pascal 2011 - Mon Tetris
Défi Pascal 2010 - Mon système de chat
Défi Delphi 2009 - Mon Sudoku Solver
Retrouvez mes différents projets sur ma page personnelle.
Articles :
Création d'un système de chat en Pascal
Programmes :
Défi Pascal 2011 - Mon Tetris
Défi Pascal 2010 - Mon système de chat
Défi Delphi 2009 - Mon Sudoku Solver
Retrouvez mes différents projets sur ma page personnelle.
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
Papy
Nul ne pourra jamais vous empêchez d'être libre.
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.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
Papy
Nul ne pourra jamais vous empêchez d'être libre.
Salut à tous,
j'ai envie de dire que n'importe quel algorithme est une méthode logique ou un ensemble de méthodes logiques.Envoyé par Félix Guillemot
Est ce que je me trompe?
Akim Merabet
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...
Vous avez un bloqueur de publicités installé.
Le Club Developpez.com n'affiche que des publicités IT, discrètes et non intrusives.
Afin que nous puissions continuer à vous fournir gratuitement du contenu de qualité, merci de nous soutenir en désactivant votre bloqueur de publicités sur Developpez.com.
Partager