Per un Sudoku classico 9×9 che deve avere esattamente una soluzione, il numero minimo provato di indizi iniziali è:
17
Esistono Sudoku unici a 17 indizi.
Non esiste invece alcun Sudoku classico unico a 16 indizi.
La seconda affermazione è stata stabilita da Gary McGuire, Bastian Tugemann e Gilles Civario tramite una ricerca esaustiva assistita da computer.
Cos'è un indizio?
Un indizio è un numero già presente prima della prima mossa.
Sinonimi contestuali:
- numero dato;
- given;
- clue.
Un Sudoku a 17 indizi parte quindi con:
- 17 caselle riempite;
- 64 caselle vuote.
La soluzione finale contiene sempre 81 valori.
Perché l'unicità fa parte della domanda
Senza richiedere una soluzione unica sarebbe possibile togliere molti più numeri e lasciare una griglia con numerosi completamenti.
La vera domanda è:
Qual è il più piccolo insieme di indizi che determina una sola griglia Sudoku classica completa?
Devono quindi valere entrambe:
- almeno una soluzione esiste;
- non esiste una seconda soluzione.
Perché 17 non era ovvio
Per anni erano noti esempi unici a 17 indizi.
Ma non trovare un esempio a 16 non dimostra che sia impossibile.
Serviva una prova esaustiva capace di escludere l'intero spazio di possibilità rilevante.
La prova contro 16 indizi
A livello alto, la ricerca usa concetti come:
- unavoidable sets;
- hitting sets;
- enumerazione sistematica;
- conteggio/validazione delle soluzioni.
Un unavoidable set è un insieme di caselle tale che un puzzle unico derivato da una certa soluzione deve contenerne almeno una come indizio.
Altrimenti può rimanere possibile un completamento alternativo.
La ricerca costruisce quindi piccoli hitting sets capaci di «toccare» tutti gli unavoidable sets pertinenti e verifica i candidati a 16 indizi.
Nessun caso unico sopravvive.
Da qui la conclusione:
ogni Sudoku classico 9×9 unico richiede almeno 17 indizi.
Minimo vs minimale
Numero minimo di indizi
La più piccola quantità possibile a livello globale.
17.
Sudoku minimale
Puzzle in cui ogni indizio presente è necessario all'unicità.
Rimuovendone uno qualsiasi, il puzzle non è più unico.
Un puzzle minimale può avere:
- 18;
- 24;
- 30;
- o più indizi.
«Minimale» non significa «17 indizi».
Un Sudoku unico a 17 indizi è sempre minimale?
Sì.
Se un indizio potesse essere rimosso mantenendo l'unicità, otterremmo un Sudoku unico a 16 indizi, impossibile.
Il contrario non vale:
un Sudoku minimale non deve necessariamente avere 17 indizi.
Posso scegliere 17 caselle qualsiasi?
No.
La maggior parte delle scelte arbitrarie:
- permette più soluzioni;
- può essere incoerente;
- può produrre un percorso human-style inadatto;
- può avere difficoltà non desiderata.
Il risultato matematico dice soltanto che alcuni Sudoku unici a 17 indizi esistono.
17 indizi significa Esperto?
No.
La difficoltà dipende dalla struttura delle deduzioni, non dal conteggio grezzo degli indizi.
Una griglia molto vuota può risolversi con Singles.
Una più piena può richiedere una Chain avanzata.
Perché il risultato conta per un generatore
Un buon generatore non dovrebbe ottimizzare semplicemente:
meno indizi possibileÈ più utile mirare a:
unicità
+ percorso umano valido
+ difficoltà calibrata
+ varietà
+ riproducibilitàIl numero di indizi è una metrica descrittiva, non un criterio di qualità sufficiente.
FAQ
Qual è il minimo per un Sudoku classico unico?
17.
Esiste un Sudoku unico a 16 indizi?
No.
Tutti i Sudoku a 17 indizi sono difficili?
No.
Tutti i Sudoku unici a 17 indizi sono minimali?
Sì.
Tutti i Sudoku minimali hanno 17 indizi?
No.
Cosa leggere dopo?
Leggi Soluzioni uniche nel Sudoku e Come vengono generati i Sudoku per vedere come l'unicità viene verificata nella pratica.