In questa pagina
Il Sudoku usa cifre, ma la sua matematica non è aritmetica. È un problema di vincoli, combinatoria e struttura: nove simboli devono essere distribuiti in 81 celle rispettando unità sovrapposte.
Perché i numeri del Sudoku sono in realtà simboli
Non sommi, moltiplichi o confronti grandezze. Sostituendo 1–9 con nove lettere distinte, la logica resterebbe identica. Le cifre sono etichette comode.
Sudoku come quadrato latino vincolato
Un quadrato latino 9×9 contiene ogni simbolo una volta per riga e colonna. Un Sudoku completato è un quadrato latino che soddisfa anche i nove blocchi 3×3.
- righe: 1–9 una volta ciascuno
- colonne: 1–9 una volta ciascuno
- nessuna regola dei riquadri
- righe: 1–9 una volta ciascuno
- colonne: 1–9 una volta ciascuno
- riquadri: 1–9 una volta ciascuno
Quindi ogni solution grid Sudoku è latina, ma non ogni Latin square è una solution grid Sudoku.
Sudoku come constraint satisfaction problem
Possiamo definire 81 variabili, una per cella, con dominio 1–9. I clues fissano alcune variabili; vincoli all-different su righe, colonne e blocchi limitano le altre.
Propagare questi vincoli produce l'equivalente computazionale di molte eliminazioni di candidati.
I vincoli locali creano una struttura globale
Ogni cella appartiene contemporaneamente a tre unità. Un placement locale modifica candidati in molte celle, che possono creare nuove restrizioni altrove. Questa rete sovrapposta spiega perché poche regole generano deduzioni distribuite come Fish e Chains.
Sudoku come problema exact-cover
Una codifica standard considera 729 possibili assegnazioni cella-cifra (81 celle × 9 cifre) e 324 vincoli:
- 81: ogni cella riceve un valore;
- 81: ogni riga contiene ogni cifra;
- 81: ogni colonna contiene ogni cifra;
- 81: ogni blocco contiene ogni cifra.
Scegliere 81 righe della matrice che coprono ciascun vincolo esattamente una volta equivale a trovare una solution grid. Algorithm X può risolvere questa rappresentazione.
Sudoku come problema in stile grafo
Celle o candidature possono diventare nodi e le incompatibilità archi. Due candidate della stessa cifra in peer sono in conflitto; coppie coniugate e celle bivalue aggiungono relazioni che assomigliano a un grafo di implicazioni.
Questa prospettiva è vicina a Coloring, X-Chains e AIC.
Ricerca e backtracking
Un solver ricorsivo sceglie una cella/candidato, prova un valore, propaga e torna indietro se il ramo diventa impossibile. Con buone euristiche e propagazione, risolve rapidamente puzzle che possono essere molto difficili per un umano.
Exact cover e backtracking non sono opposti
Algorithm X è anch'esso una forma strutturata di ricerca. Dancing Links rende efficienti le operazioni di cover/uncover. La differenza è soprattutto nella rappresentazione del problema e nelle euristiche, non in una contrapposizione “logica vs ricerca”.
Complessità computazionale del Sudoku generalizzato
Il problema decisionale per Sudoku generalizzati n²×n² è NP-completo. Questo risultato riguarda una famiglia di dimensioni crescenti, non significa che un singolo 9×9 sia “impossibile” da risolvere efficientemente in pratica.
Quante griglie Sudoku classiche completate esistono?
Il conteggio noto è:
6.670.903.752.021.072.936.960 solution grids valide.
più di sei sestilioni di griglie classiche di Sudoku complete
Questo numero include molte griglie che sono trasformazioni equivalenti l'una dell'altra.
Griglie Sudoku essenzialmente diverse
Fattorizzando trasformazioni che preservano la struttura — rinominare cifre, permutare righe dentro band, colonne dentro stack, scambiare band/stack e trasporre — restano 5.472.730.538 classi essenzialmente diverse di solution grids.
Perché il conteggio delle solution grids non è il numero di puzzle Sudoku
Un puzzle è una solution grid più una scelta di clues che determina quella soluzione (e possibilmente altre proprietà). La stessa grid può generare moltissimi clue set; alcuni sono unici, altri no, alcuni belli, altri pessimi.
Simmetria nella matematica del Sudoku
Equivalenza delle solution grids
Trasformazioni che preservano i vincoli portano una grid valida in un'altra grid matematicamente equivalente.
Simmetria del layout dei clues
Un costruttore può disporre clues con simmetria rotazionale o riflessiva per estetica. Questa è una proprietà del pattern iniziale e non garantisce unicità o difficoltà.
Le permutazioni aiutano a spiegare l'equivalenza Sudoku
Rinominare tutte le cifre con una stessa permutazione non cambia la struttura logica. Analogamente, alcune permutazioni di righe/colonne che rispettano band e stack conservano i blocchi.
Queste trasformazioni sono utili per ridurre ricerche esaustive e generare variazioni senza cambiare la struttura fondamentale.
Combinatoria della selezione dei clues
Da una solution grid si possono scegliere sottoinsiemi enormemente numerosi di celle come dati. Solo una frazione produce puzzle unici e ancora meno soddisfa criteri editoriali di difficoltà e qualità.
Minimum clues come problema estremale
La domanda “quanto pochi clues possono determinare una soluzione unica?” è un problema combinatorio estremale. Nel classico 9×9 la risposta è 17.
Difficoltà come modello del calcolo umano
Un solver completo può risolvere quasi tutti i 9×9 in tempi trascurabili, quindi il runtime del computer non è un buon proxy della difficoltà percepita. Il rating human-style modella invece tecniche, riconoscimento, dipendenze e lavoro cognitivo.
Perché solver Sudoku diversi servono lavori diversi
Solver completo / contatore di soluzioni
Trova completamenti e prova zero/uno/più soluzioni.
Solver human-style
Cerca una prossima deduzione spiegabile dentro una libreria di tecniche.
Analizzatore di difficoltà
Valuta il solve path con un modello di costi, dipendenze e tecniche.
Generatore
Costruisce solution grids e clue set, invocando gli altri componenti per unicità e qualità.
FAQ
Il Sudoku è basato sull'aritmetica?
No. Le cifre sono simboli e la logica è combinatoria.
Ogni griglia Sudoku completata è un quadrato latino?
Sì.
Tutti i quadrati latini 9×9 sono griglie Sudoku valide?
No, perché potrebbero violare i blocchi 3×3.
Quante griglie Sudoku classiche complete esistono?
6.670.903.752.021.072.936.960.
Quante griglie complete essenzialmente diverse esistono?
5.472.730.538 sotto le equivalenze standard.
Perché ci sono così tante griglie se le regole sono semplici?
Perché i vincoli permettono moltissime permutazioni globalmente compatibili pur restringendo fortemente ogni unità locale.
Il Sudoku è NP-completo?
Il Sudoku generalizzato lo è; il 9×9 fisso non viene descritto correttamente come una famiglia di input di dimensione crescente.
Algorithm X è una tecnica Sudoku umana?
No. È un algoritmo generale per exact cover usato dai solver.
L'enorme numero di solution grids determina la difficoltà Sudoku?
No. La difficoltà riguarda il percorso dal clue set a una soluzione, non il numero totale di griglie possibili nell'universo Sudoku.
Cosa imparare dopo
Approfondisci Generazione, Difficulty Rating, Minimum Clues e la panoramica Teoria del Sudoku.