• Aide à la navigation du site
  • Générez des revenus avec vos codes, scripts et tutoriaux
  • CodyxBot, le Bot GTalk & MSN qu'il vous faut !
  • RSS CodeS-SourceS
  • C / C++ / C++.NET CodeS-SourceS
begin process at 2008 07 05 07:04:20
1 205 054 membres
40 nouveaux aujourd'hui
14 118 membres club
Vous ne trouvez pas de réponse à votre problème ? Alors posez la question dans le forum.
Souvenez-vous qu'il n'y a jamais de question bête, mais rester dans l'ignorance parce que l'on n'ose pas poser une question, ça c'est une erreur !

CREATION DE SUDOKU DIFFERENTS NIVEAUX ET RESOLUTION


Information sur la source

Catégorie :Jeux Classé sous : sudoku, résolution, niveaux, jeu, création Niveau : Débutant Date de création : 19/11/2005 Date de mise à jour : 17/02/2008 01:20:46 Vu / téléchargé: 32 937 / 6 324
Auteur : sullyper Site perso
Ecrire un message privé
Note :
9,4 / 10 - par 10 personnes
9,40 / 10

  • 1

  • 2

  • 3

  • 4

  • 5

  • 6

  • 7

  • 8

  • 9

  • 10
Commentaire sur cette source (72)
Ajouter un commentaire et/ou une note

Description

2 petites sources qui permettent :
l'une crée des sudoku de 4 niveaux différents (garantissant une solution possible)
l'autre sésolve les sudoku, elle affiche à l'écran q'une de toutes les possibilités, mais écrit toutes les autres dans un fichier texte.

Le premier programme qui crée, affiche à l'écran, mais l'écrit également dans un fichier texte sour la forme de chiffre dont le 0 correspond à une case vide. "sudoku.in"
le deuxième lit le sudoku via le fichier "sudoku.in", ce qui vous permet de rentrer votre propre sudoku dans ce fichier pour qu'il le résolve, il sort toutes les solution dans le fichier "sudoku.out"...

Ne vous amusez pas à rentrer une grille vide (que avec des 0), car il y a plus de 6 * 10^11 possibilités (peut-être beaucoup plus), et donc votre programme n'affichera pas de solution à l'écran, mais en revanche écrira tout dans un fichier, qui dépassera je pense le disque dur du PC (au bout d'un certain moment certe mais bon...)

Conclusion

Bug connu euh aucun, je compte sur vous pour me les signaler...

Mon générateur sera mis à jour je pense, car même s'il donne plus de 6* 10^11 grilles pour chaque niveau, toutes les grilles sont identiques -cf explicationd de la source)

Merci à tous ceux qui laisseront des commentaires négatifs comme positifs ;)
Pour les "Membres Club", vous pouvez télécharger directement un fichier contenu dans le zip sans télécharger le zip en entier !

Télécharger le zip

