cs_loloof64
Messages postés342Date d'inscriptionvendredi 1 septembre 2006StatutMembreDernière intervention 6 novembre 2012
-
13 sept. 2008 à 15:12
cs_loloof64
Messages postés342Date d'inscriptionvendredi 1 septembre 2006StatutMembreDernière intervention 6 novembre 2012
-
13 sept. 2008 à 15:16
Bonjour à tous
J'ai du mal à créer de grilles de kakuro de taille assez importante (à partir de 8*8) .
J'ai passé enormément de temps sur le Web pour trouver une solution efficace afin de générer une grille Kakuro (les fameurx mots-fléchés où les défintions sont remlacées par des sommes à atteindre avec des chiffres non répétés).
Je suis arrivé sur une page de developpez.com où un développeur décrivit, mais malheureusement trop succinctement, une solution :
-> on crée un fonction qui puisse résoudre les kakuro
-> on procède par essais-erreurs (sic : ce sont ses propres termes) à l'aide du solveur : je pense que l'erreur à détecter est la multiplicité des solutions.
( voici la page : http://www.developpez.net/forums/d251945/autres-langages/algorithmes/kakuro-generateur-grille-unique/ )
Bref, j'ai décidé
-> de créer mon propre solveur basé sur les candidats uniques (les solveurs par backtracking que j'ai trouvés sur le web ne me convenaient pas : ils ne me renseignaient pas sur la multiplicité des solutions, mais se contentaient d'en fournir la première trouvée)
-> de me baser sur des modèles de grilles pour en générer des nouvelles, au lieu de m'embêter à chercher des agencements de cases à remplir qui puissent satisfaire à la recherche de grilles à solutions uniques (c'est à dire, que l'agencement puisse disposer d'au moins une grille qui ait une et une seule solution)
Voilà comment je procède (le projet résultat figure déja sur le site sur le nom de application kakuro)
-> la grille couramment définie dans l'interface par l'utilisateur appelle sa méthode de résolution (la structure GrilleKakuro dispose d'une méthode générer() qui s'applique à l'instance courante, soit GrilleKakuro.this)
-> dans cette méthode,
->je crée une fois pour toutes les structures de résolutions nécessaires (celles dont le solveur a besoin : alors que pour une résolution demandée par l'utilisateur, elles sont directement crées dans la fonction résoudre() ) : donc le problème de rapidité ne devrait pas se situer à ce niveau . Ces structures sont en gros les blocs de sommes à atteindre et les cases à remplir .
-> J'éfface toutes les valeurs des cases résolution à remplir, je remplis les différentes cases resolution avec des chiffres aléatoires (la défintion même des blocs résolutions et des cases résolutions, ainsi que leurs pointages mutuels, permet de vérifier automatiquement que les chiffres ne se répètent pas dans un même bloc -> c'est peut-être ici que je pourrais gagner du temps, mais je n'en suis pas sûr), je recalcule les indices des blocs résolution en fonctions des chiffres générés, j'efface à nouveau les cases résolution et je passe l'ensemble des structures résolution au solveur pour voir si la solution est unique (le solveur affecte directement les cases résolutions, donc en cas d'échec il faudra de nouveau les effacer) .
->Je reviens au point précédent si la solution n'est pas unique .
Bon, enfin la question :
connaitriez-vous s'il vous plait une méthode plus rapide pour générer des grilles ?
Je vous remercie d'avance et je suis prêt à apporter plus de précisions sur mon projet Application Kakuro si cela peut se révéler utile . (et même si cela se rapporte à un autre sujet que la génération de grilles ) .
