Kakuro
# Kakuro

Il Kakuro è un tipo di rompicapo logico molto diffuso, spesso considerato come una traslitterazione matematica del cruciverba. In origine, gli schemi di Kakuro erano problemi di programmazione lineare, e potevano essere risolti usando la tecnica delle matrici, per quanto fossero tipicamente risolti a mano. Il Kakuro appare con regolarità nella maggior parte, se non in tutte, le pubblicazioni enigmistiche negli Stati Uniti; Le Dell Magazines usano il nome Cross Sums, che in origine era loro esclusiva ma che adesso è usato comunemente da molti editori (nonostante siano ancora usati altri nomi, come Cross Addiction). In Giappone la sua popolarità è sconfinata, seconda solo al Sudoku tra le offerte del celebre editore Nikoli; Il gruppo editoriale Kappa ha ristampato il Kakuro Nikoli negli Stati Uniti, nella rivista GAMES Magazine con il nome Cross Sums. The Guardian in Gran Bretagna cominciò a pubblicare il rompicapo con il nome Kakuro nel settembre 2005; da allora molti altri giornali inglesi hanno ripreso l'idea e tuttora pubblicano schemi quotidiani. In Italia è stato pubblicato su diversi quotidiani, tra cui il Corriere della Sera. Il kakuro è conosciuto anche con i nomi Kakkuro e Tashizan Cross.

## Terminologia

Il classico Kakuro si gioca in una griglia composta da celle vuote e piene - "bianche" e "nere", rispettivamente - di solito 16×16 ma può avere altre dimensioni. Ad eccezione della prima riga in alto e della colonna più a sinistra - che sono completamente nere - la griglia, proprio come un cruciverba, è divisa in "soluzioni", linee ortogonali di celle bianche, dalle celle nere. Le stesse celle nere non sono interamente piene ma piuttosto contengono una barra diagonale dall'angolo in alto a sinistra a quello in basso a destra e un numero in entrambe le metà, così che ciascuna "soluzione" orizzontale ha un numero nella mezza cella nera alla sua immediata sinistra e ciascuna "soluzione" verticale ne ha uno nella mezza cella nera immediatamente sopra di essa. Questi numeri, seguendo la terminologia presa a prestito dal cruciverba, sono detti "definizioni".

L'obiettivo del rompicapo è di inserire una cifra da 1 a 9 in ogni cella bianca così che la somma dei numeri in ogni "soluzione" sia pari alla definizione associata ad essa e che nessuna cifra sia presente due volte nella stessa soluzione. È questo vincolo alla duplicazione che porta a creare i Kakuro con un'unica soluzione possibile.

Alcuni editori preferiscono pubblicare i loro Kakuro esattamente come dei cruciverba, senza etichettare le celle nere ma numerando le soluzioni, fornendo separatamente una lista di definizioni simile a quelle dei cruciverba (questo elimina le righe e le colonne che sono interamente nere). Si tratta semplicemente di una scelta grafica e non ha effetti sulla difficoltà di risoluzione (se non per la necessità di guardare fuori dalla griglia per risolvere il rompicapo).

Discutendo di tattiche e griglie, ci si riferisce tipicamente a una soluzione come a "(definizione, numerico)-in-(numero di celle nella soluzione, per esteso)", ad esempio "16-in-due" e "25-in-cinque". Fa eccezione "45-in-nove", per il quale è usato semplicemente "45", perché "-in-nove" è matematicamente implicito (una soluzione può essere lunga al massimo nove celle, e siccome nessuna cifra può essere duplicata deve contenere necessariamente tutte le cifre da 1 a 9). Stranamente, "3-in-due", "4-in-due", "43-in-otto" e "44-in-otto" non vengono abbreviate, nonostante "-in-due" e "-in-otto" siano anche in questi casi implicite.

## Tecniche di risoluzione

Sebbene sia ovviamente adottabile un sistema di risoluzione brute-force, un metodo migliore è la comprensione delle varie combinazioni che le soluzioni possono assumere per le differenti coppie di definizioni e lunghezze delle soluzioni. Quelle soluzioni con definizioni sufficientemente alte o basse per la loro lunghezza avranno minori possibili combinazioni da considerare, e comparandole con le soluzioni che le incrociano, la permutazione esatta - o parte di essa - può essere desunta. L'esempio più semplice è quando un 3-in-due incrocia un 4-in-due: il 3-in-due deve essere formato da '1' e '2' in qualunque ordine; il 4-in-due (siccome il '2' non può essere ripetuto) deve essere formato da '1' e '3' in qualunque ordine. Quindi, la loro intersezione non può essere che '1', l'unica cifra che hanno in comune.

Occasionalmente, può essere applicata una "tecnica a scatola", quando a prestarsi è la stessa geometria delle celle bianche vuote in una determinata fase della risoluzione: sommando le definizioni per una serie di soluzioni orizzontali (sottraendo il valore delle cifre eventualmente già trovate per quelle soluzioni) e sottraendo le definizioni per una serie di soluzioni verticali sovrapposte per la maggior parte, la differenza può rivelare il valore di parte di una soluzione, spesso di una singola cella.

