Il Sudoku usa numeri, ma non richiede aritmetica.
Le cifre da 1 a 9 funzionano soprattutto come nove simboli distinti.
L'interesse matematico nasce dalla struttura:
- combinatoria;
- quadrati latini;
- soddisfacimento di vincoli;
- Exact Cover;
- simmetrie;
- ricerca;
- conteggio delle soluzioni.
Sudoku e quadrati latini
Un quadrato latino di ordine 9 dispone nove simboli in modo che ciascuno compaia esattamente una volta in ogni riga e colonna.
Una griglia Sudoku classica completa rispetta queste condizioni più il vincolo dei nove blocchi 3×3.
Quindi:
Ogni Sudoku classico completo è un quadrato latino con vincoli regionali aggiuntivi.
Ma non ogni quadrato latino è un Sudoku.
Questa è una relazione matematica reale, non l'affermazione storica che il Sudoku moderno sia stato direttamente inventato a partire dai lavori sui quadrati latini.
Sudoku come problema di vincoli
Ogni casella può essere vista come una variabile.
Il suo dominio iniziale può essere:
{1,2,3,4,5,6,7,8,9}
Indizi e valori già risolti eliminano possibilità.
Per il giocatore questo è aggiornamento dei candidati.
Per un modello CSP è propagazione di vincoli.
Sudoku come Exact Cover
Il Sudoku può essere formulato anche come problema di Exact Cover.
Una soluzione deve soddisfare esattamente:
- una cifra per casella;
- ogni cifra una volta per riga;
- ogni cifra una volta per colonna;
- ogni cifra una volta per blocco.
Ogni possibile inserimento rNcM = d soddisfa una combinazione di questi vincoli.
Una soluzione completa corrisponde a un insieme di inserimenti che copre ogni vincolo esattamente una volta.
Ricerca e backtracking
Un solver completo può usare ricerca ricorsiva:
- scegliere una casella non risolta;
- provare un candidato;
- propagare i vincoli;
- tornare indietro se compare una contraddizione;
- continuare fino a trovare una o più soluzioni.
Questo tipo di solver risponde a domande di validità e unicità.
Non è necessariamente il modello migliore per spiegare il percorso umano.
Quante griglie Sudoku complete esistono?
Il numero di griglie Sudoku classiche 9×9 complete è:
6 670 903 752 021 072 936 960
circa:
6,671 × 10²¹
Griglie essenzialmente diverse
Molte griglie possono essere trasformate l'una nell'altra preservando la validità mediante:
- permutazione delle cifre;
- permutazione di righe dentro una banda;
- permutazione di colonne dentro una pila;
- scambio di bande o pile;
- trasposizione;
- combinazioni di queste simmetrie.
Raggruppando le griglie sotto le simmetrie standard rimangono:
5 472 730 538
griglie essenzialmente diverse.
Una griglia completa non equivale a un puzzle
Da una stessa soluzione completa si possono scegliere molti insiemi di indizi.
Alcuni:
- non sono unici;
- sono minimali;
- contengono indizi ridondanti;
- producono percorsi e difficoltà diverse.
Quindi il numero di griglie complete non è il numero di puzzle pubblicabili.
Simmetria degli indizi
La simmetria della posizione degli indizi è spesso una preferenza estetica o editoriale.
Non è una regola del Sudoku classico.
Numero minimo di indizi
La domanda:
Qual è il numero minimo di indizi che può determinare una soluzione unica?
ha risposta:
17
Il risultato descrive un limite matematico, non la qualità o la difficoltà di un puzzle particolare.
Difficoltà come modello umano
Un solver completo può risolvere rapidamente un puzzle che una persona trova difficile.
Per questo un rating umano dovrebbe considerare:
- tecniche necessarie;
- quantità di passaggi;
- dipendenze;
- sforzo di riconoscimento;
- dati dei giocatori.
Perché servono ruoli separati
Solver completo
Validità e unicità.
Solver human-style
Passaggi spiegabili e dati per il rating.
Generatore
Costruzione, verifica, analisi e selezione.
Separare questi ruoli rende più chiaro il sistema.
FAQ
Il Sudoku usa matematica?
Può essere studiato matematicamente, ma per giocare non serve aritmetica.
Ogni Sudoku è un quadrato latino?
Ogni griglia Sudoku classica completamente risolta lo è, con vincoli aggiuntivi sui blocchi.
Quante griglie complete esistono?
6 670 903 752 021 072 936 960.
Le griglie essenzialmente diverse sono molte meno?
Sì: 5 472 730 538 sotto le simmetrie standard.
Cosa leggere dopo?
Leggi Come vengono generati i Sudoku e Come viene valutata la difficoltà.