Kakuro
Da Wikipedia, l'enciclopedia libera.
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 comunemenente 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 tutt'ora pubblicano schemi quotidiani. In Italia, tra gli altri, il Corriere della Sera pubblica ogni giorno uno schema da risolvere.
Indice |
[modifica] Gioco classico e 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 cella nera alla sua immediata sinistra e ciascuna "soluzione" verticale ne ha uno nella 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" 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", "5-in-due", "43-in-otto" e "44-in-otto" non vengono abbreviate, nonostante "-in-due" e "-in-otto" siano anche in questi casi implicite.
[modifica] 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 è quanto 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 differenze 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 rompicampo 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.
[modifica] Attraverso la tabella risolutiva di fremsoft
Sul principio delle possibili soluzioni, la tabella risolutiva di fremsoft, aiuta la risoluzione di qualunque schema di kakuro senza l'utilizzo della gomma, al primo colpo. Sul sito sudoku.fremsoft.it è possibile scaricare una versione della tabella risolutiva e viene spiegato con un eloquente esempio come utilizzarla affinché si possa trasformare il rompicapo in un passatempo. Le regole per scremare le possibili soluzioni sono semplici ed intuitive. È disponibile anche una versione pocket (A5 = 210mm x 145mm) molto pratica per chi viaggia in treno.
Il bello della tabella risolutiva di fremsoft è che non viene risolto lo schema in maniera automatica dal calcolatore, ma rimane comunque un passatempo per chi deve risolvere l'enigma.
[modifica] Possibili somme
Ecco una lista di alcune delle coppie definizione/lunghezza con una sola combinazione possibile in un Kakuro; l'ordine delle cifre ovviamente non è determinato:
3-in-due: 1, 2
4-in-due: 1, 3
16-in-due: 7, 9
17-in-due: 8, 9
6-in-tre: 1, 2, 3
7-in-tre: 1, 2, 4
23-in-tre: 6, 8, 9
24-in-tre: 7, 8, 9
10-in-quattro: 1, 2, 3, 4
11-in-quattro: 1, 2, 3, 5
29-in-quattro: 5, 7, 8, 9
30-in-quattro: 6, 7, 8, 9
15-in-cinque: 1, 2, 3, 4, 5
16-in-cinque: 1, 2, 3, 4, 6
34-in-cinque: 4, 6, 7, 8, 9
35-in-cinque: 5, 6, 7, 8, 9
21-in-sei: 1, 2, 3, 4, 5, 6
22-in-sei: 1, 2, 3, 4, 5, 7
38-in-sei: 3, 5, 6, 7, 8, 9
39-in-sei: 4, 5, 6, 7, 8, 9
41-in-sette: 2, 4, 5, 6, 7, 8, 9
42-in-sette: 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 Combinations contiene una tavola completa delle combinazioni mentre 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).
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ù altro per questa lunghezza è 11 e l'unica combinazione che lo produce è 1, 2 ,3 ,5.
[modifica] 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.
[modifica] 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].
