Il teorema del Sudoku

chotda-sudoku.jpgIl Sudoku è un gioco di logica che si presenta come una griglia di nove righe orizzontali e nove colonne verticali suddivise in nove sottogriglie, chiamate regioni, costituite da 3×3 celle. Scopo del gioco è quello di riempire le caselle vuote con numeri da 1 a 9, in modo tale che in ogni riga, colonna e sottogriglia siano presenti tutte le cifre da 1 a 9 senza ripetizioni. Questo popolare rompicapo, per quanto semplice possa apparire, non è per niente facile: si tratta di un problema matematico di grande complessità.

Ai livelli di difficoltà più elevata, le domande logiche a cui bisogna rispondere sono tutt’altro che banali.

Il Sudoku non è un "cruciverba di numeri", né ha niente a che vedere con l’aritmetica: non si deve fare alcun tipo di addizione, sottrazione, moltiplicazione o divisione.

Le questioni più discusse sul Sudoku sono le seguenti: una combinazione di numeri assegnata in partenza ammette effettivamente una soluzione? C’è una tecnica sistematica che permette di risolvere ogni Sudoku? Quando la soluzione è unica? Quanti sono i Sudoku che ammettono una sola soluzione?

La qualità di un Sudoku, infatti, è data principalmente da questa caratteristica: la soluzione deve essere univoca. Ma allora qual è il numero minimo di numeri assegnati in partenza che rendono un Sudoku univoco? La risposta a questa domanda è tutt’altro che semplice. Mentre il numero massimo di “indizi” di partenza non conta, se ce ne sono troppi il gioco diventa banale e si riduce a una procedura meccanica di riempimento senza che occorra alcun procedimento logico. La quantità minima di numeri di partenza è invece importante, perché sotto una certa soglia il rompicapo diventa impossibile da risolvere, perché ammette più di una soluzione e ciò lo rende esteticamente poco interessante.

Nel numero di giugno 2007 del notiziario della Società Americana di Matematici, Agnes Herzberg e Ram Murty della Queens University (Canada) hanno pubblicato uno studio su queste complesse questioni. Il paper si chiama “Sudoku e polinomi cromatici" [http://www.ams.org/notices/200706/tx070600708p.pdf]. I due autori sono riusciti a dimostrare che un Sudoku, per avere una sola soluzione, deve presentare all’inizio del gioco almeno 8 dei 9 numeri. Se ne sono presenti solo 7, allora il puzzle ha almeno due soluzioni.

La dimostrazione di ciò si basa sulla teoria matematica dei grafi. Un grafo è uno schema creato da una serie di nodi connessi da un segmento. Nel contesto del Sudoku, le 81 caselle del puzzle possono essere pensate come gli 81 nodi di un grafo e due nodi sono considerati connessi da un segmento quando si trovano su una stessa riga, colonna o diagonale. Se si rappresenta ciascuno numero (da 1 a 9) con un colore diverso – poiché per regola nel Sudoku non possono esserci numeri uguali sulla stessa riga, colonna o diagonale – il grafo non può presentare connessioni tra nodi dello stesso colore.

Nel linguaggio di questa teoria, un grafo in cui non ci sono connessioni tra nodi dello stesso colore si dice “colorato completo”. Quello che i solutori di Sudoku fanno a ogni partita è quindi cercare di estendere un grafo colorato parziale in uno completo.

Con questa analogia, i due autori hanno provato che il numero di modi di estendere un grafo parziale in uno completo è dato da un polinomio. Se il valore del polinomio è zero per un dato Sudoku, allora il rompicapo non ha soluzione. Se il polinomio è 1, la soluzione è una sola, e così via. Infine gli autori hanno calcolato che dovrebbero essere possibili circa 5,5 miliardi di Sudoku diversi. Chissà se qualcuno riuscirà a risolverli tutti…

Per divertirti con i nostri sudoku vai alla sezione dei sudoku.

Commenti

commenti

