# Kakuro

O kakuro (カックロ em japonês) é um jogo de raciocínio lógico, considerado mais difícil que o sudoku. De origem japonesa, resulta da palavra adição com a palavra inglesa cross, que em português significa cruzar.
Pode ser entendido como a transliteração matemática das palavras cruzadas, sendo por isso conhecido nos Estados Unidos como Cross Sums, ou seja, Somas Cruzadas. É um desafio aliciante para quem aprecia sudoku. Joga-se igualmente com números, de 1 a 9, e também não é necessário ser um gênio matemático para saber resolver estes quebra-cabeças. Apenas requer perícia, prática e muita paciência. Os quebra-cabeças de kakuro apareceram pela primeira vez, na Inglaterra, no Outono de 2005.

## Jogo padrão e terminologia

O tipo de jogo kakuro padrão é jogado em uma grelha composta de células não preenchidas - “pretas e brancas”, respectivamente – geralmente no tamanho 16×16 mas podem variar muito deste formato. A grelha, assim como nas palavras cruzadas, é dividida em entradas – linhas ortogonais de células brancas – e células pretas. As células pretas não são inteiramente sólidas, elas contêm um traço diagonal do canto superior esquerdo ao canto inferior direito e um número em cada uma das metades, de tal maneira que cada entrada horizontal tem o seu número correspondente na metade da célula preta posicionada imediatamente a sua esquerda, e cada entrada vertical tem o seu número na metade da célula preta posicionada imediatamente acima. Estes números, continuando a utilizar a terminologia das palavras cruzadas, são chamados de dicas.
O objetivo do passatempo é colocar números de 1 a 9 em cada uma das células brancas, de tal maneira que a soma de todos os números em cada entrada se iguale ao número da dica associada a ela e que nenhum número esteja duplicado em cada entrada. E é esta restrição aos números duplicados que faz com que os kakuros sejam criados com uma única solução possível.
Alguns publicadores preferem imprimir as suas grelhas de kakuro exactamente da mesma forma como as grelhas de palavras cruzadas, sem dicas nas células pretas, fornecendo uma lista separada com as dicas semelhante às listas de palavras cruzadas (Isto elimina a primeira linha e coluna que são inteiramente pretas). Isto é apenas uma questão de aparência e não afecta a solução (pelo menos, não além de ter que olhar para fora da grelha para solucionar o passatempo).
Nas discussões de técnicas de solução do jogo kakuro a simbologia abreviada típica para se referir a uma entrada é "(dica, em números)-em-(número de células da entrada, por extenso)", por exemplo, "16-em-duas" que significa que o total 16 deve ser preenchido em duas células brancas, ou "25-em-cinco" que significa que o total de 25 deve ser preenchido em cinco células.

## Técnicas de Solução

Apesar da força bruta da suposição que pode ser empregada, uma arma melhor é a compreensão das várias formas combinatórias que as entradas podem ter para as diversas combinações de dicas e comprimentos das entradas. As entradas suficientemente grandes ou dicas pequenas pelo seu comprimento irão ter poucas combinações possíveis a serem consideradas, e através da comparação com as entradas que cruzam com ela e as permutas possíveis – ou parte delas – a resposta pode ser obtida. O exemplo mais simples é o 3-em-duas cruza com 4-em-duas: o 3-em-duas consiste de '1' e '2' em qualquer ordem; e 4-em-duas (já que '2' não pode ser duplicado) deve consistir de '1' e '3' em qualquer ordem. Portanto, a sua intersecção deve ser '1', que o único dígito que eles tem em comum.
A "técnica da caixa" pode também ser aplicada em alguns casos, quando a geometria das células brancas não preenchidas em um determinado estágio da solução ficar no formato de uma caixa: somando-se as "dicas" para uma série de entradas horizontais (subtraindo se os valores de quaisquer dígitos já adicionados a aquelas entradas) e subtraindo as "dicas" para uma série geralmente sobreposta de entradas verticais, a diferença pode revelar o valor de uma entrada parcial, frequentemente de uma única célula.

## Somas Possíveis

Segue uma lista de algumas dicas e seus respectivos comprimentos com somente uma combinação possível em um kakuro; perceba que a ordem correta dos dígitos ainda deve ser determinada:
3-em-dois: 1, 2 4-em-dois: 1, 3 16-em-dois: 7, 9 17-em-dois: 8, 9 6-em-três: 1, 2, 3 7-em-três: 1, 2, 4 23-em-três: 6, 8, 9 24-em-três: 7, 8, 9 10-em-quatro: 1, 2, 3, 4 11-em-quatro: 1, 2, 3, 5 29-em-quatro: 5, 7, 8, 9 30-em-quatro: 6, 7, 8, 9 15-em-cinco: 1, 2, 3, 4, 5 16-em-cinco: 1, 2, 3, 4, 6 34-em-cinco: 4, 6, 7, 8, 9 35-em-cinco: 5, 6, 7, 8, 9 21-em-seis: 1, 2, 3, 4, 5, 6 22-em-seis: 1, 2, 3, 4, 5, 7 38-em-seis: 3, 5, 6, 7, 8, 9 39-em-seis: 4, 5, 6, 7, 8, 9 28-em-sete: 1, 2, 3, 4, 5, 6, 7 29-em-sete: 1, 2, 3, 4, 5, 6, 8 41-em-sete: 2, 4, 5, 6, 7, 8, 9 42-em-sete: 3, 4, 5, 6, 7, 8, 9 36-em-oito: 1, 2, 3, 4, 5, 6, 7, 8 37-em-oito: 1, 2, 3, 4, 5, 6, 7, 9 38-em-oito: 1, 2, 3, 4, 5, 6, 8, 9 39-em-oito: 1, 2, 3, 4, 5, 7, 8, 9 40-em-oito: 1, 2, 3, 4, 6, 7, 8, 9 41-em-oito: 1, 2, 3, 5, 6, 7, 8, 9 42-em-oito: 1, 2, 4, 5, 6, 7, 8, 9 43-em-oito: 1, 3, 4, 5, 6, 7, 8, 9 44-em-oito: 2, 3, 4, 5, 6, 7, 8, 9 45-em-nove: 1, 2, 3, 4, 5, 6, 7, 8, 9

## A Matemática do kakuro

O kakuro é um NP-completo.
Há dois tipos de simetrias matemáticas prontamente percebidas no kakuro. As restrições mínimas e máximas são duplas, como são valores faltantes e necessários.
Todas as combinações de somas podem ser representadas através de uma representação binária. Esta representação é útil para determinar os valores faltantes e necessários utilizando operações de lógica binária.