Kakuro

Técnicas combinatóriasEditar

Apesar de ser possível adivinhar a força bruta, uma abordagem mais eficiente é a compreensão das várias formas combinatórias que as entradas podem assumir para vários pares de pistas e comprimentos de entrada. O espaço de solução pode ser reduzido pela resolução de intersecções admissíveis de somas horizontais e verticais, ou considerando valores necessários ou ausentes.

As entradas com pistas suficientemente grandes ou pequenas para o seu comprimento terão menos combinações possíveis a considerar, e ao compará-las com as entradas que as cruzam, a permutação adequada – ou parte dela – pode ser derivada. O exemplo mais simples é onde um 3 em dois cruza um 4 em dois: o 3 em dois deve consistir em “1” e “2” em alguma ordem; o 4 em dois (já que “2” não pode ser duplicado) deve consistir em “1” e “3” em alguma ordem. Portanto, sua intersecção deve ser “1”, o único dígito que eles têm em comum.

Ao resolver somas mais longas, há maneiras adicionais de encontrar pistas para localizar os dígitos corretos. Um desses métodos seria observar onde alguns quadrados juntos compartilham valores possíveis, eliminando assim a possibilidade de que outros quadrados dessa soma possam ter esses valores. Por exemplo, se duas pistas de 4 em 2 se cruzarem com uma soma mais longa, então a 1 e 3 na solução devem estar nesses dois quadrados e esses dígitos não podem ser usados em outro lugar nessa soma.

Ao resolver somas que têm um número limitado de conjuntos de soluções, então isso pode levar a pistas úteis. Por exemplo, uma soma de 30 em sete só tem dois conjuntos de soluções: {1,2,3,4,5,6,9} e {1,2,3,4,5,7,8}. Se um dos quadrados dessa soma só pode assumir os valores de {8,9}. (se a pista de cruzamento for uma soma de 17 em dois, por exemplo), então isso não só se torna um indicador de qual conjunto de soluções se encaixa nessa soma, como elimina a possibilidade de qualquer outro dígito na soma ser um desses dois valores, mesmo antes de determinar qual dos dois valores se encaixa nesse quadrado.

Outra abordagem útil em quebra-cabeças mais complexos é identificar qual quadrado um dígito entra eliminando outros locais dentro da soma. Se todas as pistas de cruzamento de uma soma têm muitos valores possíveis, mas pode ser determinado que existe apenas um quadrado que poderia ter um determinado valor que a soma em questão deve ter, então quaisquer outros valores possíveis que a soma de cruzamento permitiria, essa intersecção deve ser o valor isolado. Por exemplo, uma soma de 36 em 8 deve conter todos os dígitos, exceto 9. Se apenas um dos quadrados pudesse assumir o valor 2, então essa deve ser a resposta para esse quadrado.

Técnica de caixaEditar

Uma “técnica de caixa” também pode ser aplicada ocasionalmente, quando a geometria das células brancas não preenchidas em qualquer estágio da solução se presta a ela: somando as pistas para uma série de entradas horizontais (subtraindo os valores de quaisquer dígitos já adicionados a essas entradas) e subtraindo as pistas para uma série de entradas verticais na maioria das vezes sobrepostas, a diferença pode revelar o valor de uma entrada parcial, muitas vezes uma única célula. Esta técnica funciona porque a adição é tanto associativa quanto comutativa.

É prática comum marcar valores potenciais para células nos cantos das células até que todos os valores, exceto um, tenham sido provados impossíveis; para quebra-cabeças particularmente desafiadores, às vezes intervalos inteiros de valores para células são anotados por solucionadores na esperança de eventualmente encontrar restrições suficientes para esses intervalos de cruzamento de entradas para ser capaz de estreitar os intervalos para valores únicos. Devido às restrições de espaço, em vez de dígitos alguns solvers usam uma notação posicional, onde um valor numérico potencial é representado por uma marca em uma determinada parte da célula, o que facilita a colocação de vários valores potenciais em uma única célula. Isto também torna mais fácil distinguir valores potenciais de valores de solução.

Alguns solvers também usam papel gráfico para tentar várias combinações de dígitos antes de escrevê-los nas grades do enigma.

Como no caso do Sudoku, apenas enigmas Kakuro relativamente fáceis podem ser resolvidos com as técnicas acima mencionadas. Os mais difíceis requerem o uso de vários tipos de padrões de correntes, os mesmos tipos que aparecem no Sudoku (veja Enigmas de Lógica e Satisfação de Restrições Baseadas em Padrões).