Discussion :

[pierrot la lune]

bonjour, j'ai réaliser un jeu de kakuro en flash, j'ai donc créer un génerateur de grille (et aussi un solveur de grille). Mon problème est certaines de mes grilles ne sont pas uniques. j'ai beau chercher sur le net, je n'ai pas trouvé d'algo ou d'explication sur le net sur la generation de grille unique, auriez vous des pistes ou des explications?

merci beaucoup, vous me sauveriez la vie ou presque

[random]

si la grille n'est pas unique le solveur ne trouvera pas de solution ou trouveras
plusieurs solutions par élaguage des voies impraticables


tu passes la grille générée au solveur s'il échoue c'est qu'il faut complèter ta grille ou améliorer ton solveur

en fait dans ce type de problème le générateur et le solveur sont de même
niveau

[pierrot la lune]

bref en gros, c'est mon solveur qui déconne?
en faite pour generer ma grille, je place de façon aléatoire des case vides, puis je complète ces cases avec des chiffres posé aléatoirement. je fait ensuite la sommes des lignes et colonnes. Donc à la base, j'ai deja une solution (qui peut être non unique). Ensuite j'utilise mon solveur pour voir s'il y a trouver plusieurs solutions. je prend peu être le problème à l'envers?
je devrais d'abord placer de façon aléatoire (ou presque) les sommes des lignes et colonnes et voir s'il existe une solution?
j'ai peu être mal foutu mon solveur? je dois chercher vraiment toute les solutions possibles et imaginable. ce qui me pause aussi problème c'est que même maintenant la recherche de grilles valide prend beaucoup beaucoup de temps (pour une 9x9, je peu mettre toute une nuit, sick!!!)
bref merci pour la précision, je déjà vais regarder plus en détail les algo de solveur, peu être y trouverais je mon bonheur

[random]

tu pourrais suivre cette voie
dans ton solveur tu dois avoir deux parties

une partie qui évacue les positions impossibles
une partie qui procède par essai erreur

tu inhibes la partie essai erreur et tu génères des nombres aléatoires jusqu'à
optention d'une solution unique ceci doit tourner très vite et te donner la solution

à ce point tu as la solution et tu es au point exact où ton solveur sans essai erreur sait résoudre le problème


il te reste à règler le niveau du problème
tu peux rendre le problème plus facile en ajoutant un ou plusieurs nombres au problème

ou le rendre plus difficile pour cela tu peux restaurer la fonction essai et tu enlèves un ou plusieurs nombres en mesurant la profondeur de l'arbre de recherche nécessaire

[pierrot la lune]

merci, beaucoup. étant un vacances demain soir, je devrais avoir un peu de temps pour digérer ce que tu m'as dit et le mettre en application merci.

[tails]

Bonjour

J'ai un ordinateur 1,6 Ghz tournant sur Ubuntu 8.04

J'ai essayé de générer des grilles de kakuro en Java 1.6 sous NetBeans à partir d'ossatures de grilles existantes(les cases restent du même type : neutre, à indices, ou remplissage; seules leurs valeurs changent)

-----------------------------------------------------------------------
Voici ma méthode .
1) Je vide les cases remplissages de la grille qui sert de modèle (je les mets à la valeur 0).
2) Je remplis, grâce à un générateur de nombres aléatoires (java.util.Random), les différentes cases tout en respectant les contraintes d'unicité de chiffre par bloc de somme à résoudre .
3) Je modifie les indices en fonction des cases remplissages
4) Je passe la grille au solveur de grille => un booléen m'indique si la grille admet et, et une seule solution
5) Succès si c'est le cas . Sinon, si le nombre de tentatives n'est pas trop élevé (du genre 10000 essais), je repasse en 1)
-----------------------------------------------------------------------

Verdict ?

Pour les grilles 3*3 (4 cases remplissage disposées en carré) : solution unique et temps de génération < 1s

Pour les grilles 8*8 (avec une structure plus ou moins complexe) : solution unique et temps de génération : environ 30s .

Et
pour les grilles 10*10
échec dans tous les cas de figure .

--------------------------------------------------------------------------

Quelqu'un pourrait-il me proposer une meilleure solution ?