Sudoku minimali e massimali
Immagino che sappiate quasi tutti cos’è un sudoku, almeno se in questo millennio siete vissuti sul pianeta Terra. Se poi siete assidui lettori di questo blog, vi ricordate sicuramente che due anni fa ho anche spiegato cos’è il sudoku dal punto di vista matematico: la parte matematica non sono certo i numeri dello schema, che possono essere sostituiti tranquillamente da lettere, ideogrammi o colori, quanto piuttosto la struttura dello schema completo. I matematici possono divertirsi a risolvere i sudoku esattamente come chi matematico non è: ma i neuroni di un Vero Matematico si mettono subito in moto per immaginare qualche proprietà massimale o minimale dei giochi stessi. Detto in altre parole, qual è il numero minimo di caselle che devono essere fornite per essere certi di risolvere il gioco? Ricordo che per “risolvere un sudoku” occorre che la soluzione sia unica; inoltre, a differenza degli schemi che si vedono su giornali e riviste, il matematico non si cura della simmetria dello schema di partenza.
Credo che nessuno di voi farà fatica a dimostrare che un sudoku con solo sette caselle riempite non potrà mai essere risolubile. Provate a pensarci un momento, prima di continuare a leggere… Occhei, ci siete arrivati? Anche supponendo che le sette caselle contengano tutti numeri diversi è chiaro che ci saranno due numeri, chiamiamoli a e b, che non appaiono nello schema. Bene, ovviamente non potremmo mai distinguere uno schema completato in un certo modo da quello che otteniamo scambiando a e b, giusto? Ecco, abbiamo dimostrato che la soluzione non può essere unica.
Certo che 7 è soltanto un limite inferiore, e anche piuttosto rozzo: fino alla fine del 2011 infatti si sapeva solo che esistono degli schemi con 17 caselle riempite che avevano una soluzione unica, ma non si riusciva a scendere sotto questo limite. Per la cronaca, c’è un tizio, tal Gordon Royle della University of Western Australia, che sta catalogando tutti gli schemi di sudoku da 17 caselle. Mentre sto scrivendo ne ha 49151: se qualcuno trova troppo semplici gli schemi usuali può provare a divertirsi con quelli. Io non ci tento nemmeno.
Ordunque: a Capodanno, invece che smaltire il cenone, Gary McGuire dello University College di Dublino ha pubblicato su arXiv un articolo, scritto insieme a Bastian Tugemann e Gilles Civario, che dimostra che effettivamente 17 è il limite cercato: insomma, un qualunque schema di sudoku con sedici o meno caselle riempite ha più di una soluzione (oppure, per i pignoli – e si sa che i matematici sono pignoli – non ha nessuna soluzione). La scoperta è stata resa nota da Nature: qui in Italia ne ha appena scritto Stefano Pisani, anche se io non ho ancora aperto il suo articolo perché altrimenti rischiavo non solo di scrivere le stesse cose ma anche di scriverle nello stesso modo.
Come ha fatto McGuire a dimostrare che sedici non bastano? Con il sistema più semplice possibile: provando tutte le combinazioni possibili, e vedendo che nessuna di esse portava a una soluzione univoca. Beh, non proprio così ma quasi: l’approccio brutale a forza bruta (permettetemi il pessimo gioco di parole) non sarebbe stato computazionalmente possibile, data l’esplosione più che esponenziale del numero di combinazioni. L’approccio è stato pertanto leggermente diverso, lavorando alla rovescia. Partendo da ciascuna griglia sudoku completa essenzialmente diversa – ruotarla, specchiarla o fare una permutazione dei numeri lascia la stessa griglia, in fin dei conti; il numero di queste griglie è “solo” 5.472.730.538 – il gruppo di lavoro ha cercato tutti gli schemi che portano a una soluzione unica, e verificato che tali schemi avevano almeno diciassette caselle riempite. Per fare questo, hanno inizialmente cercato un numero sufficientemente ampio dei cosiddetti insiemi inevitabili (unavoidable sets), gruppi di caselle tali che almeno una di esse deve essere riempita per assicurare l’unicità della soluzione. Il secondo passo è stato enumerare tutti gli insiemi di 16 caselle che hanno almeno una casella in comune con ciascuno degli insiemi inevitabili; questi nella teoria dei grafi si chiamano hitting sets. La logica del secondo passo dovrebbe essere chiara: se non do valori a nessuna delle caselle degli insiemi inevitabili, allora per definizione avrò soluzioni multiple. Infine per ciascuno degli hitting set trovati si è controllato se effettivamente avrebbe portato o no a una soluzione. Essendo la risposta stata “no”, il problema è risolto.
Peccato che il problema degli hitting set è noto per essere NP-hard, cioè uno dei più complicati esistenti dal punto di vista computazionale (ho parlato qui di problemi P e NP; vi basti sapere che nei problemi NP tutti gli algoritmi noti crescono esponenzialmente con la dimensione dei dati, e i problemi NP hard sono tutti equivalenti, nel senso che se mai si trovasse un algoritmo polinomiale per uno se ne potrebbe ricavare uno polinomiale per tutti gli altri). McGuire e colleghi sono però riusciti a trovare un algoritmo “non troppo esponenziale”, se mi passate il termine; l’algoritmo cresce sì esponenzialmente ma è sufficientemente veloce per essere applicato ai dati del sudoku e avere richiesto “solo” 7 milioni di ore di CPU del cluster di computer dello University College. L’algoritmo è tra l’altro la parte più interessante di tutto il progetto, perché a detta degli autori può essere riciclato nei test del software e soprattutto nella bioinformatica (le sequenze geniche che sono tanto di moda in questi anni…), per la serie “la matematica inutile non è mai davvero inutile”.
Un sudoku con 77 caselle riempite eppure non risolubile
Leave a comment