Qual è il numero minimo di indizi che un Sudoku può avere?
Ultimo aggiornamento
Un Sudoku valido - con esattamente una soluzione - richiede almeno 17 cifre date. Questo è un risultato matematico provato. Qualsiasi puzzle con 16 o meno indizi ha soluzioni multiple o nessuna.
La dimostrazione del 2012
Nel 2012, Gary McGuire, Bastian Tugemann e Gilles Civario dell'University College Dublin hanno pubblicato una dimostrazione che non esiste alcun Sudoku valido con 16 indizi. Il loro lavoro è stato principalmente computazionale: hanno esplorato l'intero spazio delle possibili griglie con 16 indizi e verificato che nessuna produceva una soluzione unica. La ricerca ha richiesto circa 7 milioni di ore-core di calcolo.
Prima di ciò, si credeva ampiamente che 17 fosse il minimo e migliaia di puzzle con 17 indizi erano stati trovati sperimentalmente. Il team di McGuire ha fornito la prima dimostrazione rigorosa che 16 è impossibile.
Che aspetto hanno i puzzle con 17 indizi
I puzzle con 17 indizi sono estremamente radi - 17 cifre date in 81 celle, lasciando 64 vuote. Sono tra i puzzle più difficili da risolvere e richiedono tipicamente tecniche avanzate. Trovare puzzle validi con 17 indizi ha richiesto decenni di sforzo computazionale. Al momento della scrittura, sono noti oltre 49.000 puzzle Sudoku con 17 indizi essenzialmente diversi.
Cosa significa questo per la progettazione di puzzle
I puzzle pubblicati destinati a risolutori umani raramente scendono sotto i 22 indizi. I puzzle di difficoltà Expert e Master usano tipicamente 22-27 cifre date, mentre i puzzle Facili usano 36-45. Il minimo di 17 indizi è un limite teorico - In pratica, la risolvibilità con buona tecnica e un percorso di risoluzione piacevole contano molto più del solo numero di indizi.