Bonjour à tous !
J'aimerais savoir comment on peux créer une grille de sudoku.
J'ai quelques idées pour créer la grille mais je n'ai absolument aucune idée pour enlever des cases au hasard... Si possible avec différents niveaux de difficulté...
Je ne veux pas un code source tout fait, mais une explication du raisonnement.
Je pense pas que les jeux de sudoku soit généré au hasard.
Oui, en effet.
Il faut que la grille admette une unique solution, sinon la grille est fausse.
Si on "enlève" les cases de façon totalement aléatoire sans algorithme à coté, on risque un moment donné d'avoir une grille qui admet plus d'une solution.
Il faut faire attention à ce point.
Tu as raison Arthurus, mais je crois qu'il existe des grilles niveaux experts ou il y a 2 soultions (maintenant, peut-être qu'il y avait une erreur dans la grille que j'ai vu...)
Il faut que la grille admette une unique solution, sinon la grille est fausse.
Ah bon . Moi lors de ma seconde et ma première mes cours de français et histoire géographie servaient à faire des sudokus et lors de ces 2 années j'en aie rencontré quelques uns qui admettaient au moins 2 solutions (on trouvait des solutions différentes moi et un ami) et les grilles n'étaient pas fausse.
je sais, mais si on supprime de "mauvaises" cases, on rend la grille impossible et le nombre de grilles enlevées ne permet pas du tout de gérer les niveaux de hasard...
Moi je cherche un algorithme qui serait capable (en théorie hein, j'ai pas une éternité à passer sur mon ordi) de créer toutes les grilles de Sudoku, aléatoirement.
Re-Salut, pour crée un algorithme il faut du temps ou sinon crée une grille de sudoku complète et qui fonctionne Et après il te suffit de supprimer des cases tout en laissant une solution à la fin
PS : je ne sais même pas si l'algorithme est le bon terme. Essaye de crée une I.A vérifiant si il y a une possibilité
Moi je cherche un algorithme qui serait capable (en théorie hein, j'ai pas une éternité à passer sur mon ordi) de créer toutes les grilles de Sudoku, aléatoirement.
Non, avec la possibilité d'avoir 2 ou 3 possibilités dans les niveaux "extrèmes"
Je ne connais pas d'autres méthodes que de partir d'une grille pleine, de retirer des cases, d'utiliser un solveur et de voir combien il te génère de grilles. Il faut donc que ton solveur soit très rapide sinon la génération sera lente.
Et comment faire pour créer des niveaux de difficultés ?
Jamais su ce qu'était la difficulté d'un sudoku, si tu as une explication rationnelle, je suis preneur, faut dire que j'ai jamais vu en le sudoku qu'un problème de brute force ...
Personnellement je considère qu'un sudoku est difficile quand il devient impossible à résoudre sans faire un choix arbitraire, continuer, et voir si ce choix a abouti ou pas.
Fvirtman a fait un solveur de sudokus (en C++) que tu peux trouver sur sa page perso...
Pour les niveaux de difficulté, je pense que c'est par rapport au nombre de chiffres qu'on peut logiquement trouver à un moment donné : Plus c'est facile, plus le nombre de chiffres qu'on pourra trouver avec les données de départ (sans ajouter les chiffres qu'on a trouvé) est grand. Lorsque cela devient difficile, les possibilités sont restreintes et il faut les chercher minutieusement, et lorsqu'on est en "difficile" ou "expert", il faut carrément faire des tentatives sans avoir 100% de chances que le nombre se trouve là, quitte à le mettre au mauvais endroit et à devoir tout recommencer...
Même si vôtre position est justifiée, il existe une méthode, au moins, pour générer une grille aléatoirement(pseudo-aléatoirement).
Ceci en utilisant des rotations homogènes de toute la grille, je m'explique, le principe est de garder la grille uniforme (cohérente avec les règles du sudoku) entre deux mélanges. Ceci nétant possible que si tu mélange des lignes droites par bloc de trois lignes.
Voici la grille de départ :
123|456|789 le mélange se 123|...|... puis ces lignes ...|456|... de même pour
789|123|456 fait en 789|...|... entre elles => ...|123|... le dernier
456|789|123 intervertissant 456|...|... ...|789|... bloc.
----------- ces lignes ----------- -----------
912|345|678 verticales 912|...|... ...|345|...
678|912|345 entre elles => 678|...|... ...|912|...
345|678|912 345|...|... ...|678|...
----------- ----------- -----------
891|234|567 891|...|... ...|234|...
567|891|234 567|...|... ...|891|...
234|567|891 234|...|... ...|567|...
On fera de même pour les lignes horizontales, mais par bloc de trois lignes,exactement comme ce qu'on a fait avec les lignes verticales.
Et répéter ceci un nombre aléatoire de fois (attention pas très grand, entre 2 et 5 fois c'est largement suffisant), ce qui au final placera tes nombre de façon aléatoire, tout en gardant notre grille uniforme.
Maintenant il ne reste plus qu'à cacher des nombres et en laisser d'autres visibles en fonction du niveau de difficulté. Là il faut laisser travailler ton imagination (je ne dis pas que c'est la partie la plus simple) mais ce n'est pas le plus compliqué.
Pour la résolution d'une grille de sudoku je ne mets jamais de chiffres au hasard, c'est une erreur. Il y a beaucoup de techniques pour trouver les solutions :
La technique et la suivante on crée une grille juste (alors la c'est le problème) on retire des casses au hasard. Et on envoye la grille obtenu a une résolveur on récupère le temps mit par le résolveur, pour éventuellemnt messure la difficulté (tout et relatif ). Si le résolveur ne peut pas résoudre la grille (sans triché) cette grille est eliminer.
Après on stock le tout dans un fichier et c'est partie.
Je suis d'accord la génération de grille et pas très rapide et pas forcément a implémenter dans l'appli. Mais on peut faire un fichier qui soi contiennent un nombre de grille immense ou qui ce renouvelle de temps en temps un programme d'update ou autre.
Personnellement je considère qu'un sudoku est difficile quand il devient impossible à résoudre sans faire un choix arbitraire, continuer, et voir si ce choix a abouti ou pas.
oui mais "impossible à résoudre" à partir de quelles règles d'inférence ? si je te comprends, tu vas considérer que le sudoku est "difficile" dès lors que pour chaque case libre C, si on regarde les seulement les contraintes d'appartenance de C à sa ligne, sa colonne et son mini-carré, on n'a toujours plus d'une possibilité de remplir C ? A mon avis ça rend beaucoup de sudokus difficiles.
Le problème est qu'il doit certainement exister des "théorèmes" qui te disent lorsque tu as plusieurs alternatives de placement dans une case C, qu'en fait, il est certain que c'est telle valeur que tu dois placer en C. A vrai dire j'en sais rien mais je suppose que certain chercheurs ou amateurs ont trouvé ce genre de théorème et qui enrichissent les règles d'inférence dues au seul examen des contraintes sur la ligne, la colonne et le mini-carré contenant C, je sais pas si j'ai réussi à me faire comprendre.
faut dire que j'ai jamais vu en le sudoku qu'un problème de brute force ...
Il me semble avoir lu que le sudoku peut être ramené à un problème de coloration de graphe (9 couleurs, une arête entre chaque sommet de chaque ligne, colonne, mini-carré).
En tout cas j'ai fait un solveur ''brute force'', et sur une grille difficile (trouvée sur Internet), il peut tourner un jour sans trouver de solution. Un algorithme ''brute force'' ne m'apparaît pas comme une solution pratique au sudoku.
Salut!
1ere partie construire une grille au hasard a deviner:
A la base on fabrique deux objets que L'on nomme canoniques:
le premier est une chaine 123456789 et une matrice 9*9 selon
123456789
234567891
345678912
456789123
567891234
678912345
789123456
891234567
912345678
ces deux objets a partir de lesquels on va travailler
en ce qui concerne la chaine on peut construire un algorithme simple selon la methode:
J'ENVOI LA DEUXIEME PARTIE PLUS TARD CAR J'AI UN PROBLEME POUR
envoyer des messages longs
Le problème est qu'il doit certainement exister des "théorèmes" qui te disent lorsque tu as plusieurs alternatives de placement dans une case C, qu'en fait, il est certain que c'est telle valeur que tu dois placer en C.
Un tel théorème ne peut pas exister.
Le problème de résolution du sudoku est NP-complet.
NP veut dire non déterministe polynomial, et non déterministe veut dire que le fait de faire un choix puis se rétracter n'est pas choquant.
Si un théorème qui garantit que chaque valeur de case peut être déterminée en se basant uniquement sur les valeurs existantes des autres cases existe, alors sudoku ne serait plus NP-complet.
Je suis rassuré, j'ai failli me sentir con (Quand vous m'aviez dit qu'on peut résoudre tous les sudoku sans faire des choix, je me suis senti vraiment con )
@kimimsc : Mon post te vise aussi
EDIT : quoi que... je commence à douter, et j'ai pas toute ma tête en ce moment
Si quelqu'un peut vérifier ce que je dis, ce serait cool
Et on envoye la grille obtenu a une résolveur on récupère le temps mit par le résolveur, pour éventuellemnt messure la difficulté (tout et relatif ). Si le résolveur ne peut pas résoudre la grille (sans triché) cette grille est eliminer.
Ton programme risque de buguer 7 fois sur 10. Si jamais il tourne en boucle sans trouver de solution ? Que pense tu faire pour éviter que cela arrive ? Mettre un watchdog peut être ?
Réfléchie un peu aux problèmes que je viens de te citer, tu trouveras que ce n'est pas aussi simple que ça en a l'air.
Sinon pour rejoindre la discussion, effectivement c'est fun de trouver une méthode qui satisfasse aux attentes de tout le monde ici. Et surtout à leurs définitions des dits "niveaux de difficultés".
Je viens de penser à une méthode (un peu mathématique) que je vais voir plus en détails avant de la publier : Qui consiste, par principe d'arbre, à éliminer les cases dont il existe au moins une condition pouvant la retrouver. Je compte ensuite l'appliquer à toute la grille case par case (pour au final se retrouver avec un strict minimum pour que la grille admette une seule et unique solution), ceci étant pour le niveau le plus difficile.
Pour les autres niveaux, l'algorithme s'arrêtera avant.
Et je vais voire si cela fonctionne. (Théoriquement oui, mais je préfère en être sûr).
La difficulté de trouver un algorithme robuste, est dû au fait que les cases sont liées, non seulement spatialement (on tranche sur la valeur d'une case en fonction de la ligne, colonne ou cadre), mais aussi chronologiquement (quelle case trouvée avant permettrait de trouver la case en question). Ce qui nous met devant un problème quadridimensionnel à maîtriser.
Edit : Ce post est une petite dédicace à Arthurus , qui n'est autre que la solution réversible à ce que tu as annoncé comme étant un problème, à savoir les "multi-solutions" vu que ça part d'une solution seule et unique. Théoriquement en tout cas
Je ne parle pas d'un théorème général, je te parle d'un théorème avec certaines hypothèses restrictives valable uniquement pour certaines configurations.
Je ne parle pas d'un théorème général, je te parle d'un théorème avec certaines hypothèses restrictives valable uniquement pour certaines configurations.
Oui je vois ce que tu veux dire.
Je ne sais pas, je n'ai pas d'intuition sur le sujet.
Peut être bien que ça existe au final.
× Après avoir cliqué sur "Répondre" vous serez invité à vous connecter pour que votre message soit publié.
× Attention, ce sujet est très ancien. Le déterrer n'est pas forcément approprié. Nous te conseillons de créer un nouveau sujet pour poser ta question.
Objectif Zéro Bug - le test logiciel professionnel | L'électronique de zéro | Tableaux & pointeurs | Pointeurs sur fonctions | Lecture/écriture binaire
Objectif Zéro Bug - le test logiciel professionnel | L'électronique de zéro | Tableaux & pointeurs | Pointeurs sur fonctions | Lecture/écriture binaire