Essai erreur, ensuite tu peux essayer de tirer au hasard les cases exposées. Ca marche mais donne en général des grilles assez faciles.
Essai erreur, ensuite tu peux essayer de tirer au hasard les cases exposées. Ca marche mais donne en général des grilles assez faciles.
"La haine seule fait des choix" - Koan Zen
"Il ne faut pas être meilleur que les autres, il faut être meilleur que soi." Albert Jacquard
"Ceux qui savent où ils ont posé leur parapluie ne sont pas alcooliques." - pgibonne.
Faites du Prolog, ça vous changera les idées !
Ma page Prolog
Mes codes sources commentés
Mon avatar : La Madeleine à la veilleuse de Georges de La Tour
Je dirais que tu doit avoir un algo de résolution, generer des cases aléatoirement et appliquer ton algo. Si il bloque, il genere des cases, si il reussi, il garde ta grille et tu peux etre sur qu'elle n'a qu'une solution. Par contre, la difficulté de la grille generée dependra de la puissance de l'algo de resolution qui doit, bien sur, fonctionner par logique et non par essai erreur... Je ne sait pas si je suis suffisement explicite.
Je pense que si tu veux pouvoir generer des grilles tres difficile, tu doit deja realiser un algo de resolution capable de comparer les ensembles de possibilités de plusieurs groupes de cases (blocs+lignes,blocs+colones) et en tirer des conclusions. Pour ma part, j'ai un peut décroché ces derniers temps mais je n'ai pas encore trouvée une logique satisfesante pour cette étape.
Ca rejoint un peut ce dont je parlait dans mon precedant post :
Multiples solutions pour une grille :
Je ne shaite pas que mon algorithme fasse de choix. Il ne doit donc pas etre capable de résoudre les grilles à plusieurs solutions. Mais je peux moi meme modifier la grille manuellement si elle n'est pas résolue.
Il est facile de verifier qu'une grille n'a qu'une seule solution. Si la grille n'est pas resolue, je choisi une case pour laquelle il n'y à que peut de possibilité, fait un choix et relance mon algorithme. Si il se rend compte que la grille est invalide (certaines case n'ont plus de possibilités) c'est que ce choix n'etait pas correcte. En continuant ainssi, on peut vite verifier si une grille à une solution unique.
C'est dans ce sens là que je parlais d'algo essais erreurs, tant que le Sudoku a plus d'une solution on rajoute une case, une fois qu'il n'a qu'une solution, on regarde si on peut évenutellement enlever des cases.Envoyé par monstroplante
"La haine seule fait des choix" - Koan Zen
"Il ne faut pas être meilleur que les autres, il faut être meilleur que soi." Albert Jacquard
"Ceux qui savent où ils ont posé leur parapluie ne sont pas alcooliques." - pgibonne.
Faites du Prolog, ça vous changera les idées !
Ma page Prolog
Mes codes sources commentés
Mon avatar : La Madeleine à la veilleuse de Georges de La Tour
Oui ca permetrait d'augmenter encore la difficulté !une fois qu'il n'a qu'une solution, on regarde si on peut évenutellement enlever des cases.
Mais je pense que ce qui est interessant a comprendre c'est que c'est la qualité de l'algo de resolution qui fera la difficulté de la grille.
Ca permet d'alleur, en separant les algos de resolution, de choisir la difficulté de la grille generee.
Ca par contre tu as tout à fait raison.Envoyé par monstroplante
"La haine seule fait des choix" - Koan Zen
"Il ne faut pas être meilleur que les autres, il faut être meilleur que soi." Albert Jacquard
"Ceux qui savent où ils ont posé leur parapluie ne sont pas alcooliques." - pgibonne.
Faites du Prolog, ça vous changera les idées !
Ma page Prolog
Mes codes sources commentés
Mon avatar : La Madeleine à la veilleuse de Georges de La Tour
pour générer un sudoku qui n'a qu'une solution j'ajoute des
nombres
je remplis les quatres carrés de base placés aux quatre extrémités
après chaque nombre placé je lance l'algo de résolution qui me donne
les nombres que je peux placer au coup suivant
quand mon algo de résolution a trouvé la solution je dispose d'une
grille complète valide
il suffit alors de travailler avec deux grilles
je tire un nombre au hasard dans la grille résolue et je l'applique
au problème quand mon algo de résolution a trouvé la solution le problème est complet
la qualité du problème dépend donc de celle de l'algo de résolution
ps ceci ne génère pas nécessairement des problèmes intéressants
par contre cela permet de s'imprègner de tous les aspects du problème
Elle est pas belle la vie ?
Il existe une liste de toutes les grilles du Sodoku possible. On en prend une au hasard, et on supprime des points au fur et à mesure.
Le seul pb, c'est effectivement que l'algo de résolution soit balèze - on peut même donner la complexité de la résolution en comptant le nombre d'appels à des fonctions de résolution genre assigner la seule valeur restante, assigner la seule case qui a une valeur dans un regroupement, ôter des valeurs dans un regroupement, ... -, et pour l'instant, je n'en ai pas vu capable de résoudre les 3 grilles que je fournis avec mon solveur - qu'il faudrait que je fasse évoluer un peu et qui sera aussi bientôt sur Sourceforge avec possibilité de l'essayer sous Linux et sous Windows -
Nous sommes donc tous d'accord que la difficulté réside dans le codage de l'algo de résolution.
Pour ma part, j'ai pensé à une regle supplémentaire :
Considerons un bloc (carré de 3x3 cases) :
-Il peut se décomposer en 3 lignes.
-Chaqune de ces lignes fait partie d'une ligne du tableau general.
Imaginons maintenant qu'une possibilité ne soit presente que dans une ligne de notre bloc. Nous pouvons en déduire que cette possibilité ne peut se trouver dans le reste de la ligne du tableau general dont fait partie cette ligne du bloc.
Inversement : On peut decomposer une ligne du tableau général en 3 morceaux de 3 cases. Si une possibilité n'est presente que dans un de ces morceaux alors, cette possibilité peut etre supprimée du reste du bloc dont fait partie ce morceau.
On peut, bien sur, appliquer cette regle aux colones...
Voila, c'est tout ce que j'ai trouvé pour le moment mais je me demande si il n'y a pas une regle plus generale a trouver...
Ca s'appelle notre règle n°2 de Dr Topos, non ?
J'ai bien eu l'impression en effet qu'on était déjà passé par là. Mais je n'ai pas trop le temps de m'occuper de Sudoku en ce moment.Envoyé par Miles
Miles -> où en es-tu de ta démonstration ?
En effet ca ressemble à une de ces regles (plustot la 3).
Je n'avait pas lu en détail...
Petite subtilité tout de meme, na nuance suivante n'avait pas étée abordée :
En dehors de ca, il me semble que toutes les regles évoquées sont prises en compte par mon algo de base. Sauf, peut etre, la regle N2 mais je n'en ait pas le tps de verifier ce soir.Inversement : On peut decomposer une ligne du tableau général en 3 morceaux de 3 cases. Si une possibilité n'est presente que dans un de ces morceaux alors, cette possibilité peut etre supprimée du reste du bloc dont fait partie ce morceau.
J'ai déjà cette subtilité dans mon programme
Les règles seront de plus en plus difficiles, je n'ai pas encore analysé précisément quelles pourraient être les moyens de résoudre les 3 grilles très très très très difficiles, mais effectivement, je n'ai pas de démonstration que les 3 règles suffisent, ou plutôt j'ai la preuve qu'elles ne suffisent pas
la complexité maximale du problème est ici toujours égale à la sagacité du solveur
en effet celui qui publie le problème doit proposer une solution
unique
c'est donc qu'il manque des règles au solveur
Elle est pas belle la vie ?
cela dit, on peut tout de meme proceder par essai erreur.
Je m'explique :
On peu déterminer si une grille à une solution unique en appliquant un algo de base (elimine les possibilitées uniquement en se basant sur les case ellucidées).
Pour ce faire, il suffit :
-d'appliquer l'algo jusqu'a ce qu'il ne trouve plus rien a resoudre
-On choisit une case qui à plusieurs possibilitées
-On choisit une de ces possibilitées au hasard
-On réapplique l'algo jusqu'a ce qu'il ne trouve plus rien a resoudre
-On continue jusqu'a ce que l'algo démontre que la grille est invalide (un case doit se retrouver sans possibilité)
-On peut alors elliminer la possibilité choisie au départ puisquelle conduit à une grille invalide.
Par contre, si l'algo parvient a resoudre la grille c'est qu'il n'y a qu'une seule possibilité suite au choix que nous avons fait. Il faut alors vérifier si un autre choix pour la meme case de départ aurait pu donner une solution...
J'espere que cette explication est suffisement comprehensible (elle meriterait d'hetre mieu developpée).
Du coup, puisque nous disposons d'un alogo qui est capable de determiner pour n'importe quelle grille si elle a une et une seule solution, nous sommes aussi en mesure de generer des grilles d'une difficultée maximum...
C'est la bifurcation, mais je ne trouve pas ça une super approche
Je suis d'accord mais c la seulle que nous ayons pour le moment qui soit capable de generer des grilles d'une difficulté sans limite.
Je ne considere pas pour autant qu'il soit ininteressant de trouver une methode plus élégante.
Il me semble simplement que cette solution devait etre évoquée.
Mouais... Le problème avec la bifurcation, c'est qu'il faut tester les autres possibilités afin de n'avoir qu'une seule solution.
En fait, pour etre plus precis, on ne test que des arbres de possibilité. à chaque fois que l'algo de resolution bloque, on cree un nouvel arbre. Donc plus l'algo de resolution est efficace et moin on aura d'arbre de possibilité à verifier.
Deux questions :
Combien existe-t-il de grilles complètes valides au Sudoku ?
Combien existe-t-il de grilles incomplètes donnant une et une seule solution ?
J'affirme péremptoirement que toute affirmation péremptoire est fausse
5ième élément : barde-prince des figures de style, duc de la synecdoque
Je ne réponds jamais aux questions techniques par MP
en fait pour la bifurcation il faut partir à l'envers
j'ai une grille avec n chiffres placés qui conduit à une solution valide
j'ai la grille précédente avec n-1 chiffre placés qui diffère de n par la résolution d'un bigramme sur le solveur
si je propose la grille n-1
le solveur va s'arrêter en n-1 si j'inhibe la bifurcation
en testant les deux chiffres du bigramme je vais arriver
soit à une solution non valide (non respect des contraintes)
soit à la solution valide
partant de n-1 je peux remonter en n-2 éventuellement 4 solutions possibles
c'est encore dire que solveur et générateur sont toujours de même niveau
Elle est pas belle la vie ?
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