La domanda "come si genera un Sudoku" mi ha portato a scrivere questo semplice generatore casuale di Sudoku, che permette anche di giocare il puzzle direttamente all'interno del browser. Il generatore è scritto in TypeScript e l'interfaccia è sviluppata con React.
L'idea iniziale era quella di trovare un algoritmo matematico per creare una sequenza di numeri (81 per una griglia 9x9) che soddisfa 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 indivudare una soluzione soddisfacente.
Nell'attesa di raggiungere questo obiettivo, ho scritto il resto del gioco creando i Sudoku in maniera casuale attraverso un algoritmo di backtracking, che usa il seguente processo:
- La griglia viene inizializzata con 17 numeri casuali in posizioni altrettanto casuali, verificando all'aggiunta di ogni numero che la tavola soddisfi le regole del Sudoku;
- Il risultato di questo primo passaggio viene dato in input ad un algoritmo che cerca di risolvere il puzzle attraverso il backtracking, ovvero cercando la prima cella libera e provando ad inserire un numero al suo interno e verificando che la griglia risultante soddisfi le regole del Sudoku; se la griglia risultante non soddisfa le regole, il numero viene rimosso e viene provato un altro numero, e una volta esauriti tutti i numeri possibili il risolutore torna alla cella precedente e prova un altro numero; se la griglia risultante soddisfa le regole, il risolutore passa alla cella successiva e ripete il processo;
- Se il puzzle è risolvibile, il risultato di questo processo è un Sudoku completo, che può essere usato per giocare semplicemente nascondendo all'utente un numero di celle pari al livello di difficoltà desiderato;
- Se il puzzle non è risolvibile, o superato un numero massimo di tentativi, il puzzle viene scartato ed il processo viene ripetuto.
Questo approccio non è, naturalmente, né perfetto né particolarmente efficiente, ma è sufficiente per il caso medio ed è quello adottato da molti altri generatori di Sudoku, sebbene molti giochi analoghi abbiano un elenco di puzzle predefiniti caricati in memoria anziché generati in tempo reale.
Il gioco ha le seguenti feature:
- Selezione di una cella e impostazione del suo valore;
- Aggiunta e rimozione delle note per ciascuna cella;
- Gestione dello storico delle azioni, con la possibilità di annullare e ripetere ogni azione effettuata;
- Selezione del livello di difficoltà, che determina il numero di celle inizialmente visibili;
- Attivazione indizi, che mostrano per ciascuna cella i numeri che possono essere inseriti (rendendo il gioco più facile);
- Disattivazione della visualizzazione degli errori, rendendo il gioco più difficile;
- Un timer che conta il tempo impiegato per completare il puzzle;
Si tratta di un gioco molto semplice che è possibile giocare direttamente dal browser, sia da Desktop che da Mobile.
- Su desktop, si può selezionare una cella cliccandoci sopra, inserire le note digitando i numeri e impostare il numero premendo CTRL + il numero desiderato, oppure utilizzando i numeri sotto la griglia: con il tasto sinistro si inserisce il numero come nota, mentre con il tasto destro si imposta il numero; utilizzando CTRL+Z e CTRL+Y è possibile annullare o ripetere un'azione effettuata in precedenza;
- Su mobile, si può selezionare una cella facendoci tap sopra, inserire le note con i numeri presenti al fondo della schermata e inserire un numero tenendo premuto il numero desiderato; sono anche presenti due pulsanti per annullare e ripetere un'azione effettuata in precedenza.
Se vuoi giocare, puoi farlo andando su questa pagina.