Graph Coloring Approach to Solving Sudoku with Oscillatory Neural Networks

Immaginate un mondo in cui i computer non si limitano a elaborare numeri come una super-calcolatrice, ma invece danzano seguendo un ritmo. Questo è il regno delle Reti Neurali Oscillanti (ONN), un tipo di calcolo "basato sulla fisica". Invece di utilizzare gli standard interruttori elettronici, queste reti utilizzano minuscole unità vibranti chiamate oscillatori. Pensateli come una stanza piena di metronomi o un coro di cantanti. In questo sistema, l'informazione non è memorizzata come un semplice bit "acceso" o "spento", ma nella tempistica delle vibrazioni, nota come fase. Se due oscillatori vibrano in perfetta sincronia, sono "in fase"; se vibrano in tempi opposti, sono "fuori fase".

L'obiettivo di queste reti è trovare uno stato di perfetta armonia, o il livello di energia più basso possibile, dove tutti gli oscillatori si assestano in un modello stabile. Questo approccio è particolarmente efficace per risolvere problemi di ottimizzazione combinatoria — enigmi in cui bisogna disporre un insieme di pezzi affinché si incastrino secondo regole specifiche senza conflitti. Potreste aver sentito parlare del problema del Coloring dei Grafi (Colorazione dei Grafi), che è come cercare di colorare una mappa in modo che due paesi vicini non condividano lo stesso colore. Se riuscite a far sì che una rete di oscillatori si assesti naturalmente in un modello in cui nessun "vicino" vibra allo stesso tempo, avete risolto un puzzle complesso usando le leggi della fisica piuttosto che la matematica a forza bruta. Questo è importante perché i computer tradizionali faticano con questi tipi di enigmi, spesso consumando enormi quantità di elettricità e tempo, mentre questi oscillatori danzanti potrebbero offrire un modo più veloce e meno dispendioso dal punto di vista energetico per pensare.

---

La Grande Sfida di Danza del Sudoku

Ora, parliamo di Sudoku. Conoscete già il gioco: una griglia di numeri dove bisogna riempire gli spazi vuoti in modo che ogni riga, colonna e quadratino contenga le cifre da 1 a 9 (o da 1 a 4 per la versione più piccola) senza ripetizioni. È un classico enigma logico, ma per un computer è un enorme mal di testa di tentativi ed errori.

I ricercatori di questo articolo, Filip Sabo e Aida Todri-Sanial dell'Università di Tecnologia di Eindhoven, hanno deciso di affrontare il Sudoku utilizzando la loro rete di "oscillatori danzanti". Hanno trattato la griglia del Sudoku come un problema di Coloring dei Grafi. Immaginate che ogni cella vuota della griglia del Sudoku sia un ballerino. La regola è semplice: due ballerini nella stessa riga, colonna o quadratino non possono indossare lo stesso "colore" (che, in questo caso, rappresenta un numero specifico come 1, 2 o 3).

Nel mondo degli oscillatori, "indossare un colore" significa vibrare a un ritmo specifico. Per un Sudoku 9x9, ci sono 9 possibili ritmi (fasi) tra cui gli oscillatori possono scegliere. Il compito della rete è far sì che tutti i ballerini scelgano un ritmo tale per cui nessun vicino stia eseguendo la stessa mossa di danza.

Il Problema con le Vecchie Mosse di Danza

Gli autori hanno esaminato come altri scienziati avessero provato a risolvere questo problema in precedenza. Un metodo prevedeva una complessa formula matematica che era molto costosa da calcolare, come cercare di coreografare una danza calcolando in anticipo ogni singolo movimento muscolare. Un altro metodo utilizzava un approccio più semplice, ma aveva un difetto fatale: permetteva ai ballerini di imbrogliare.

Immaginate uno scenario in cui due ballerini nella stessa riga decidono entrambi di eseguire la danza del "Numero 1". Nei vecchi modelli più semplici, la rete potrebbe pensare: "Ehi, stanno entrambi eseguendo il ritmo del 'Numero 1', che è un ritmo valido, quindi va bene così!". Ma nel Sudoku, questo è un disastro. Le regole dicono che non puoi avere due 1 nella stessa riga. I vecchi modelli non avevano un modo per espellere i ballerini da quello stato indesiderato se accidentalmente si fossero sincronizzati sul numero sbagliato.

