Kakuro
![](http://upload.wikimedia.org/wikipedia/commons/thumb/e/e0/Crosssum.gif/220px-Crosssum.gif)
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
[modifica | modifica wikitesto]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
[modifica | modifica wikitesto]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
[modifica | modifica wikitesto]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
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
[modifica | modifica wikitesto]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
[modifica | modifica wikitesto]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]
Note
[modifica | modifica wikitesto]- ^ Copia archiviata (PDF), su phil.uu.nl. URL consultato il 14 luglio 2006 (archiviato dall'url originale il 16 luglio 2006).
- ^ Copia archiviata (PDF), su focus.it. URL consultato il 3 luglio 2007 (archiviato dall'url originale il 28 settembre 2007).
- ^ Dezaku Droid
Bibliografia
[modifica | modifica wikitesto]- (EN) Guida alla combinazione dei numeri nel Kakuro, su strivinglife.com. URL consultato il 18 agosto 2007 (archiviato dall'url originale il 15 marzo 2008).
Altri progetti
[modifica | modifica wikitesto]Wikimedia Commons contiene immagini o altri file su Kakuro
Controllo di autorità | J9U (EN, HE) 987007554216005171 |
---|