domenica 15 gennaio 2012

I 17 indizi del sudoku

Qui si parla di sudoku, di una nuova scoperta che lo riguarda e di una rivista che mi è simpatica e che quindi non voglio sbugiardare esplicitamente.

Comunque, in una pagina di notizie brevi di scienza, la rivista riporta che:
Il Sudoku ha una soluzione unica se contiene almeno 17 indizi. Gli schemi con un numero inferiore di indizi numerici possono invece avere più di una soluzione. Lo studio, pubblicato sulla rivista online Arxiv.org, è basato sullo sviluppo di un nuovo algoritmo e ha richiesto 7,1 milioni di ore di calcolo all'Irish centre for high-end computing.
Ora, la prima frase è falsa, la seconda quasi e nella terza c'è una seria imprecisione.
La vera notizia è che un sudoku con meno di 17 “indizi” (cioè numeri dati nello schema iniziale) sicuramente non ha una soluzione univoca. 17 è il numero minimo che permette di costruirne uno con una soluzione unica, ma non è certo vero che se un sudoku contiene almeno 17 numeri o più la soluzione sia unica. Ce ne sono di ben più affollati con soluzioni multiple.
Infine, Arxiv.org non è una rivista: è, come suggerisce il nome, un archivio in cui si possono depositare articoli, spesso in attesa che vengano valutati da una rivista scientifica, in modo che siano immediatamente accessibili a tutti.

E, sì, certi matematici tra cui il sottoscritto non sono particolarmente interessati a risolvere i singoli sudoku ma sono incuriositi dai non pochi aspetti matematici del gioco, come le sue proprietà “estremali” (qual è il minimo numero di indizi che devono essere presenti perché la soluzione sia unica? qual è il numero massimo che ammette più soluzioni? e via dicendo) e combinatorie in generale.
Poi, il sudoku in generale ha il problema innato di essere un esempio, elementare ma bello, di ragionamento matematico nonostante siano presenti dei numeri.
In altre parole, una reazione naïf al sudoku può essere: «Ci sono dei numeri, quindi è matematica». E spero che ormai quasi tutti sappiano che questa implicazione non è vera.
Qualcuno un po' più smaliziato conclude: «Sì, ci sono dei numeri, ma se anziché 10 9 cifre fossero 10 9 lettere o 10 9 simboli arbitrari, il gioco funzionerebbe allo stesso modo. Quindi non è matematica». L'inizio è giusto, ma poi il ragionamento naufraga drammaticamente, perché si basa sulla stessa premessa sbagliata che “matematica = numeri”.
Invece la matematica è fatta di ragionamenti, di configurazioni, di escludere contraddizioni, di porre ipotesi e trarne deduzioni. E tutte queste cose, in maniera embrionale, sono presenti anche nel più semplice degli schemi di sudoku.

Per approfondire, Maurizio Codogno spiega più in dettaglio le novità matematiche sul sudoku e rinvia a un altro proprio articolo sui quadrati latini e gli altri antenati del sudoku; a questo riguardo si possono vedere anche i lucidi di un seminario di Peter J. Cameron su “Sudoku, Mathematics and Statistics”; mentre nell'arxiv si può trovare appunto l'articolo con la scoperta di cui parliamo, “There is no 16-Clue Sudoku: Solving the Sudoku Minimum Number of Clues Problem” di Gary McGuire et al.

7 commenti:

  1. un sudoku 9x9 con DIECI numeri o lettere o pittogrammi sarebbe interessante :-)

    RispondiElimina
  2. più seriamente, in italiano in questo caso si usa "indizi" per tradurre "clues"? A me non piaceva, quindi ho usato sempre "caselle già riempite"...

    RispondiElimina
  3. Anche a me suona strano: l'ho usato solo per coerenza con la notizia che riportavo. Uno dei motivi per cui /non/ mi suona in italiano è che in inglese "clue" si usa anche per le "definizioni" dei cruciverba (che poi spesso non sono definizioni vere e proprie ma enigmi vari), mentre in italiano non si direbbe mai.

    RispondiElimina
  4. Per Ragazzini, clue = indizio ma anche indicazione, suggerimento, aiuto, "dritta" (virgolette mie); per Zingarelli, indizio (tralascio il significato legato al diritto processuale) = Segno o situazione per mezzo dei quali è possibile ricostruire un fatto già accaduto o prevederne uno con fondatezza...
    3 †Segnale, traccia.
    4 (lett.) Indicazione, informazione.
    A me, tutto sommato, non pare improprio, anzi.

    RispondiElimina
  5. Grazie delle "dritte", Isa! In questi giorni, tra l'altro, nei "clue" mi imbatto anche perché sto traducendo un testo su tecniche di "forensics"; l'altro termine che va sempre tradotto con cautela, e qui doppiamente, è "evidence".

    RispondiElimina
  6. indicazioni in questo contesto mi piace più di indizi, ma potrebbe essere una cosa mia.

    RispondiElimina