Kakuro

Da Wikipedia, l'enciclopedia libera.
Un semplice esempio di 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 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 tuttora pubblicano schemi quotidiani. In Italia è stato pubblicato su diversi quotidiani, tra cui il Corriere della Sera.

Gioco classico e terminologia[modifica | modifica sorgente]

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 sorgente]

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.

Possibili somme[modifica | modifica sorgente]

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

(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[modifica | modifica sorgente]

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 sorgente]

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 sorgente]

  1. ^ [1]
  2. ^ [2]
  3. ^ Dezaku Droid

Bibliografia[modifica | modifica sorgente]

Altri progetti[modifica | modifica sorgente]

matematica Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica