Voici un bon à réfléchir sur:
http://fr.wikipedia.org/wiki / Kakuro
Je tente de faire un solveur pour ce jeu. La paperasse est terminée (en lisant un fichier initial avec un nombre variable de colonnes et de lignes. Il est supposé que le fichier d'entrée suit les règles du jeu afin que le jeu soit toujours solvable. Prenez votre temps pour lire les règles de jeu. < P> J'ai pris soin de la structure de données que je pense conviendra mieux: et fait un "tableau" de ceux-ci de manière dynamique pour fonctionner.
Je l'ai fait pour que les carrés noirs avaient une valeur de -1 et des carrés blancs (les carrés de solution réelles) initialisent à 0. Vous pouvez également obtenir la position de chaque structure ASquare à partir du tableau facilement, pas besoin de faire des champs de structure supplémentaires pour cela. . Maintenant l'algorithme ... Comment dans le monde vais-je concilier toutes ces sommes et trouver une manière générale qui résoudra tous les types de grilles. Je me suis battu avec cela tout l'après-midi en vain. aide est apprécié, amusez-vous! * Modifier: Je viens de réaliser que le lien réel que j'ai publié a des conseils concernant la résolution de techniques de résolution. Je resterai toujours là pour voir ce que les gens montent.
6 Réponses :
Il s'agit d'une algèbre linéaire directe, d'utiliser des techniques de manipulation vectorielles / matrix pour résoudre.
[Modifier - Répondre aux commentaires] P>
a 0 0 0 0 na 0 b 0 0 0 nb 0 0 c 0 0 nc 0 0 0 d 0 nd 0 0 0 0 e ne
En utilisant une algèbre linéaire, vous ne vous retrouverez généralement pas avec une solution entière. La combinatoire doit entrer en quelque sorte.
L'algèbre linéaire ne peut représenter la règle de la duplication sans chiffre.
Dans votre exemple, il y a un ordre d'élimination où la solution est tous des entiers, mais trouver une telle commande pour une matrice générale de 0-1 n'est pas facile. Essayez d'effectuer une élimination gaussienne dans l'ordre que vous présentez, vous constaterez que 1/2 rampe dans. Dans ce cas, un bon ordre est facile à trouver (un exemple est un, B, D, C, E), mais dans Général, vous auriez besoin de pouvoir revenir en arrière dans le GE au cas où un élément de matrice ultérieur s'avère fractionnaire en raison d'une décision antérieure.
Se souvient de cette technique, pensait que cela pourrait être utile. (Effectivement oublié, c'était Gauss - merci)
En pensant à cela un peu plus, je me suis rendu compte que mon point sur 1/2 rampant n'est pas toute l'histoire. Si vous avez une matrice inversible carrée, vous obtiendrez la bonne réponse, même si les fractions apparaissent dans GE. Le problème réel est que le système d'un puzzle Kakuro est sous-déterminé (dans l'exemple Wikipedia, vous obtenez une matrice 24x36), une fois que vous avez terminé, vous devez déterminer comment attribuer toutes les variables libres pour obtenir le reste de eux d'être des entiers. Cela rétrécit considérablement l'espace de recherche, de sorte que cela aiderait comme une étape de prétraitement dans l'approche de retour arrière.
Si votre intérêt est finalement dans la création d'un solutionniste logiciel pour ces jeux, mais je ne recommande pas d'utiliser un moteur de programmation de contraintes (CP). Le CP est un paradigme de programmation déclaratif qui convient très bien à ces types de problèmes. Plusieurs moteurs CP commerciaux et open source sont disponibles.
Un simple solveur de force brute pour Sudoku prend des Milisecondes à courir, de sorte que vous n'avez pas besoin de déranger de mettre en œuvre des tactiques spéciales. Je pense que dans le cas de Kakuro, ce sera le même. Un algorithme simple: Cet algorithme pourrait mieux fonctionner si vous trouvez le meilleur ordre des champs à remplir. Essayez de choisir des champs qui seront les plus contraints (comme dans: il n'y a pas beaucoup de valeurs légales). Quoi qu'il en soit, cela sera probablement le plus simple à mettre en œuvre, alors essayez-le et cherchez plus sophistiqué Solvers uniquement si celui-ci ne fonctionnera pas. (En réalité, il s'agit d'un des solvants de programmation de contraintes les plus simples; les solveurs de CP réels sont bien compliqués, bien sûr).
Notez qu'il y a beaucoup de place à l'intelligence dans le «[calculer les valeurs juridiques possibles pour ce champ]».
@Brian: plus pour choisir une position, comme dans de nombreux algorithmes, cela pourrait signifier passer du polynôme à l'époque exponentielle. Kakoru est un NP-complet, mais en choisissant toujours la commande judicieusement peut rendre les constantes beaucoup plus petites. Et calculer des valeurs juridiques possibles devraient être une durée constante avec des structures de données appropriées, de toute façon.
Assez juste. Dans un solveur, j'ai conçu (pour un autre casse-tête), une astuce que j'ai utilisée était de choisir chaque position et d'essayer pour une itération, en utilisant la preuve par contradiction pour réduire le nombre de valeurs juridiques possibles. Je suis également rempli dans tous les espaces qui n'avaient qu'une valeur juridique possible. Ainsi, mon puzzle avait un de facto [Calculez des valeurs légales possibles pour chaque champ] . Mon sélecteur de position pour faire des suppositions n'avait aucune intelligence du tout et n'en a pas vraiment besoin. Pour être juste, Nurikabe est un puzzle binaire. Toutes les positions sont donc également contraintes.
Je devinerais que Dans tous les cas à l'aide d'une table avec les combinaisons les plus sûrs seront utiles à coup sûr (par exemple, http: //www.enigmoteka.com/kakuro%20cheatsheet.pdf )
J'ai trouvé de belles astuces de manipulation binaire qui accélèrent la résolution de Kakuro. Vous pouvez choisir la source ici .
En ce qui concerne la programmation de contraintes: Voici quelques implémentations différentes de la manière de résoudre un casse-tête Kakuro avec une programmation de contraintes (tout en utilisant le même principe de base). L'instance de problème est fixée dans le programme.
Edit: Ajout de Google OU-Outils / C # et de réponses SET SET PROGRAMMATION.