Techniques combinatoiresModification
Bien que la devinette par force brute soit possible, une approche plus efficace est la compréhension des diverses formes combinatoires que les entrées peuvent prendre pour diverses paires d’indices et de longueurs d’entrée. L’espace de solution peut être réduit en résolvant les intersections autorisées des sommes horizontales et verticales, ou en considérant les valeurs nécessaires ou manquantes.
Les entrées avec des indices suffisamment grands ou petits pour leur longueur auront moins de combinaisons possibles à considérer, et en les comparant avec les entrées qui les croisent, la permutation appropriée – ou une partie de celle-ci – peut être dérivée. L’exemple le plus simple est celui où un 3-en-deux croise un 4-en-deux : le 3-en-deux doit être constitué de « 1 » et de « 2 » dans un certain ordre ; le 4-en-deux (puisque « 2 » ne peut être dupliqué) doit être constitué de « 1 » et de « 3 » dans un certain ordre. Par conséquent, leur intersection doit être « 1 », le seul chiffre qu’ils ont en commun.
Lors de la résolution de sommes plus longues, il existe des moyens supplémentaires de trouver des indices pour localiser les bons chiffres. Une de ces méthodes serait de noter où quelques carrés ensemble partagent des valeurs possibles éliminant ainsi la possibilité que d’autres carrés de cette somme puissent avoir ces valeurs. Par exemple, si deux indices 4-en-deux se croisent avec une somme plus longue, alors le 1 et le 3 de la solution doivent se trouver dans ces deux carrés et ces chiffres ne peuvent pas être utilisés ailleurs dans cette somme.
Lors de la résolution de sommes qui ont un nombre limité d’ensembles de solutions alors cela peut conduire à des indices utiles. Par exemple, une somme de 30 en sept n’a que deux ensembles de solutions : {1,2,3,4,5,6,9} et {1,2,3,4,5,7,8}. Si l’un des carrés de cette somme ne peut prendre que les valeurs {8,9} (si l’indice de croisement est une somme de 17 en deux, par exemple), alors cela devient non seulement un indicateur de l’ensemble de solutions qui correspond à cette somme, mais cela élimine la possibilité que tout autre chiffre de la somme soit l’une ou l’autre de ces deux valeurs, avant même de déterminer laquelle des deux valeurs correspond à cette case.
Une autre approche utile dans les casse-têtes plus complexes consiste à identifier dans quelle case un chiffre va en éliminant d’autres emplacements dans la somme. Si tous les indices de croisement d’une somme ont de nombreuses valeurs possibles, mais qu’on peut déterminer qu’il n’y a qu’une seule case qui pourrait avoir une valeur particulière que la somme en question doit avoir, alors quelles que soient les autres valeurs possibles que la somme de croisement permettrait, cette intersection doit être la valeur isolée. Par exemple, une somme de 36 sur 8 doit contenir tous les chiffres sauf 9. Si un seul des carrés peut prendre la valeur de 2, alors ce doit être la réponse pour ce carré.
Technique des casesModifié
Une « technique des cases » peut également être appliquée à l’occasion, lorsque la géométrie des cases blanches non remplies à un stade donné de la résolution s’y prête : en additionnant les indices d’une série d’entrées horizontales (en soustrayant les valeurs des chiffres déjà ajoutés à ces entrées) et en soustrayant les indices d’une série d’entrées verticales qui se chevauchent pour la plupart, la différence peut révéler la valeur d’une entrée partielle, souvent une seule case. Cette technique fonctionne parce que l’addition est à la fois associative et commutative.
Il est courant de marquer les valeurs potentielles des cellules dans les coins des cellules jusqu’à ce que toutes, sauf une, aient été prouvées impossibles ; pour les énigmes particulièrement difficiles, des plages entières de valeurs pour les cellules sont parfois notées par les résolveurs dans l’espoir de trouver éventuellement suffisamment de contraintes à ces plages à partir des entrées croisées pour pouvoir réduire les plages à des valeurs uniques. En raison des contraintes d’espace, certains résolveurs utilisent, au lieu de chiffres, une notation positionnelle, où une valeur numérique potentielle est représentée par une marque dans une partie particulière de la cellule, ce qui permet de placer facilement plusieurs valeurs potentielles dans une seule cellule. Cela permet également de distinguer plus facilement les valeurs potentielles des valeurs de solution.
Certains résolveurs utilisent également du papier millimétré pour essayer diverses combinaisons de chiffres avant de les inscrire dans les grilles du puzzle.
Comme dans le cas du Sudoku, seuls les puzzles de Kakuro relativement faciles peuvent être résolus avec les techniques mentionnées ci-dessus. Les plus difficiles nécessitent l’utilisation de divers types de motifs en chaîne, les mêmes que ceux qui apparaissent dans le Sudoku (voir Satisfaction de contraintes basée sur des motifs et casse-tête logiques).