Incuriosito dalla notizia “La matematica svela i segreti del Sudoku”, apparsa recentemente in rete e anche sulla pagina di Maddmaths, ho provveduto a leggere i due articoli citati, ossia [1] “A Pencil-and-Paper Algorithm for Solving Sudoku Puzzles” di J.F. Crook  e [2]“Sudoku Squares and Chromatic Polynomials” di A.M. Herzberg e M.R. Murty .

L’articolo di Crook promette bene, nell’introduzione, lì dove dichiara di “sviluppare un algoritmo per la risoluzione di ogni Sudoku con carta e matita, specialmente quelli classificati come diabolici”. In realtà, a parte una formalizzazione di termini ampiamente noti tra i giocatori di Sudoku, l’algoritmo proposto da Crook è ben lungi dall’essere un algoritmo efficiente nel risolvere gli schemi. Visto con gli occhi dell’appassionato di Sudoku, l’algoritmo dice una cosa ovvia e già nota: “Usa alcune tecniche logiche per individuare i numeri da mettere nelle caselle e, quando ciò non è più possibile, vai avanti a tentativi, con la tecnica del ‘trial and error’”. Inoltre, l’algoritmo proposto da Crook sembra coincidere con alcuni accorgimenti logici assolutamente noti ai solutori. Per esempio ci sono già vari siti che riportano lodevolmente tutte le tecniche logiche finora note, tipo il sito [4] SudokuWiki.org, Strategies for Number Puzzles of all kinds, decisamente più completo, che le implementa anche in un sofisticato software che segnala, ad ogni passo, la tecnica utilizzata per l’individuazione di un numero in una casella o per l’eliminazione di alcuni candidati. Le tecniche sono divise in cinque gruppi, per un totale di 37 teniche, in base alla loro difficoltà di applicazione. Per esempio il primo gruppo riunisce le 7 tecniche più semplici; le tecniche del quarto, dette infernali, vanno dal 22 al 35; infine il solutore si affida a tecniche a tentativi (“trial and error”).. Tutte le tecniche del primo e del secondo gruppo sono assolutamente all’altezza dei solutori più o meno abili, mentre poche diaboliche sono utilizzabili manualmente. In seguito le tecniche diventano estremamente complesse e, se si escludono appassionati particolarmente allenati, esse possono essere poco utilizzate e possono servire quasi esclusivamente per un solutore informatico. Il sito riporta anche un esempio di schema non risolubile con nessuna delle tecniche elencate (lo schema viene denominato “esempio di Bowman”), che deve essere forzatamente e ripetutamente risolto con il metodo del “trial and error”.

Crook, invece, si ferma a schemi (i famosi “diabolici”) che sono, sulla base delle mie pur limitate conoscenze e capacità risolutive del Sudoku, sempre risolubili con le tecniche più elementari riportate dal sito sopra citato o anche in [3] SudoCue – Sudoku Solving Guide, cioè possono essere risolte senza alcuna necessità di tentativi, eventualmente tramite l’indicazione in ogni casella dei candidati, cioè di tutti i numeri che potrebbero essere inseriti nella casella. Come scrivo nel mio articolo [5], definendo schemi a scelta singola (SSS) quelli risolubili con le sole tecniche logiche e schemi a scelta multipla (SSM) quelli che necessitano di tentativi, lo scopo della ricerca di nuove tecniche logiche dovrebbe essere poter rendere di tipo SSS tutti i Sudoku, compreso il famigerato “esempio di Bowman”.

Insomma è difficile concordare con il Daily Mail [6] che dichiara entusiasticamente “si pensa che l’algoritmo di Crook sia la prima dimostrazione di come risolvere il rompicapo”. A mio parere questo non è un teorema, è una tautologia. E’ evidente che, lì dove la logica non arriva più, occorre passare al “trial and error”. Non serve un articolo di matematica per dimostrarlo. Prova ne sia, ad esempio, che un solutore mediamente esperto riesca ad eliminare molti più candidati di quanto ne riesca a fare Crook con il suo algoritmo, nello schema da lui indicato con “MEPHAM D”. Il software del sito [4], col quale  ho provato a risolvere tale schema, non va oltre le più semplici tecniche diaboliche, pur sempre applicabili manualmente da un giocatore allenato. Su questo sembra concordare anche il Prof. Murty, altro matematico esperto di Sudoku, in un’intervista [7]: “Ciò che Crook ha fatto […] è più o meno di aver sistematizzato ciò che la mente comune fa e di aver messo questo in una specie di algoritmo informatico  – che è una procedura step-by-step”.

