CREATION DE SUDOKU DIFFERENTS NIVEAUX ET RESOLUTION

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.

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

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

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

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

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

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?

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.

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

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

Commentaire de coucou747 le 21/11/2005 18:28:52 administrateur CS

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

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

Commentaire de coucou747 le 23/11/2005 13:23:58 administrateur CS

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

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.

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

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

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.

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

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 ?

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

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

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.

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.

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

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.

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

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

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

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

Commentaire de sullyper le 03/05/2006 17:26:38

Et oui, déjà en train de programmer :P 36h ça ne m'a pas suffit... Non en fait, je lisais mes mails et donc j'ai vu ce message...
Mais faut croire que toi aussi tu es déjà présent... En tout cas ça m'a fait plaisir de rencontrer du monde... Quand je disais à Funto que c'était grâce à vous que j'étais à Prologin... Il suffit de relire les commentaires et tu verras que c'est toi qui 'a incité à le faire ^^

Sinon pour w00tw00t, si ça l'amuse de se sentir supérieur, tant mieux pour lui, il a raison au moins sur un point : il l'est... Maintenant, est-ce qu'il a du mérite à l'être, c'est une autre question, est-ce qu'il a du mérite à s'en venter, ça par contre je connais la réponse... ^^

Commentaire de sullyper le 03/05/2006 20:39:58

Moi j'ai même pas pu avoir mes 12h de sommeil... J'ai dormi 7h à Marseille puis j'ai pris le train pour aller directement en cours :P

Y en a qui ont de la chance...

Commentaire de Elektordi le 03/05/2006 23:40:53

Faudra bien que je finisse par y aller une année...

Commentaire de sullyper le 04/05/2006 13:31:13

Kirua ==> Oui je pense qu'on s'est vu :D, tu étais avec Funto non ? Moi je suis le petit qui a fini 8ème :D

Je passais régulièrement voir Funto... Donc moi je vois qui tu es :D, sinon c'est pas grave tu nous battera tous l'année prochaine... Si tu peux encore participer !

Ils sont amusant leur sujet c'est calir, mais leur serveur est un peu pourri... Enfin il faut faire avec, ça ne serait plus Proologin sinon !!!

Commentaire de plasmaphobe le 11/05/2007 18:00:24

lut,  
jolie comme prog,,,,mais évite l'utilisation de "goto" ,
peut etre dans votre code sa marche mais dans autres cas c'est le masacre.....
et bon cour

Commentaire de coucou747 le 11/05/2007 21:45:40 administrateur CS

c'est ce post qui m'a envoye a prologin, et deux ans apres j'y repasses :) avec celui qui m'y a envoye XD

ca merite de rester dans mes signets, (relecture pleine d'emotion :) )

il marche bien ton pc ?

Commentaire de sullyper le 11/05/2007 21:59:02

Lol, comme on se retrouve :P

Pour répondre, au très cher qui est passé par là :
J'étais étonné de voir que j'avais mis un goto... En fait ce doit être du gotoxy que tu parles :D

Je sais que ça ne marche pas partout, mais c'était pour avoir un joli affichage, il reste la possibilité de supprimer tout ce qui est de l'affichage et de ne laisser que le fichier de sortie pour recevoir le résultat :D

Enfin, c'est vieux tout ça, maintenant, je ne code plus comme ça (d'ailleurs il a fallu que je reffasse le même code en Caml pour la prépa :-(, en moins optimisé... Sont c*** les profs des fois !!!)

Sinon pas de chance pour le PC, si tu veux je peux t'en débarrasser :D !!!