19 novembre 2005 12:13:27 :
Bon j'ai remplacé les .exe par des .ex_ comme me l'a demandé l'admin, maintenant rien ne vous empêche de le recompiler vous-même si vous n'avez pas confiance et j'ai retiré les accents...
19 novembre 2005 12:21:31 :
j'avais oublié de remmetre la source dsl...
17 février 2008 01:18:43 :
Cela fait un petit moment que j'ai créé un vrai générateur, un qui crée réellement une nouvelle grille, en revanche, il n'y a aucun controle quant à la difficulté, il est possible de gérer ce problème avec une euristique (fausse), qui serait de rajouter des cases en cas d'une difficulté moindre... En fait pour décrire brièvement le code de ce nouveau générateur : il mélange de façon aléatoire une grille toute faite, puis il sélectionne toutes les cases de la grille dans un ordre aléatoire, et essaye de la retirer, s'il peut, il le fait, sinon, il remet la valeur, ce programme fonctionne à l'aide du code de résolution. Je le mets à titre indicatif, le code est peu commenté il me semble, et pas forcement très propre, pour être honnête cela fait longtemps qu'il traine sur mon ordi, mais je me suis dit qu'il pourrait interesser des gens qui cherchent à créer des grilles, cela donne une base de départ. PS : Aucun effort n'est fait sur l'affichage, car leur de sa création, je n'avais plus la librairie conio... Mais au moins tout le monde pourra le compiler
17 février 2008 01:20:46 :
Cela fait un petit moment que j'ai créé un vrai générateur, un qui crée réellement une nouvelle grille, en revanche, il n'y a aucun controle quant à la difficulté, il est possible de gérer ce problème avec une euristique (fausse), qui serait de rajouter des cases en cas d'une difficulté moindre... En fait pour décrire brièvement le code de ce nouveau générateur : il mélange de façon aléatoire une grille toute faite, puis il sélectionne toutes les cases de la grille dans un ordre aléatoire, et essaye de la retirer, s'il peut, il le fait, sinon, il remet la valeur, ce programme fonctionne à l'aide du code de résolution. Je le mets à titre indicatif, le code est peu commenté il me semble, et pas forcement très propre, pour être honnête cela fait longtemps qu'il traine sur mon ordi, mais je me suis dit qu'il pourrait interesser des gens qui cherchent à créer des grilles, cela donne une base de départ. Aucun effort n'est fait sur l'affichage, car leur de sa création, je n'avais plus la librairie conio... Mais au moins tout le monde pourra le compiler
  • signaler à un administrateur
    Commentaire de BruNews le 19/11/2005 12:07:48 administrateur CS

    Salut,

    les EXEs sont supprimés au download du zip, si donc tu veux le mettre doit être renommé en ex_ par exemple.
    Evite les accents dans les noms de fichiers, ça empêche la visualisation aux membres club et c'est dans tous les cas une mauvaise habitude car gênant en cas d'internationalisation de ton prog.
    Pour tout cela essaie de mettre à jour ta source avec un nouveau zip.

    Bonne continuation.

  • signaler à un administrateur
    Commentaire de Elektordi le 19/11/2005 12:17:09

    Je suis justement en train de faire un prog de résolution de sudoku en C# qui sera portable PocketPC... Je l'ai presque fini et je le posterait sur cshrap fr quand j'aufait fini !

    En ce qui concerne ton code j'aimerait bien le tester mais le cpp c'est pas vraiement mon truc donc je vais attendre les exe...

    Mais promis je vais pas copier ! ;-)

  • signaler à un administrateur
    Commentaire de sullyper le 19/11/2005 12:19:39

    bha tu sais, c'est du Cpp, mais c'est juste pour ne pas avoir de problème lors de mes déclarations de variables... ^^
    car sinon j'utilise printf("..."); et non cout... donc tu sais tu peux lire...

    et en plus, toutes les lignes de la résolutions sont commentées

    et puis les exe sont remis ;-)

  • signaler à un administrateur
    Commentaire de BruNews le 19/11/2005 12:26:12 administrateur CS

    Merci.

  • signaler à un administrateur
    Commentaire de Elektordi le 19/11/2005 12:37:19

    Bravo ! Quand je pense que mon programme de résolution met parfois 5 à 10 secondes pr résondre une grille que le tien trouve en moins de 2 secondes...

    Quand j'aurait finit mon prog, je sent que je vais me baser sur ton algo pour la version pocketpc ! (Si je le fait, je te rassure, je te préviendrait...)

  • signaler à un administrateur
    Commentaire de sullyper le 19/11/2005 13:20:14

    tu utilises quoi comme Algo ??? car bon sur mon PC moi il me génère le solution en bien moins d'une seconde, bon ça ça dépend du PC, et il me trouve parfois 150 solutions en moins de 1 sec (lorsque je vire un chiffre niv GOD)... Mais bon, mon algo étant le plus simple possible : je teste tous les nombres dans toutes les cases, sauf si j'ai déjà placé ce nombre dans la colonne ligne ou dans le carré, enfin en gros j'essaye tous les nombres possibles...

    Bon après il est possible que tu fasses la même chose mais qu'au lieu de stoquer les nombres déjà placé dans un tableau comme moi, tu vérifies à chaque fois toutes la colonne, puis toutes la ligne, puis tout le carré pour voir si ce nombre est déjà mis, dans quel cas tu perdrais beaucoup de temps...

    On peut diminuer le temps de résolution de mon programme si au lieu de le laisser chercher toutes les solutions on l'arrête dès la première (car si le sudoku est bien fait il n'y en a qu'une), mais le gain de temps est minime, autre chose que j'aurais dû rajouté mais qui n'est pas très importante, c'est un test qui si pos (le nombre de possibilités dépasse un certain nombre comme 1000000, j'arrête de chercher... ça évite d'écrire trop de chose dans le fichier de sorti...

    Enfin merci, mais stp dis moi quel est l'algo que tu utilises car, même s'il parrait moins bon, il est peut-être interessant et me permettrait d'améliorer mon algo... en faisant un mixte des deux ;-)

    Sinon pour comprendre mon algo c'est simple toutes les lignes sont détaillées en français plus ou moins correcte...

  • signaler à un administrateur
    Commentaire de Elektordi le 19/11/2005 13:45:22

    Au démarrage, je génère des "lignes de résolution" qui sont en fait toutes les lignes (ou colonnes) possibles. Il s'agit de tous les nombres ne contenant pas 2 fois le même chiffre. Cela donne factiorelle 9 possibilitées (env. 38000) et sont générées en env 4 secs.

    Ensuite, pour chaque ligne, je ne conserve les lignes de résolution qui coincident avec les nombres déjà en place. Puis, grâce à une fonction récursive, je teste toutes les possibilitées en me basant sur ces lignes de résolution qui ont été conservées. Ensuite je fait un test des lignes, colonnes et carrés et au moindre chiffre en double, je passe à la possibilité suivante.

    Le problème majeur et que traiter ces lignes de résolution et gourmand en resources (même optimisé, la RAM utilisé par ces collection de lignes peut attendre plus de 100Mo)

    Sinon, dès la première solution trouvée, j'utilise une exception gérée pour sortir de ma fonction récursive. J'arrète donc mon algorithme dès la première solution.

    En tous cas, j'ai étudié un peu ton algo et il est minuscule et complètement différant du mien ! Je sent que je vais l'abandonner et recommancer à zéro avec un algo plus simple, qui je pense va ressembler au tien...

  • signaler à un administrateur
    Commentaire de sullyper le 19/11/2005 20:27:56

    sur, le mien est moin gourmand, d'après ce que tu dis plus rapide, et mon avantage c'est qu'il génere rapidement toutes les possibilités lorsqu'elles sont en un nombre raisonnable, toutefois en compliquant mon algo un peu on peut arriver facilement à plus rapide... mais j'en ai pas trouvé l'utilité ;-)

    Par contre juste ne petite question : Est-ce que tu trouves que mon code est clair ??? enfin je veux dire, il est pas trop dur à comprendre ??? car recemment j'ai modifié ma façon de programmer dans le but de le rendre plus clair... donc voilà...

  • signaler à un administrateur
    Commentaire de zeratul67 le 19/11/2005 21:35:32

    Joli code :)
    Les commentaires sont amplement suffisants pour comprendre le fonctionnement.
    L'algo de résolution est sympa :)
    Bonne continuation

  • signaler à un administrateur
    Commentaire de Kirua le 20/11/2005 10:14:06

    Hmm, en fait si ton sudoku a plusieurs solutions, ça veut dire qu'à la résolution "à la main", tu pourras parfois hésiter, ce qui est une très mauvaise chose. Tu es censé de créer que des sudoku à solution unique, ce qui n'est pas bien difficile dans l'idée de base mais demande quelques raffinements: tu remplis la grille de façon valide, puis tu retires des éléments tant qu'il y a plus qu'une solution. Dans la mesure oà ça ne demande pas grand chose comme temps de résoudre un sudoku (mon algo mettait 0.65s je crois pour toutes les solutions), tu peux te permettre ça :) d'autant plus qu'une grille invalide est très vite traîtée.

  • signaler à un administrateur
    Commentaire de sullyper le 20/11/2005 10:23:28

    non mais t'inquiète, mais générateur de sudoku ne crée aucune grille à plusieurs solutions... il y a aucun risque qu'il en crée une, par contre la méthode que tu viens de citer, c'est celle que je comptais implémenter, retirer les chiffres de telle sorte qu'il y aie toujours qu'une solution...
    Sur mon PC, mon système de résolution met bien moins de .65 sec, donc je sais que ce n'est pas bien compliqué...

    Quand je parlais de grilles à plusiseurs possibilités, c'était lorsque quelqu'un les rentrait à la main, si jamais il fait une erreure de frappe, ou autre, pas plus tard que ce matin je me suis aperçu que j'essayais de résoudre un sudoku qui en fait avait 16 possibilités, mais il venait d'un site web, et j'ai du mal le recopier... c'est tout ;-)

    Enfin merci quand même pour les commentaires :D

  • signaler à un administrateur
    Commentaire de gagah1 le 20/11/2005 11:16:00

    En partant d'un modèle, on arrive à créer un sudoku juste en faisant des permutations. Pas mal comme idée.
    Par contre l'algo de la résolution c'est très bien fait.

  • signaler à un administrateur
    Commentaire de Kirua le 20/11/2005 12:09:32

    Pour faire les choses dans les règles, il faudrait un algo (et c'est faisable) qui résout le sudoku comme un humain devrait le faire. Ça permettrait d'être sûr qu'il est possible sans essai-erreur, ça permettrait d'expliquer la solution au joueur, et en interdisant certaines "réflexions" à l'ordinateur on a aussi un meilleur contrôle sur la difficulté du puzzle. Ce serait sans doute plus lent quand même ... Je pense que ce que les pros font, c'est de générer plein de sudoku "au hasard", comme évoqué ci-dessus, puis ils lancent un algo du type que j'ai décrit dessus pour déterminer le niveau (sûrement lié au nombre de raisonnements nécessaires et au niveau de ceux-ci, ce qui doit être lié au nombre de chiffres donnés dès le départ, mais pas exclusivement).

    Quel algo as-tu implémenté? Perso j'avais fait un depth-first search, tout simplement, rien de brillant. Ça met combien de temps une resolution exhaustive chez toi? Avec quoi comme PC?

  • signaler à un administrateur
    Commentaire de sullyper le 20/11/2005 13:54:52

    bha l'algo, ce qui y a de plus simple, je cherche la premiere case vide, j'essaye tous les nombres possibles de cette case (ceux qui ne sont pas encore placé dans la ligne, la colonne et le carré) puis je relance la même fonction de là... (cf ma source), pour le temps que ça prend, bha sur mon PC 3Ghz, disons qu'il me donne la solution "directe" donc je ne sais pas le temps, même lorsqu'il y a plusieurs solution genre 150 (des fois en retirant un chiffre c'est le cas), il le fait en moins de une seconde, mais comme il ne repart pas de 0, ça veut pas dire grand chose, et puis y a des sources où il rame un peu plus, disons qu'il met je dirais 2 à 3 dizièmes, faudrait que je regarde le temps mais je ne sais pas comment faire ^^

    Sur un autre PC de 1Ghz, il met en gros 2 dizième poue afficher une solution, mais c'est pareil faudrait que je regarde vraiment... Euh en fait, c'est quoi un "depth-first search", car perso les noms d'algo je connais pas trop...

    Pour l'idée des permutations... c'est pratique dans le sens où ça donne l'impression de donner des nouvelles grilles alors que en fait c'est la même et le système de résolution reste toujours le même, bien que dans le niveau 4, il faut y aller plus ou moins au pif à un moment ou 2... Il faudrait que j'implémente un système qui en crée des nouveaux vraiment, en revanche le système de permutation reste pratique, car en partant d'une grille résolue (même une très facil faites à la main), je fais les permuations donc j'obtiens une grille nouvelle et de là je supprime des cases...

    Pour l'algo décrit au-dessus permettant les résolutions, je suis pas sûr qu'il puisse réelment fonctionner, enfin le problème est que en niveau très facil, ça marche, il n'y a pas de test erreur, mais dès que cela se complique, tu en utilises sans être conscient : "si je met un x là, alors je met un y ici, et donc je bloque après donc le x est faux" Cela parait rien, mais c'est du test erreur, ou bien alors l'algo fait lui-même des test erreur et celon au bout de combien de temps il tombe sur une erreur, il juge la difficulté ???

    Je réfléchirai comment bien implémenter un générateur de différent niveau, les idées sont les bienvenues, et si quelqu'un d'interessé veut essayer d'en faire avec moi, de faire un petit projet à 2 pourquoi pas ???

    Des amateurs ???

  • signaler à un administrateur
    Commentaire de Kirua le 20/11/2005 14:05:47

    Je dirais alors qu on peut accepter un test erreur avec une profondeur maximale de disons 1 en mode facile et peut etre 4 en tres difficile, mais 4 c est vrmnt bcp ^^. Ceci dit, c est bien que tu aies dit ca, parce que je n y avait pas pense ^^ c est en effet assez inconscient, ca parait etre un unique mvmt logique.

    La depth first search, c est ce que tu as fait mais en formalise. Tu devrais chercher un peu de doc la dessus, je suis certain que ca t interesserait bcp. Ca permet de resoudre bcp bcp de probleme connus comme des problemes a contraintes, ce qui est bien le cas ici: on cherche une grille de nombres qui respecte qq contraintes: les nombres de depart imposes et les regles du jeu.

  • signaler à un administrateur
    Commentaire de sullyper le 20/11/2005 15:20:00

    oui, mais après il faut réussir à faire l'algo qui réfléchirait comme un humain, j'ai essayé de visualiser dans ma tête, mais c'est chaud à mettre en place, il y a beaucoup de choses à charger dont on a pas conscience de tennir compte en résolvant un sudoku, pour avoir un algo de résolution plus performant que l'humain mais étant basé sur les mêmes règles de la pensée...

    Bon sinon merci du conseil, je suis allé cherché un peu de doc, et en même temps je suis tombé sur pleins de doc sur les graphes, exactement ce qui me manquait ^^ mirci bien ;)

    Bon je m'en vais aller méditer sur le comment faire fonctionner un bon générateur de sudoku, ou bien une nouvelle méthode de résoudre le sudoku, ça vous dérangerait de m'envoyer votre code qui réout les sudoku, que je puisse voir comment il fonctionne ??? mani_hak@hotmail.com

  • signaler à un administrateur
    Commentaire de Kirua le 20/11/2005 19:22:08

    Mon code c'est le même que le tien à mon avis, donc pas trop d'intérêt à ce que je te l'envoie.
    Pour ce qui est de l'algo humain, quand j'y ai pensé ça m'avait l'air faisable ... pas vrmnt approfondi. J'y penserai ^_^.

    Les graphes c'est excellents, pousse à fond dans cette direction si t'es déjà à l'aise avec les piles / files / listes / arbres etc, ça ouvre PLEIN de voies :)

    Au fait: fais un tour sur www.prologin.org si c'est pas fait, et fais les éliminatoires vers le début de l'année civile, genre janvier - février, tu passes les mains dans les poches avec ce genre de code, et c'est la folie totale à la finale ;)

  • signaler à un administrateur
    Commentaire de Elektordi le 20/11/2005 20:24:21

    Pour revenir à mon programme:

    J'ai complètement abandonné mon algorithme et je l'ai repensé... Résultat: il ressemnle beaucoup au tien, mais bon comme j'ai lu ton code avant de taper le mien, j'ai dû m'en inspirer sans faire exprès... ;-)
    En tous cas, j'ai mon ton nom et un lien vers cette page dans le "A propos de" de mon appli !

    Sinon, j'ai quasiment fini le portage sur PPC et, sur émulateur, pour résoudre la grille du "20 minutes" de jeudi (niveau moyen), y met environs 2 à 3 secondes !
    Je pense pouvoir tester chez un copain sur un vrai PPC dans la semaine...
    Par contre, sur PPC, mon appli met bien 10 secondes à se lancer ! (Au démarrage, je ne fait que créer un tableau de 9x9 textboxes et je les affiche !!!)

  • signaler à un administrateur
    Commentaire de sullyper le 20/11/2005 20:52:18

    ouiap je suis allé vite fait sur prologin, en fait je suis surtout sur france-ioi, c'est les même personnes qui s'en occupe mais le but final est défférent...

    Bon j'irais voir sur prologin ce qu'on demande de faire ;-)

  • signaler à un administrateur
    Commentaire de Kirua le 20/11/2005 20:57:40

    pr france ioi tu peux pas avoir fini ta terminale, ça peut poser des problèmes à certains vieux jetons comme moi ;)

  • signaler à un administrateur
    Commentaire de coucou747 le 21/11/2005 18:28:52

    Salut, j'ai fais un truc en php qui fait (pour me moment peu de chose, mais c'est suffisant pour tennir une comparaison) une résolution de sudoku, je me suis dit : on réfléchit de deux façons :
    tout d'abbord, on fait des déductions : on prends un chiffre, et on essai de le placer (on repère une case ou il n'est pas présent, et on regarde ou il pourrait l'être), puis on prends une colone/ligne/zone qu'on essai de compléter...

    Autre méthode : les suppositions... ici, pour un sudoku vide, ça ferait beaucoups de possibilitées... (81 cases avec 9 possibilitées soit 81^9 sauf que certaines possibilitées sont impossibles... soit 81^9=9^18 = 3^36, ça fait beaucoups...), donc, il faudrait mettre un minimum de cases pré-remplies car sinon... Bon, à part ça, on peut faire sans déduction une fonction récursive qui remplirait les cases à chaque fois, et renverrais les solutions qu'elle s'est elle même renvoyée...

    Bon, j'ai fait la première solution, ce qui corespondrais à des sudokus "simples", pour la dèrnière, je n'ai pas pris le temps de comparer les différentes méthodes possibles (appeler la fonction de déduction après chaque placement ou non... à la limite pourquoi pas... ça éviterais des appels bidons... Faudrait faire des benchs...)

  • signaler à un administrateur
    Commentaire de sullyper le 22/11/2005 20:51:22

    moui, pour IOI, j'ai la chance de ne passer mon bac que cette année... ;-), pour prologin, j'irais voir, ça marche comment la finale ??? c'était quoi le sujet de l'année dernière ?

    Pour te répondre Coucou747... La méthode récursive testant toutes les possibilités 9^81 mis à part celles qui on sait n'aboutiraient à rien, ne prend pas beaucoup de temps en C++ mais en PHP je pense que c'est plus long... Cette méthode à l'avantage de résoudre tous les sudokus même les plus durs, même ceux à plusieurs solutions... Celle que tu as choisie à part contre l'avantage de pouvoir tester le niveau de difficulté d'une grille plus facilement... Après c'est un choix, est-ce que tu pourrais m'envoyer ta source en PHP, ou bien me donner l'algo stp, je voudrais voir comment tu fais pour implémenter un meilleur générateur de grilles...

  • signaler à un administrateur
    Commentaire de Kirua le 23/11/2005 13:08:44

    Pour prologin, la finale c'est 100 geeks + les "animateurs" dans un local tout joli mignon de l'Epita, 100 PC dernière génération avec écrans plats, un sujet assez long d'intelligence artificielle (l'année passée: construction d'hotels sur une planète, mais en concurrence avec les autres, avec qq règles assez subtiles par rapport à la construction de bâtiments de différents types et pour la survie des tes unités + la valeur des hotels).

    Ca dur 36h non stop, + qq heures parce qu'ils insistent pour que tlm mange ^^. J'oubliais de préciser: le clou de l'équipement, c'est qu'il n'y a pas d'ondulateur pour protéger les serveurs (avec nos fichiers) des coupures de courants :p enfin, ça n'arrivera plus je pense. L'ambiance est extraordinnaire en tout cas, si t'as l'occasion d'y aller, ben fonce. Y avait vrmnt moyen de faire une IA de tous les niveaux, je crois que c'est une compèt' assez accessible pour des gens qui programment déjà le genre de code que tu as pondu ici. N'hésite pas à regarder les photos et les vidéos des finales (dans les archives), c'est tripant, ça donne trop envie d'y (re)être :)

  • signaler à un administrateur
    Commentaire de sullyper le 23/11/2005 13:22:36

    mouais, je vais voir, c'est vrai que c'est interessant, en même temps j'ai vu le qcm d'inscription, et bien y a pas mal de question dont je ne connais pas la réponse, bon internet est là pour m'aider...

    Il serait possible de communiquer avec toi hors cppfrance pour avoir plus d'info sur comment tout se déroule, et puis t'as l'air calé en algo donc si tu as des sites où je peux apprendre différents algo..., mon msn : mani_hak@hotmail.com

    En ce moment j'étais plus sur france-ioi, car c'est la dernière année où je peux m'inscire et que je n'ai découvert ça qu'il y a 2 mois... mais bon, je suis pas mal monté dans le classement ;) c'est ce qui compte, mais d'un côté prologin est plus ce que j'aime dans l'info, même si je suis mauvais dans ce domaine : l'IA

    Bon merci bien

  • signaler à un administrateur
    Commentaire de coucou747 le 23/11/2005 13:23:58

    Kirua, mais cette année, c'est passé non ? (si oui, alors je devrais reboubler pour pouvoir participer...)
    sullyper, je mettrais la source sur phpcs bientot

  • signaler à un administrateur
    Commentaire de sullyper le 23/11/2005 13:31:52

    ok tu pourras me tenir au courrant ici, car j'y vais jamais sur phpcs, enfin si j'y suis allé 3 ou 4 fois du temps où je bossais en php le bon vieux temps quoi :p

    France ioi : ne pas avoir le bac et une limite d'age de 19 ans je crois
    Prologin : -de 20 ans et ne pas être dans je ne sais plus quelle école...

  • signaler à un administrateur
    Commentaire de Kirua le 23/11/2005 19:50:47

    Tu peux pas être à l'EPITA puisque c'est organisé là ... et qu'ils st trop forts ^^. Et on s'est ts fait traîter de geek par les etudiants d'Epita l'année passée, ça fait bizarre :D.

    Pr le qcm, on s en fiche, c'est un test pr voir si tu connais l'url de google ;) ce qui est important c'est les algos, et au premier tour c'est très simple. t'es même pas obligé de faire un truc qui marche pr ttes les questions au premier tour !

    pas de prob pr l'IA, tu improvises, comme tlm :) par exemple, les machines à état c'est un concept d'IA, mais tt le monde en fait avant de savoir que ça existe: c'est juste des if-else un peu structurés. sans le savoir, tu en fais tt le temps. mtnt, le savoir permet de structurer la pensée. prends un bloc de feuille, c'est ton meilleur ami qd tu n'as que 36h.

    je communique pas via msn, ça m'énerve ;) je peux pas écrire bcp mtnt parce que je mange des olives et du coup je peux pas taper ac ts les doigts, mais je t'envoie juste un mail vide pr que tu aies mon adresse.

  • signaler à un administrateur
    Commentaire de coucou747 le 23/11/2005 19:58:01

    lol Kirua, t'as pas changé ^^

    Bon, ces concours ont l'air interessant, mais on y gagne quoi (lol, oui, je suis matèrialiste...)

    Je ne peux pas te passer mon algo car je l'avais fait pour le plaisir, mais je ne voulais pas le diffuser, et en le regardant de plus près bah... il marche mal... il fait des erreurs... c'est génant... l'autre fois, je croyais qu'il marchait, mais finalement, je sais qu'on peut y arriver, mais moi, j'ai du mal...

  • signaler à un administrateur
    Commentaire de sullyper le 23/11/2005 20:14:57

    à gagner... euh y avait un PC en premier lot ;-) portable bien sur...

    Sinon pour les IA, clair si j'ai l'occasion je fais comme tout le monde : j'improvise, pour le questionnaire on verra... :p quand j'aurais du temps :p :p

    Bon sinon Kirua, j'attends ton mess :p

  • signaler à un administrateur
    Commentaire de Kirua le 23/11/2005 20:17:36

    coucou, je comprends pas vraiment ce que tu veux de plus que 3 jours de geekitude totale :) en l'occurrence, on a tous eu un t-shirt événement et un clé usb 128Mo, et personnellement j'ai eu 2 gros bouquins de prog de la collection O'reilly, dont les prix magasins sont de l'ordre de 50 euros, ça fait tjs plaisir :)

  • signaler à un administrateur
    Commentaire de sullyper le 23/11/2005 20:24:06

    clr, moi si je fais, c'est pas pour les lots, franchement, je kiffe trop la prog pour m'arrêter là-desssus, par contre c'est vrai que si en plus on gagne des choses c'est mieux...

    Mais bon la prog doit avant tout être un plaisir...

    A kirua, tu sais pourquoi j'arrive pas a envoyer mes sources sur prologin :
    "Warning: fsockopen(): unable to connect to kirika.prologin.epita.fr:80 in /www/business/prologin-org/site/tools.php on line 408"

    Il te fais ça aussi en ce moment ou c'est mon PC qui déconne (il me fait ça depuis le début de la journée...

  • signaler à un administrateur
    Commentaire de coucou747 le 23/11/2005 21:09:36

    lol Kirua, franchemnt, mes vacances, c'est déja la geekitude (ou geekatitude ^^)...
    là, je programmes depuis que j'ai arrété les cours (un plugin pour X-Chat si tu veux les détails...) Pour moi, la compétition, c'est une ocasion de rencontrer des personnes de haut niveau, mais rien de plus... j'ai fait de la compétition, et j'y allais pour être avec mes potes, mais pour pratiquer la prog, t'as rien de mieux qu'un coupe p1/p4... ça donne un bel aperçu des possibilitées des différents langages libres... (optimisations sur le p1, défouloir sur le p4...)
    je suis allé sur le site de prologin...
    T'as fait une belle performance Kirua, félicitation ! Mais je suis loin d'avoir ton niveau en C++... Ils disent que c'est tt langage, mais c'est forcément sous réserve des compilateurs dispo... Mais je vois de mentionné pascal et java, et je ne connais ni l'un, ni l'autre... je ne vois mentionné aucune autre langage...

    Sur leur site, je ne vois ni frais d'inscription, ni formulaire d'inscription... Pourtant, dans les news, je vois que c'est en ligne...

  • signaler à un administrateur
    Commentaire de Kirua le 23/11/2005 22:38:57

    pour ton erreur de fsockopen, ça dot être de leur côté l'erreur, tu sais, ils font les serveurs de jeu pendant la finale, alors ça m'étonnerait pas :D (j'en profite pr qd même dire que c'est un boulot fabuleux, j'aurais trop mauvais d'être exclu de la compétition pour irrespect :p).

    les langages acceptés sont le C, le C++, le Pascal, le Java et le Caml. Ceci dit, les langages gagnants sont qd même le C et le C++ évidemment :p la phase éliminatoire peut se faire en tout, même en français: c'est corrigé par un humain.

    faut suivre le lien de la page d'accueil pr le questionnaire de cette année, mais rien ne presse.

  • signaler à un administrateur
    Commentaire de dautrey le 26/11/2005 19:59:18

    J'ai testé votre algo de résolution, et je le trouve génial. J'ai développé un petit logiciel en pseudo freeware (un appel sur allopass le débride) il s'agit de SUDOKU EXPERT. Mais je développe avec WINDEV qui pour ce genre d'algo est particulièrement lent. Il est pratiquement impossible de traiter des grilles à solution multiple. Puis-je me permettre de m'inspirer de votre algo pour améliorer la performance ? Mon programme est téléchargeable à l'adresse suivante:
    http://oragogo.free.fr/xsudoku.msi
    J'attends votre avis et votre accord éventuel.
    Très cordialement et encore bravo !
    François DAUTREY

  • signaler à un administrateur
    Commentaire de sullyper le 26/11/2005 20:09:38

    oui oui, aucun problème, vous pouvez vous inspirer de mon algo, au contraire, ça me fera plaisir d'avoir pu aider qqn ;)

  • signaler à un administrateur
    Commentaire de dautrey le 27/11/2005 19:31:01

    Merci, je vais y travailler dans la semaine,je n'ai jamais utilisé le mariage Windev et C++ c'est l'ocasion d'essayer. Je vous tiendrai au courant des résultats et éventuellement je me permettrai de vous demander des tuyaux. Vos sources sont parfaitement renseignées.

  • signaler à un administrateur
    Commentaire de Byro le 06/12/2005 16:15:34

    Y at'il un intéret particulir à utiliser une fonction recursive plutot qu'itérative ? Une solution "bêtement itérative" n'est-elle pas aussi simple et aussi rapide ?

  • signaler à un administrateur
    Commentaire de Kirua le 06/12/2005 16:27:38

    récursif: élégant
    itératif: rapide

  • signaler à un administrateur
    Commentaire de sullyper le 06/12/2005 17:40:17

    Récursif = simple
    Itératif = Compliqué

    Enfin c'est ma façon de voir, je trouve un code recursif plus simple à comprendre donc plus simple à produire...

  • signaler à un administrateur
    Commentaire de coucou747 le 28/12/2005 18:15:53

    Bon, depuis t'as eu deux sources sur Cppfrance sur les sudoku...
    voila le mien
    http://phpcs.com/code.aspx?ID=35308
    mais le mien ne fait aucune supposition...

  • signaler à un administrateur
    Commentaire de Kirua le 28/12/2005 18:26:06

    Simple et élégant, c'est souvent couplé :)

    Rapide et compliqué c'est moins direct comme lien, mais pour programmer itérativement, il faut souvent, c'est vrai, réfléchir plus, ...dans les cas où la récursions est immédiate: c'est une tautologie, la déclaration se mord la queue :)

    D'une manière générale, j'ai tendance à penser que le temps de calcul de mon PC est plus important que mon temps, parce que c'est ludique d'optimiser, mais dans le monde professionnel et en compétition ... plus vite tu programmes, mieux c'est! (le plus souvent). Un informaticien coûte plus cher qu'un P4 ^^.

  • signaler à un administrateur
    Commentaire de sullyper le 28/12/2005 19:18:32

    Oui mais bien que je pourrais optimiser ma source... Je ne suis pas sûr de gagner en simplicité qui je pense est assez importante, surtout sur un site comme celui-là, je en poste pas une source pour qu'elle serve aux gens mais plus pour qu'ils puissent la comprendre facilement et s'en inspirer, à eux après d'optimiser...

    Et puis la gain de temps se verrait-il ??? CEla dépend du PC je pense car sur celui que je pocède, je ne vois pas la différence entre ma source et une réponse instantanée...

    Enfin forcement chacun pense ce qu'il veut :P, chacun se retrouve sur le net... y en a pour tous les goûts... ceux qui aiment le récursif venez les autres partez :P

    Par contre Kirua je trouve ta dernière remarque très bonne, sauf que j'ai plein d'autres choses à programmer (l'entrainement IOI par exemple) et donc cette optimisation devient facultative...

  • signaler à un administrateur
    Commentaire de Kirua le 28/12/2005 19:26:17

    Je pensais à prologin en disant ça en fait. À l'épreuve machine de la demi finale c'est le plus marquant notament: 4h, plein d'exos, des contraintes de temps et de mémoire. L'important, c'est de taper juste bien pr satisfaire les contraintes... bcp de gens, je pense, essayent de faire l'algo le plus optimisé possible, ce n'est souvent pas la peine.

  • signaler à un administrateur
    Commentaire de sullyper le 28/12/2005 19:32:39

    J'espère y avoir accès à cette demi-finale et puis pouvoir la passer...
    En même temps mon entrainement aux IOI m'entraine aussi pour Prologin car c'est exactement le même principe pour la demi-finale...

    En revanche pour la finale je pense qu'il faut aboir un code assez optimisé... car y a une contrainte de temps quand même :P (je parle du sujet de l'année dernière)...
    Donc le mieux c'est de prendre l'habitude de programmer quelque chose de propre et d'assez optimisé pour ce qu'on souhaite... pas besoin de plus que le minimum nescessaire :P

    Kirua, tu la feras où ta demi-finale (car tu y seras si tu as rempli le forumulaire :p) Peut-être se retrouvera-t-on au même endroit, sinon pourquoi pas en final... j'aime savoir à qui je parle :P

    D'ailleur si je vasi en demi-finale je t'enverrais certainement un mail pour avoir des rensignements... si cela ne te dérange pas...

    Cordialement Sullyper

  • signaler à un administrateur
    Commentaire de Kirua le 28/12/2005 19:39:23

    Je fais les demis à Lille (selon toute probabilité ^^).

    La demi finale c'est, à mon sens, essentiellement une épreuve technique: si tu connais les algos classiques et les structures de données bateaux, ça doit passer: mais faut être rapide!

    C'est pas pour faire de la pub (à peine ^^), mais sur le forum de www.coder-studio.com (et notament ici: http://www.coder-studio.com/forums/index.php?showtopic=253&st=40&hl=prologin mais aussi à plein d'autres endroits), ça parle de prologin, et d'une manière générale les questions types ressortent, et puis on en discute. Si ça intéresse...

    Tu peux attraper MoDDiB aussi, qui rode sur cppfrance parfois :p il va aussi à Lille. Idem pour Xurei, aussi sur cppfrance et phpcs de temps en temps.

  • signaler à un administrateur
    Commentaire de coucou747 le 28/12/2005 19:54:05

    Kirua, on n'a jusqu'a quand pour s'inscrire ?

  • signaler à un administrateur
    Commentaire de sullyper le 28/12/2005 19:56:27

    c'est jusqu'au 31 janvier pour le formulaire qui permet d'accéder au demi-final... donc y a encore un peu de temps :P

  • signaler à un administrateur
    Commentaire de dautrey le 23/01/2006 16:33:28

    J'utilise sudoku.exe comment modifier le source pour que si la variable "pos" dépasse par exemple 50 on quitte la procedure recursive. Je ne sais pas trop comment on peut faire. Peux-tu m'indiquer où il faut quitter à la hussarde avant de faire exploser son disque ?
    Merci pour ton conseil.

  • signaler à un administrateur
    Commentaire de dautrey le 23/01/2006 16:34:06

    J'utilise sudoku.exe comment modifier le source pour que si la variable "pos" dépasse par exemple 50 on quitte la procedure recursive. Je ne sais pas trop comment on peut faire. Peux-tu m'indiquer où il faut quitter à la hussarde avant de faire exploser son disque ?
    Merci pour ton conseil.

  • signaler à un administrateur
    Commentaire de sullyper le 23/01/2006 18:47:08

    dans la fonction "void MakeGrille()"
    en première ligne marque : if (pos > 50) return;

    Normalement ça devrait éviter de faire trop de calcul
    sinon si tu vois que le programme est trop long et que tu veux arrêter le programme, comme c'est du sous dos tu peux faire "ctrl c", à condition qu'il ne soit pas désactivé cehz toi :P

  • signaler à un administrateur
    Commentaire de drapolas le 11/02/2006 03:42:41

    salut bon code mais je n'arrive pas a le compiler
    avec quoi l'a tu compiler
    merci

  • signaler à un administrateur
    Commentaire de sullyper le 19/02/2006 10:46:11

    Dev C++

    mais le problème (je viens de m'en rendre compte après un formatage), c'est que j'utilise un fichier conio.c que j'ai piqué dans l'ancienne version de Dev, et sans ce fichier il ne peut pas compiler, toutefois, ce fichier n'est pas indispensable pour le fonctionnement, il servait juste à avoir une interface plus jolie, si tu ne te sers du programme que pour la résolution, tu peux très bien retirer tout ce qui est affichage et récupérer la solution dans le fichier *.txt...

    J'espère avoir résolu ton problème, bon tu peux aussi bien entendu récupérer le fichier conio.c, mais je ne l'ai plus donc je ne peux pas le mettre dans le zip...

    Cordialement Sullyper

  • signaler à un administrateur
    Commentaire de xixi666 le 27/02/2006 23:55:10

    Faut arreter d'écrire des codes de résolution pas instantanné les gens :P

    Quelques notions de complexité des algorithmes suffisent a privilégier les opérations logiques d'élimination combinatoire sur toute la grille plutôt que les recursions dans tous les sens. Un bête algo qui marche très bien consiste à maintenir pour chaque case l'ensemble des chiffres possibles pour cette case, en fonction de tous les autres chiffres déjà connus, et de déduire les case pour lesquelles il ne reste plus qu'une seule possibilité. Une petite amélioration peut ensuite consister à rechercher les cases comportant une possibilité unique pour un ensemble donné. Les méthodes purement logiques ont l'avantage de remplire la grille extremement rapidement, sans aucun essai et erreur, mais ne suffisent pas. Donc oui une méthode récursive est aussi necessaire, mais pour aller plus vite que tout le monde il faut obligatoirement la combiner avec une méthode logique, telle que celles citées plus haut.
    Temps de calcul: moins de 1 ms sur un athlon mobile 1700+. Occupation mémoire: négligeable (de l'ordre de la dizaine de Ko, sans aucune optimisation (stockage de 9x9x9 boolean dans les int et il faut compter une ou deux recursion pour les grilles difficiles, j'avais un peu la flemme de faire plus cours :p))

  • signaler à un administrateur
    Commentaire de coucou747 le 28/02/2006 12:44:54

    xixi666, tu as raison, ta méthode est l'une des plus optimisée, tu as une autre méthode de déduction qui trouve moins de chiffres, mais qui prend trois fois moins de mémoire, et qui est peut-être plus rapide... tu pose les valeurs interdites dans des colones, lignes et cases, dans des tableaux... ça te fait un tableau de 9*9 pour les valeurs, et un tableau de 9*3*9 pour les valeurs interdites... Problème : avec cette méthode, on ne peut pas faire autant de déduction qu'avec la tienne... Utilisant trois fois moins de mémoire, mais devant faire plus de suppositions (donc, plus d'étapes récursives), je ne sais pas quelle méthode est la plus rapide... Mon code est en php, donc, on ne pourra pas faire de benchs, mais bon, en php, quand un algorithme comme ça s'exécute en moins de trois secondes (dèrnière optimisation en date, tests réalisés sur un céléron 2.4 ghtz, avec un sudoku démoniaque...), je ne suis pas mécontent...

  • signaler à un administrateur
    Commentaire de w00tw00t le 03/05/2006 13:58:07

    Moi, je trouve ce code moyen, pas mal pour un débutant,
    perso, j'ai créé un code qui met 1 milliseconde su un 1 Ghz Celeron (machine test) pour créer un sudoku de n'importe quelle difficultée ……… il met 5 millisecondes au max pour en résoudre ………
    C'est entièrement en C++, +- 2100 lignes
    aucun API n'est utilisé excepté stdio, strings.h ……… la bibliothèque standard quoi
    il peur donc même tourner sous Windaube ………

  • signaler à un administrateur
    Commentaire de w00tw00t le 03/05/2006 13:58:57

    J'avais oublié, je suis dvelopeur de métier alors faut pas vouloir la source …

  • signaler à un administrateur
    Commentaire de sullyper le 03/05/2006 15:41:15

    Oui, moi je suis encore au lycée, j'ia fait ce code en 2h, alors tu sais, j'i aps essayé de l'optimiser... La création de sudoku, c'était juste un petit test.

    Et puis, le but de mon programme, ce n'était pas la vitesse, sinon je m'y serais pas pris comme ça, c'était la simplicité à coder... Je me voyais mal poser un code de 2100 lignes, ça aurait été vachement pratique pour ceux qui auraient aimé relire le code.

    Tu codes, c'est ton métier, la source n'est destinée à personne autre que toi, tu dois faire un truc performant, donc tu le fais.
    Je m'amuse, je poste la source ici pour aider un grand nombre de personne n'arrivant pas (car c'est un sujet assez à al mode il faut dire), donc je fais quelque chose de simple.

    Par contre, je ne dispose pas d'une machine de test (1 Ghz Celeron), si tu pouvais tester mon programme pour me dire en combien de temps il résout les sudoku, je serais content :D. Ok ça ne sera pas forcement terrible, mais le temps de résolution est largement négligeable en comparaison avec celui mis pour entrer le sudoku...

    Cordialement Sullyper

  • signaler à un administrateur