E’ sufficiente aggirarsi per qualche forum di discussione di appassionati del Sudoku per verificare che la “scoperta” fatta da Crook nel migliore dei casi ha lasciato freddi, nel peggiore dei casi ha ingenerato reazioni irritate e infastidite. Nell’articolo di Crook viene anche citato uno schema che, secondo l’autore, ammette 2 soluzioni. Esso venne proposto nella finale del campionato del mondo di Sudoku nel 2007, a Praga. L’autore indica anche quali siano tali soluzioni, individuate tramite il suo algoritmo. In realtà la duplice soluzione si ha nel momento in cui si operi non con il classico Sudoku, ma con il cosiddetto Jigsaw Sudoku, le cui regole possono essere trovate su [4], che pone ulteriori vincoli sulla scelta dei numeri. Lo studio dello schema proposto, senza ulteriori vincoli, porta in realtà a ben 30 soluzioni distinte. Ciò dimostra, a maggior ragione, una certa inadeguatezza del metodo di Crook, soprattutto nel caso di non unicità della soluzione.

Il fatto che mi lascia comunque più perplesso è che, scondo me, con il suo articolo, Crook ha svolto un pessimo servizio alla comunità matematica, pur nel lodevole intento di formalizzare un algoritmo ritenuto “vincente”. L’immagine che passa tra la gente comune è ben sintetizzata da un commento di un giocatore [8]: “[Crook] sa solo come descrivere semplici meccanismi mentali logici in modo complicato”.

Di ben altro calibro, a mio parere, l’articolo [2] di A.M. Herzberg e del già citato M.R. Murty, i quali, con tecniche basate sulla teoria dei grafi, mostrano un risultato che è stato molto apprezzato dalla comunità dei giocatori di Sudoku: “Un Sudoku, per avere una sola soluzione, deve presentare nello schema iniziale del gioco almeno 8 dei 9 numeri”. Questo risultato, come altri (si pensi alla prova di B. Felgenhauer e F. Jarvis sul numero di Sudoku 9×9 [9], o al lavoro incessante di Gordon Royle [10] per verificare, con tecniche di combinatoria computazionale, la congettura secondo la quale non esistono schemi con meno di 17 dati iniziali che portino ad un’unica soluzione), siano essi in forma di teoremi o di congetture, vengono ben accolti, discussi e rielaborati anche dai non matematici e sono senz’altro un valido veicolo della cultura logica e matematica all’interno di gruppi che, altrimenti, probabilmente non parlerebbero mai di matematica.

di Alberto Bersani
Dipartimento Metodi e Modelli Matematici – Università “La Sapienza”, Roma
bersani@dmmm.uniroma1.it

BIBLIOGRAFIA E SITOGRAFIA

[1] J.F. Crook, “A Pencil-and-Paper Algorithm for Solving Sudoku Puzzles”, Notices of the AMS, vol. 56, n. 4, 460-468;
[2] A.M. Herzberg e M.R. Murty, “Sudoku Squares and Chromatic Polynomials”, Notices of the AMS, vol. 54, n. 6, pp. 708-717;
[3] SudoCue – Sudoku Solving Guide ;
[4] SudokuWiki.org –  Strategies for Number Puzzles of all kinds ;
[5] A.M. Bersani, “Dal Treize al Sudoku: tre secoli di permutazioni”, Archimede, 1/2007, pp. 18-25;
[6] MailOnline – http://www.dailymail.co.uk/news/article-1163925/Puzzling-behaviour-Maths-professor-finds-formula-solve-ANY-Sudoku.html ;
[7] thestar.com – ” Academic finally cracks the Sudoku code”;
[8] Famewatcher ;
[9] B. Felgenhauer, F. Jarvis – Enumerating possible Sudoku grids ;
[10] Minimum Sudoku .