Il Nuovo Termine di "Calcio" (Kick)

Per risolvere il problema, gli autori hanno inventato un modo più semplice per far danzare gli oscillatori e hanno aggiunto un meccanismo speciale di "calcio" (kick).

1. Il Ritmo Più Semplice: Invece di usare la complicata e costosa formula matematica, hanno usato un'equazione più pulita e diretta. Questo ha reso la simulazione al computer molto più veloce ed economica.
2. Il "Calcio" (Il Ingrediente Segreto): Questa è la parte più importante. Hanno aggiunto un termine speciale alle equazioni che agisce come un arbitro. Se due ballerini nella stessa riga, colonna o quadratino iniziano accidentalmente a vibrare alla stessa identica frequenza (il che significa che hanno scelto lo stesso numero), questo arbitro dà loro un "calcio" secco. Li spinge fuori da quello stato stabile e confortevole e li costringe a provare un ritmo diverso.

Questo "calcio" assicura che la rete si assesti solo quando il puzzle è effettivamente risolto correttamente. È come un insegnante che gira per l'aula: se due studenti sussurrano la stessa risposta sbagliata, l'insegnante dà un colpetto sulla spalla per farli smettere e riflettere di nuovo.

I Risultati: Una Performance Impeccabile

Il team ha testato il loro risolutore a oscillatori "da urlo" su migliaia di puzzle di Sudoku, che vanno da piccole griglie 4x4 alla versione standard 9x9. Hanno confrontato i loro risultati con altri due famosi risolutori: uno basato sulle Reti Neurali di Hopfield (HNN) e un altro standard di Reti Neurali Oscillanti.

Ecco cosa hanno scoperto:

• Per i puzzle 4x4: Il loro nuovo risolutore è stato praticamente perfetto. Ha risolto quasi il 100% dei puzzle correttamente, indipendentemente da quanti numeri mancavano. Gli altri risolutori hanno avuto difficoltà, con l'accuratezza che calava drasticamente man mano che i puzzle diventavano più difficili (con più numeri mancanti).
• Per i puzzle 9x9: I risultati sono stati comunque impressionanti, anche se non perfetti. Quando i puzzle avevano meno numeri mancanti (fino a circa il 25% di sconosciuti), il loro risolutore era impeccabile. Anche quando i puzzle diventavano più difficili (fino al 37,5% di sconosciuti), risolveva ancora più dell'80% di essi. Tuttavia, quando i puzzle diventavano molto difficili (più del 50% di numeri sconosciuti), il risolutore iniziava a inciampare, risolvendone circa il 50%. Gli altri risolutori fallivano molto prima, spesso non riuscendo a risolvere alcun puzzle correttamente una volta superati il 40-50% di numeri mancanti.

I ricercatori hanno anche osservato un "parametro d'ordine", che è essenzialmente un punteggio di quanto bene gli oscillatori siano riusciti a stabilizzarsi nei loro ritmi finali corretti. Hanno scoperto che ogni volta che il risolutore risolveva il puzzle correttamente, gli oscillatori erano molto ben organizzati (alto parametro d'ordine). Quando sbagliava, gli oscillatori erano caotici e non riuscivano a concordare su un modello stabile.

Cosa C'è Dopo?

Gli autori sono piuttosto fiduciosi che il loro termine di "calcio" sia la ragione del successo, ma ammettono che c'è ancora del lavoro da fare. Il loro modello aveva alcuni "pomelli" che dovevano regolare manualmente (parametri regolabili) per farlo funzionare, il che ha richiesto molto tempo per essere compreso. Hanno anche notato che per i puzzle 9x9 più difficili, gli oscillatori a volte avevano bisogno di più tempo per "danzare" e assestarsi, o forse il "calcio" non era abbastanza forte.

Suggeriscono che le versioni future di questo risolutore potrebbero provare a utilizzare oscillatori ancora più complessi, "non lineari" (ballerini con mosse più complicate) o a perfezionare la funzione di "calcio" per renderla ancora più efficace nel catturare chi infrange le regole. Ma per ora, hanno dimostato che aggiungendo una regola semplice e intelligente alla fisica di queste reti danzanti, possiamo risolvere i puzzle di Sudoku molto meglio di prima. È un piccolo passo, ma dimostra che a volte, tutto ciò di cui si ha bisogno per riparare un sistema rotto è una piccola spinta nella direzione giusta.