begin process at 2010 03 18 22:18:14
  Trouver un code source :
 
dans
 
Accueil > Forum > 

JAVA / J2EE / J2ME

 > 

Algorithme

 > 

Maths

 > 

[Kakuro] Générer rapidement une grille .


Derniers messages déposésPoser une question dans le forum ou lancer une discussion

[Kakuro] Générer rapidement une grille .

samedi 13 septembre 2008 à 15:12:47 | [Kakuro] Générer rapidement une grille .

loloof64

Membre Club

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 : [ Lien ] )

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

samedi 13 septembre 2008 à 15:16:01 | Re : [Kakuro] Générer rapidement une grille .

loloof64

Membre Club

Ah oui, j'ai oublié de préciser que mon objectif est de créer des grilles à solution unique .



Cette discussion est classée dans : générer, grille, cases, résolution, kakuro


Répondre à ce message

Sujets en rapport avec ce message

Générer aléatoirement des lettres [ par amlev11 ] Bonjour!Je dois créer une espèce de jeu de type Boggle pour mon cours.  Mon problème se situe au niveau de la génération les lettres.  Le jeu comporte Toutes les cases (libres) d'une grille sont-elles connectées ? Par le pathfinding ? [ par loloof64 ] Bonjour à tous Tout d'abord, après une recherche sur la toile, j'ai trouvé un tutoriel très intéressant et qui explique très bien le fonctionnement de résolution d'écran [ par lasayoub ] BonjourTout de suite voici ma question : Comment puis je detecter la résolution d'écran des portables et PDA pour que mon application java (J2ME) soit Changer la résolution d'une image en java [ par alex10843 ] Bonjour tout le monde, quelqu'un pourrait-il me dire s'il est possible de changer la résolution d'une image et si oui comment. En fait j'aimerais bais Générer des nombres unique [ par moonracker0210 ] Bonjour à tous. Je cherche à générer une liste de nombre allant de 1 à 54. Jusque la, pas de soucis. Mais j'aimerais que cette liste contiennent des grille haxagonale [ par shemcylin ] Bonjour à tous, je cherche à progammer en java une grille hexagonale, en n'utilisant que la moitié de celui-ci pour éviter une double lecture du progr générer objets métiers EJB3 et une couche présentation à partir de JPA [ par achrafff ] Bonjour, Mon but est de générer objets métiers EJB3 et une couche présentation riche de test à partir d'une couche JPA. Explication:A partir de JPA g générer des sources en java [ par tamami ] [^^happy13]salut tout le monde moi je cherche comment faire pour générer des paquet en java c'est-à-dire de créer une source qui envoi des paquets de debutant illegal star of expression [ par scyon ] Le but de mon code est de chercher l'attribut FOR dans ma bdd, faire un private int case[][] selon le cas... J'ai toujours la meme erreur sans savoir pb avec void init() [ par scyon ] Alors voilà. Je veux réaliser un applet faisant appel à plusieurs classes. Mon but est de faire une map. J'ai une première classe nommée AppletJeu dan


Nos sponsors


Sondage...

Comparez les prix

CalendriCode

Mars 2010
LMMJVSD
1234567
891011121314
15161718192021
22232425262728
293031    

Consulter la suite du CalendriCode

Photothèque

 
Développement réalisé par Nicolas SOREL (Nix) avec l'aide de : Cyril DURAND et Emmanuel (EBArtSoft), Merci à Vincent pour ses précieux conseils.
CodeS-SourceS.com© Toute reproduction même partielle est interdite sauf accord écrit du Webmaster
CodeS-SourceS.com© est une marque déposée tous droits réservés

Google Coop CodeS-SourceS Google Coop CodeS-SourceS
Temps d'éxécution de la page : 0,484 sec (4)

Nous contacter | Annoncer sur CodeS-SourceS | Mentions légales