La opzione di specifici valori per taluno purchessia dei quadrati e’ conosciuta che “Ri-etichettatura”. L’arrangiamento delle abbreviazione da 1 a 9 nel allacciatura Per, e’ indivisible caso di campagna di ri-etichettatura.
Frazer Jarvis ed Di nuovo Russel, sopra certain lavoro offerto “ Mathematics of Sudoku ”, hanno individuato 3359323 simmetrie. Una di queste e’ quella rappresentata per aspetto 9, luogo la rete riportata rimane effettivamente la stessa nell’eventualita che sottoposta ad una fermento di 90 gradi di nuovo di ri-etichettatura 1->3->9->7->1 e 2->6->8->4->2. Il 5 rimane acconciatura.
Tenendo vantaggio di tutte le simmetrie, gli autori sono arrivati per accertare ad esempio tutte le possibili griglie differenti del Sudoku sono 5472730538.
Pieta questa riscontro con Sudoku ed grafi, Herzberg ancora Murty hanno usato le tecniche dei grafi verso provare non molti teoremi riguardanti il Sudoku
Abitualmente, il Sudoku deve avere una sola soluzione, se no il puzzle non e’ bene. Per essere sicuri di cio’, i puzzles sono presentati in certain bravura di iniziali gia’ presenti nella graticola passato, lasciando al atleta la conclusione delle rimanenti abbreviazione da introdurre nelle celle libere. Adesso il ottimo totale ottenuto sul infimo talento richiesto nella gratella passato e’ di 17 monogramma. Corrente e’stato guadagnato dal insegnante Gordon Royle dell’Universita’ dell’Australia. Ora non sinon sa se con 16 sigla cifra il Sudoku ammette una singola sospensione. Tutte le griglie sopra 17 entrate iniziali, vengono chiamate i Sudoku minimi. Arpione sinon conoscono 47793 diversi Sudoku minimi.
A tentare il gioco del Sudoku e’ plausibile addirittura abusare la dispensa dei grafi . E’ esso ad esempio hanno affare Agnes M. Herzberg anche M. Ram Murty per excretion loro fatica sorto sul disegno Notices of the AMS di Giugno/Luglio 2007. E’ fattibile provvedere appata inferriata del Sudoku, ad esempio agli 81 nodi di excretion grafo. Qualsivoglia nota da 1 a 9 puo’ capitare colorato per come altro, ancora coppia nodi possono essere connessi dato che ed solo dato che le coppia celle quale essi rappresentano sinon trovano nella stessa rango, colonna ovverosia appezzamento 3×3. Poiche’ nessuna rango, prolungamento ovverosia allacciatura 3×3 puo’ restringere piu’ di fu lo uguale competenza, questo significa che razza di il grafo non avra’ connessioni fra nodi dello proprio carne. Nel gergo della teoria dei grafi, indivis grafo colorato in assenza di connessioni entro nodi dello in persona colorito sinon chiama excretion “grafo dipinto proprio”.
Posteriore questa operazione, sono possibili anche le:
Quello quale i giocatori di Sudoku, pertanto, fanno tutti i giorni, e’ ambire di espandere certain grafo parzialmente-affresco (la gratella iniziale) ad indivisible grafo affresco adatto .
Verso dimostrazione, hanno esausto quale il competenza di modi verso variare indivis grafo parzialmente colorato e’ accordato da certain polinomio. Se il valore di codesto polinomio e’ zero verso una certa griglia Sudoku, ebbene il puzzle non ha deliberazione. Qualora il fatica e’ 1, ebbene il puzzle ha una sola deliberazione e cosi strada. Essi hanno addirittura dimostrato come affinche’ certain Sudoku abbia un’unica deliberazione, ci devono risiedere perlomeno 8 delle 9 cifre presenti nella rete iniziale quale entrate. Se vengono dati scapolo 7 numeri, in quella occasione il puzzle ha perlomeno paio soluzioni.
Tenendo presente, tuttavia, il totale di G. Royle, verso ricevere un’unica sistema dobbiamo garantirci che nella rete passato ci siano al minimo 17 numeri ancora che tipo di questi siano rappresentati da 8 diverse sigla. Verso caso con una sfilza del tipo:
E’ facile ideare ad esempio semmai ci tanto un numero di entrate preferibile per 17, cosi tanto ipotizzabile avere un’unica spiegazione del Sudoku. Addirittura anzi non e’ di continuo cosi. L’articolo di Herzberg anche Murty, riporta indivisible modello di una griglia per 29 numeri cifra quale ha paio differenti soluzioni. Sciocchezza vizio a indivis enigma ad esempio il Sudoku. Indivis prossimo studioso, David Eppstein dell’Universita’ della California, ha applicato di nuovo egli la teoria dei grafi a costruire nuovi metodi di sistema.
