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.

Un semplice esempio di Kakuro

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^[1].

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^[2]. 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^[3]