Ci sono 14 commenti su questo articolo:

  1. invece credo che sia giusto “diagonale”. in effetti cosi si gioco di solito .ma forse alcuni hanno cambiato le regole per comodita :-)

  2. Secondo me nell’articolo c’ e’ un errore’ che vuol dire che non possono esserci gli stessi numeri sulla diagonale???

    Saluti

  3. Il paper è stato tradotto. Siamo in attesa di ricevere l’autorizzazione alla pubblicazione

  4. Alle celle binarie (cb) corrispondono per dualità le cifre bilocate – ossia due sole celle ammesse in una
    9_pla – (CB).
    Tali elementi sono in grado di costruire Strutture globali orientate.
    Mentre le prime risiedono nel piano dello schema, le seconde sono stratificate in un “Big Mac” di nove strati.
    Sono affascinanti i sottoinsiemi orientati entro una 9_pla che contengono simultaneamente q cb e q CB; is n’t it?

  5. Ho scoperto (!?!) che gli Autori propongono l’applicazione del Principio del Terzo Escluso (noto in matematica come dimostrazione per assurdo) cui è stato dato il nome di Almost Locked Sets.
    Si vuole che il corno del dilemma che conduce all’esclusione sia facilmente percorribile.
    A localizzare nello schema il dilemma idoneo giova conoscere al meglio i criteri di deduzione.

  6. Con la mia consorte abbiamo scoperto alcuni teoremi, che io,più propriamente, chiamo “criteri di deduzione”.
    Recentemente ho studiato le “celle binarie” (che ammettono DUE cifre) da cui si trae la nozione di “rete globale orientata”, che ammette DUE insiemi di allocazioni di cifre a celle.
    Tale strumento da luogo a diversi criteri di deduzione, che stiamo scoprendo.
    Ma noi siamo solutori!
    Mi chiedo se gli Autori conoscono e impiegano tali criteri… e molti altri.
    Forse scopro l’acqua calda?

  7. A me interessa un’altra questione: quando un sudoku è impossibile (cioè non ammette soluzioni)?. Lo chiedo perché ai miei figli è stato regalato un gioco in scatola (Sudoku, appunto) che permette di inventare e risolvere sudoku: ma molti, anzi quasi tutti, i sudoku da noi inventati sono impossibili (cioè ad un certo punto non è più possibile inserire numeri rispettando le limitazioni del gioco). Insomma, come si fa ad inventare un sudoku che ammetta una soluzione?

  8. Io ho fatto un programmino in DBASE III + (fatto molti anni fa) e mi risolve in automatico la guasi totalità dei SUDOKU che trovo nei giornali. Per fare un esempio il programma mi risolve il gioco in circa 1 minuto.

  9. Invece di risolvere il difficile problema descritto nell’articolo:”stabilire se uno specifico sudoku ha soluzione unica”, ho tentato di di capire se, utilizzando il risolutore Excel (programmazione matematica), riuscivo a trovare la soluzione dei problemi proposti dai giornali. In pratica si riesce bene ad imporre variabili intere, ad esprimere i limiti (bounds 1-9) e anche il vincolo delle celle preimpostate (lower=upper bound). Non ho avuto però successo nel tentativo di esplicitare il vincolo che tutti i valori debbano essere diversi. Ora leggo che la “Constraint Programming” permette di esprimere vincoli del tipo “All different”. Pensate che questo approccio, molto utile per problemi combinatori tipo “commesso viaggiatore”, possa essere utile per risolvere i Sudoku?

  10. Purtroppo non conosco l’inglese, qualcuno può tradurlo?
    E’ nell’interesse della comunità:
    Grazie.

  11. he rabbia non conoscere l’inglese!
    vorrei poter leggere tutto l’articolo.
    Ho sempre pensato che sarebbe bello dimostrare “teoremi” sul sudoku o altri giochi.
    Ma qualcuno sa dirmi con quale criterio il sudoku è definito FACILE, DIFFICILE,… a presto airam

  12. Wow veramente interessante come articolo!! non pensavo si potesse collegare il sudoku alla teoria dei grafi