Problema del minimo numero di indizi nel Sudoku

Il problema del minimo numero di indizi nel Sudoku è risolto. 17. Come si sospettava.

Qual è il minor numero di indizi (numeri noti) in uno schema di Sudoku, che possono individuare una griglia univocamente?

Una griglia specifica, ovviamente.
Era nota una griglia che poteva essere individuata da 29 set diversi da 17 indizi ciascuno, in precedenza, ma era arduo pensare di dimostrare che questo fosse il limite, senza controllare esaustivamente i set di 16 indizi.

Gary McGuire ha scritto un programma ottimizzato per controllare tutte le griglie (5,472,730,538 uniche a meno di permutazioni e simmetrie di vario tipo) alla ricerca di un set di 16 indizi. Checkers, il programma, usa una tecnica relativamente nuova che sfrutta i "set inevitabili" di indizi, dei gruppi di cifre nella griglia di cui almeno una deve essere presente in una griglia di soluzione, per mantenere l'unicità.

In meno di un anno il suo cluster di computer ha finito di controllare le griglie confermando l'ipotesi, e bruciando sul tempo progetti analoghi come Sudoku@vtaiwan, che usavano una vecchia versione (meno ottimizzata, circa cento volte piu' lenta) di Checkers.