Domande sul Sudoku
In tutto il mondo sta impazzando il gioco matematico Sudoku, in Italia spacciato anche come enigmistico (il quotidiano La Repubblica ne pubblica quotidianamente due schemi). Dal momento che non sempre la soluzione è unica e il gioco è a base matematica mi chiedevo se voi potete rispondere alle seguenti due domande:
Qual è il numero massimo di caselle riempite per cui la soluzione non è unica? Qual è il numero minimo di caselle riempite per cui la soluzione è unica?
Qual è il numero massimo di caselle riempite per cui la soluzione non è unica? Qual è il numero minimo di caselle riempite per cui la soluzione è unica?
8 luglio 2005
Se il numero di cifre di partenza è compreso tra 17 e 77, l'unicità non è mai garantita. In questo caso, infatti, per ogni numero di cifre iniziali ci sono sia schemi con soluzione unica sia schemi con soluzione multipla. Uno schema con più di 77 cifre di partenza ha sicuramente una soluzione unica mentre sembra, ma non è stato ancora dimostrato, che uno schema con meno di 17 cifre di partenza abbia sempre soluzioni multiple. 
Affrontiamo ora il problema più in dettaglio.
Il numero massimo di caselle per cui la soluzione non è unica è 77, cioè 4 in meno dello schema completo. Questo fatto è facilmente dimostrabile:
Una sola casella bianca
Il numero mancante è l'unico che non compare nel quadrato 3x3 che contiene la casella vuota. In questo caso la soluzione è unica.
Due caselle bianche
Se i due numeri sono uguali, basta riempire le due caselle con lo stesso numero; se i due numeri sono diversi, le righe o le colonne corrispondenti alle caselle vuote indicano univocamente i numeri da inserire. In entrambi i casi, la soluzione è unica.
Tre caselle bianche
Se i numeri sono tutti e tre uguali basta riempire le caselle con lo stesso numero; se i numeri sono tutti e tre diversi, le righe, le colonne e i quadrati indicano univocamente i numeri da inserire; se i numeri sono due uguali ed uno diverso basta scrivere il numero "spaiato" grazie agli incroci e poi posizionare gli altri due. In tutti tre i casi, la soluzione è unica.
Quattro caselle bianche
Si può avere la seguente situazione:
In questo caso nelle caselle A può andare l'1 e nelle caselle B il 2 o viceversa.
Si hanno, così, due soluzioni diverse, da cui la tesi.
Viceversa il numero minimo di caselle per cui la soluzione non è univoca sembra essere 17 nel caso di sudoku non simmetrico e 18 nel caso di sudoku simmetrico. Queste affermazioni, come già accennato, non sono state ancora dimostrate.
Alan Viezzoli
Dipartimento di Matematica, Università di Trieste