È pratica comune segnare i valori possibili per una cella negli angoli della cella stessa fino a che tutti tranne uno siano dichiarati impossibili; per rompicapo particolarmente impegnativi, a volte i solutori annotano l'intera gamma delle possibilità per le celle nella speranza di trovare sufficienti vincoli nelle soluzioni incrociate da poter ridurre la gamma a un singolo valore.

Alcuni solutori usano dei fogli millimetrati per provare diverse combinazioni di cifre prima di scriverle nella griglia.

## Valori Unici

Ecco una lista delle coppie definizione/lunghezza con una sola combinazione possibile in un Kakuro; l'ordine delle cifre ovviamente non è determinato:

| Celle | Valore | Combinazione |
| - | - | - |
| 2 | 3 | 1+2 |
| | 4 | 1+3 |
| | 16 | 7+9 |
| | 17 | 8+9 |
| 3 | 6 | 1+2+3 |
| | 7 | 1+2+4 |
| | 23 | 6+8+9 |
| | 24 | 7+8+9 |
| 4 | 10 | 1+2+3+4 |
| | 11 | 1+2+3+5 |
| | 29 | 5+7+8+9 |
| | 30 | 6+7+8+9 |
| 5 | 15 | 1+2+3+4+5 |
| | 16 | 1+2+3+4+6 |
| | 34 | 4+6+7+8+9 |
| | 35 | 5+6+7+8+9 |
| 6 | 21 | 1+2+3+4+5+6 |
| | 22 | 1+2+3+4+5+7 |
| | 38 | 3+5+6+7+8+9 |
| | 39 | 4+5+6+7+8+9 |
| 7 | 28 | 1+2+3+4+5+6+7 |
| | 29 | 1+2+3+4+5+6+8 |
| | 41 | 2+4+5+6+7+8+9 |
| | 42 | 3+4+5+6+7+8+9 |
| 8 | 36 | 1+2+3+4+5+6+7+8 |
| | 37 | 1+2+3+4+5+6+7+9 |
| | 38 | 1+2+3+4+5+6+8+9 |
| | 39 | 1+2+3+4+5+7+8+9 |
| | 40 | 1+2+3+4+6+7+8+9 |
| | 41 | 1+2+3+5+6+7+8+9 |
| | 42 | 1+2+4+5+6+7+8+9 |
| | 43 | 1+3+4+5+6+7+8+9 |
| | 44 | 2+3+4+5+6+7+8+9 |
| 9 | 45 | 1+2+3+4+5+6+7+8+9 |

Ogni soluzione di otto o nove celle ha un'unica combinazione: le soluzioni di nove celle contengono sempre tutte le cifre da '1' a '9' e quindi la loro definizione sarà sempre "45"; le soluzioni di otto celle avranno come definizione necessariamente 45 meno il valore della cifra mancante. Kakuro Helper by Koalog è un assistente interattivo che mostra le combinazioni corrispondenti a una data somma e a un dato numero di celle (entrambi utili anche alla risoluzione dei rompicapo chiamati Killer Sudoku). I due link di cui sopra non contengono aiuti per risolvere Kakuro, ma puntano a giochi di Sudoku. Nella pratica può essere utile una lista abbreviata come quella che segue:

Valori minimi per ogni lunghezza

* 3 = 1, 2
* 6 = 1, 2, 3
* 10 = 1, 2, 3, 4
* 15 = 1, 2, 3, 4, 5
* 21 = 1, 2, 3, 4, 5, 6
* 28 = 1, 2, 3, 4, 5, 6, 7
* 36 = 1, 2, 3, 4, 5, 6, 7, 8
* 45 = 1, 2, 3, 4, 5, 6, 7, 8, 9

(i numeri triangolari)

Valore massimo per ogni lunghezza

* 17 = 9, 8
* 24 = 9, 8, 7
* 30 = 9, 8, 7, 6
* 35 = 9, 8, 7, 6, 5
* 39 = 9, 8, 7, 6, 5, 4
* 42 = 9, 8, 7, 6, 5, 4, 3
* 44 = 9, 8, 7, 6, 5, 4, 3, 2
* 45 = 9, 8, 7, 6, 5, 4, 3, 2, 1

Questa lista può essere costruita rapidamente e fornisce un valido aiuto mnemonico alle combinazioni addizionali univoche. Per esempio il valore minimo di una definizione per una soluzione di quattro celle è 10 = 1, 2, 3,4, il successivo valore più alto per questa lunghezza è 11 e l'unica combinazione che lo produce è 1, 2,3,5.

## Matematica del Kakuro

Il Kakuro è NP-completo.

Ci sono due tipi di simmetria matematica prontamente identificabili nel Kakuro. I vincoli minimo e massimo sono duplici, così come i valori mancanti e richiesti.

## Varianti

Una variante abbastanza comune del Kakuro è il suo logico successore, Cross Products (o Cross Multiplication), dove le definizioni sono il prodotto delle cifre nella soluzione anziché la somma. Un'altra variante è Arrow Numbers, dove le combinazioni per ogni definizione non possono essere ripetute all'interno della griglia. Una variante del Kakuro è anche il Dezaku. Il Dezaku indica direttamente sulle celle delle soluzioni che operazione bisogna applicare (somma o moltiplicazione). Il Dezaku non è conosciuto come le altre varianti esiste solamente qualche versione online e una versione per Android

