La domanda "come si genera un Sudoku?" mi ha portato a scrivere questo semplice generatore casuale di Sudoku, che permette anche di risolvere il puzzle direttamente nel browser. Il generatore è scritto in TypeScript e l'interfaccia è sviluppata con React.
L'idea iniziale era trovare un algoritmo matematico per creare una sequenza di numeri (81 per una griglia 9x9) che soddisfi le regole del Sudoku (i numeri non sono mai ripetuti all'interno di una riga, una colonna o un quadrante) ma, nonostante diversi tentativi e la lettura di diversi articoli sul tema, non sono riuscito a individuare una soluzione soddisfacente.
Il gioco genera gli schemi in tempo reale attraverso un algoritmo di backtracking, con il seguente processo:
- Il generatore crea una griglia completa valida;
- Il risolutore usa il backtracking: sceglie la cella libera con meno candidati, prova un numero consentito e prosegue. Se non trova una soluzione, torna sui propri passi e tenta un'altra scelta;
- A partire dalla griglia completa, il generatore prova a rimuovere un indizio alla volta, in ordine casuale. Ogni rimozione viene mantenuta soltanto se il risolutore conferma che il puzzle ha una sola soluzione;
- Il livello scelto determina la quantità desiderata di indizi. Lo schema può conservarne di più per garantire una soluzione unica, anche quando la verifica raggiunge il limite di ricerca previsto.
La generazione avviene in un Web Worker, per lasciare l'interfaccia reattiva. I livelli regolano la quantità di indizi, non le tecniche logiche necessarie a risolvere il puzzle.
Il gioco offre queste funzionalità:
- Griglie 4×4, 9×9 e 16×16; in queste ultime le lettere A–G rappresentano i valori da 10 a 16;
- Selezione di una cella e impostazione del suo valore;
- Aggiunta e rimozione delle note per ciascuna cella tramite la modalità note;
- Gestione dello storico di numeri e note, con la possibilità di annullare e ripetere ogni azione effettuata;
- Quattro livelli: facile, medio, difficile ed esperto;
- Visualizzazione facoltativa dei candidati, che evidenzia i numeri consentiti nella cella selezionata;
- Evidenziazione facoltativa degli errori;
- Un timer che conta il tempo impiegato per completare il puzzle.
Il gioco si può giocare direttamente dal browser, sia da desktop che da mobile.
- Su desktop, si può selezionare una cella cliccandoci sopra o spostandosi con le frecce, quindi inserire un numero dalla tastiera o dal tastierino a schermo. Il pulsante Modalità note, o il tasto N, attiva e disattiva l'inserimento delle note; Maiusc + numero permette di inserire una nota direttamente. Canc/Backspace cancella il contenuto della cella. Ctrl/⌘ Z annulla, mentre Ctrl/⌘ Maiusc Z o Ctrl Y ripete un'azione;
- Su mobile, si può selezionare una cella toccandola e inserire un numero dal tastierino a schermo. Attivando Modalità note, gli stessi pulsanti aggiungono o rimuovono le note. Sono presenti anche i pulsanti per cancellare, annullare e ripetere.
Le preferenze per errori e candidati si possono modificare senza perdere la partita; cambiare formato o livello genera invece un nuovo schema. La partita resta in memoria fino al ricaricamento della pagina.
Il gioco è disponibile a questo indirizzo.