In questa pagina
Per il Sudoku classico 9×9 con soluzione unica, il numero minimo di clues è 17. Esistono puzzle unici con 17 dati, mentre una ricerca esaustiva ha dimostrato che nessun puzzle a 16 clues può avere una sola soluzione.
Questo risultato riguarda il numero di dati iniziali, non la difficoltà e non la minimalità nel senso tecnico.
Cosa conta come clue Sudoku?
Un clue, dato o given è una cifra fissata nella griglia iniziale. I numeri inseriti dal giocatore durante la risoluzione non contano come clues.
Il problema del minimo chiede: qual è il minor numero di posizioni inizialmente fissate che può ancora determinare esattamente una soluzione classica 9×9?
Perché l'unicità fa parte del problema del minimo
Con pochissimi clues è facile costruire griglie che ammettono molte soluzioni. Il risultato “17” ha senso soltanto imponendo che il puzzle abbia un unico completamento valido.
Una griglia a 10 o 16 clues può essere coerente, ma non può essere un puzzle classico unico a 16 secondo il risultato noto.
Perché 17 non era ovvio
Trovare esempi a 17 dimostra che il minimo è al massimo 17, ma non dimostra che 16 sia impossibile. Per stabilire il minimo serviva anche escludere ogni possibile configurazione a 16 clues senza enumerare ingenuamente un numero astronomico di casi equivalenti.
Come ha funzionato la prova no-16
Nel 2012 Gary McGuire, Bastian Tugemann e Gilles Civario completarono una prova computazionale che esclude tutti i Sudoku unici a 16 clues. Il metodo riduce il problema usando simmetrie/equivalenze delle solution grids e strutture chiamate unavoidable sets, quindi verifica sistematicamente che ogni possibile set di 16 clues fallisca l'unicità.
Il risultato non è una semplice osservazione statistica: è una esclusione esaustiva della classe rilevante.
Cos'è un unavoidable set?
Un unavoidable set è un insieme di celle di una solution grid tale che qualsiasi puzzle unico derivato da quella soluzione deve includere almeno un clue in quell'insieme. Se nessuna cella dell'insieme fosse data, sarebbe possibile una trasformazione che produce un altro completamento.
Questi insiemi permettono di restringere enormemente le combinazioni di clue set da esaminare.
Perché un insieme casuale di 17 clues non basta
Diciassette è il minimo possibile, non una garanzia. La grande maggioranza delle selezioni casuali di 17 celle non determina una soluzione unica. Possono ammettere più completamenti o non formare un puzzle di qualità.
Serve una scelta molto specifica delle posizioni e dei valori.
Minimum vs minimal nei puzzle Sudoku
Puzzle minimum-clue
Raggiunge il minimo globale di clues per la classe: 17 nel classico 9×9 unico.
Puzzle minimal
È irriducibile: togliendo qualsiasi singolo clue, il puzzle perde l'unicità. Un puzzle minimal può avere molti più di 17 clues.
Ogni Sudoku unico a 17 clues è minimal?
Sì. Se togliessi un clue da un puzzle unico a 17, otterresti un puzzle unico a 16, che è impossibile. Quindi ogni 17-clue unico è necessariamente minimal.
Può esistere una griglia a 16 clues?
Può esistere una configurazione iniziale con 16 numeri che rispetta localmente le regole, ma non può determinare una singola soluzione classica 9×9. Avrà più soluzioni oppure non soddisferà le proprietà richieste.
Meno clues significa Sudoku più difficile?
No. La difficoltà human-style dipende dalla struttura delle deduzioni, non dalla quantità grezza di dati. Esistono 17-clue con percorsi relativamente accessibili e puzzle con più clues che richiedono tecniche avanzate.
Perché i costruttori normalmente non inseguono il limite di 17 clues
Un buon puzzle ottimizza molte proprietà: percorso interessante, difficulty target, estetica, simmetria, varietà tecnica, chiarezza e riproducibilità. Ridurre il clue count al minimo può rendere la costruzione più costosa senza migliorare l'esperienza.
Numero minimo di clues per varianti e altre dimensioni
Il risultato 17 è specifico al Sudoku classico 9×9 con blocchi 3×3 e soluzione unica. Cambiando dimensione o regole — Killer, Jigsaw, Diagonal, ecc. — cambiano i vincoli e quindi il problema del minimo.
Perché il risultato è importante
Mostra quanto una piccola quantità di informazione possa determinare un'enorme struttura combinatoria e fornisce un risultato rigoroso che collega Sudoku, ricerca esaustiva, simmetrie e combinatoria.
FAQ
Qual è il minor numero di clues in un Sudoku classico 9×9 unico?
17.
Esistono Sudoku unici a 16 clues?
No, per il classico 9×9 è stato dimostrato che non esistono.
Chi ha dimostrato che servono almeno 17 clues?
Gary McGuire, Bastian Tugemann e Gilles Civario con una prova computazionale pubblicata nel 2012 e successivamente formalizzata in letteratura.
Ogni Sudoku a 17 clues è unico?
No. Soltanto specifiche selezioni di 17 clues determinano una soluzione unica.
Ogni Sudoku unico a 17 clues è minimal?
Sì, perché rimuovere un clue produrrebbe un impossibile puzzle unico a 16.
Ogni Sudoku minimal è a 17 clues?
No. Minimal significa irriducibile e può avere più di 17 clues.
Ogni Sudoku a 17 clues è difficile?
No. Clue count e difficulty human-style non coincidono.
Il limite di 17 clues vale per le varianti Sudoku?
No. È specifico del classico 9×9 con i vincoli standard.
Cosa imparare dopo
Leggi Soluzioni uniche, Come vengono generati i Sudoku e Sudoku e matematica per collegare il risultato del minimo a unicità e costruzione.