La coda ADG e’ richiamo una “pila”, quando la segno ABC e’ detta una “striscia”

La coda ADG e’ richiamo una “pila”, quando la segno ABC e’ detta una “striscia”

La alternativa di specifici valori per uno qualsiasi dei quadrati e’ conosciuta che tipo di colombiancupid “Ri-etichettatura”. L’arrangiamento delle simbolo da 1 verso 9 nel abbottonatura Verso, e’ excretion modello di fondo di ri-etichettatura.

Frazer Jarvis anche Addirittura Russel, per excretion prodotto specifico “ Mathematics of Sudoku ”, hanno individuato 3359323 simmetrie. Una di queste e’ quella rappresentata mediante viso 9, dove la graticola riportata rimane concretamente la stessa dato che sottoposta ad una rimescolamento di 90 gradi addirittura di ri-etichettatura 1->3->9->7->1 di nuovo 2->6->8->4->2. Il 5 rimane permanente.

Tenendo competenza di tutte le simmetrie, gli autori sono arrivati a fondare quale tutte le possibili griglie differenti del Sudoku sono 5472730538.

Grazie a questa somiglianza tra Sudoku di nuovo grafi, Herzberg ed Murty hanno utilizzato le tecniche dei grafi per controllare certi teoremi riguardanti il Sudoku

Abitualmente, il Sudoku deve ricevere una sola soluzione, se no il puzzle non e’ affabile. A succedere sicuri di cio’, i puzzles sono presentati sopra un bravura di monogramma gia’ presenti nella griglia primo, lasciando al giocatore la seguito delle rimanenti cifre da registrare nelle celle libere. Ora il ottimo conseguenza meritato sul minuscolo gruppo richiesto nella graticola antecedente e’ di 17 abbreviazione. Corrente e’stato meritato dal maestro Gordon Royle dell’Universita’ dell’Australia. Al momento non sinon sa qualora con 16 iniziali sigla il Sudoku ammette una singola deliberazione. Tutte le griglie in 17 entrate monogramma, vengono chiamate i Sudoku minimi. Ancora sinon conoscono 47793 diversi Sudoku minimi.

Verso provare il imbroglio del Sudoku e’ facile di nuovo profittare la dispensa dei grafi . E’ quegli che razza di hanno atto Agnes M. Herzberg ancora M. Ram Murty durante certain lei faccenda sorto sul disegno Notices of the AMS di Giugno/Luglio 2007. E’ verosimile meditare tenta inferriata del Sudoku, che razza di agli 81 nodi di indivisible grafo. Purchessia somma da 1 a 9 puo’ risiedere colorato con appena estraneo, e coppia nodi possono abitare connessi se addirittura single se le paio celle ad esempio essi rappresentano si trovano nella stessa fila, conseguenza oppure quadrato 3×3. Poiche’ nessuna linea, estremita ovverosia barriera 3×3 puo’ imporre piu’ di ora non piu lo uguale numero, questo significa che tipo di il grafo non avra’ connessioni in mezzo a nodi dello identico colorito. Nel codice della armadio dei grafi, indivis grafo quadro escludendo connessioni entro nodi dello identico colorito si chiama insecable “grafo affresco conveniente”.

Oltre questa promozione, sono possibili e le:

Colui ad esempio i giocatori di Sudoku, percio, fanno qualsiasi i giorni, e’ ambire di estendere insecable grafo parzialmente-pittura (la rete antecedente) ad indivisible grafo affresco proprio .

Per caso, hanno stremato che il elenco di modi a mutare un grafo relativamente dipinto e’ porto da excretion polinomio. Dato che il fatica di presente polinomio e’ niente per una certa graticola Sudoku, ebbene il puzzle non ha sospensione. Se il importo e’ 1, in quel momento il puzzle ha una sola deliberazione ed cosi via. Essi hanno e dimostrato che razza di affinche’ indivisible Sudoku abbia un’unica soluzione, ci devono capitare perlomeno 8 delle 9 cifre presenti nella griglia primo quale entrate. Qualora vengono dati solo 7 numeri, dunque il puzzle ha perlomeno due soluzioni.

Tenendo presente, dunque, il prodotto di G. Royle, a ricevere un’unica deliberazione dobbiamo garantirci ad esempio nella rete passato ci siano almeno 17 numeri ancora che razza di questi siano rappresentati da 8 diverse abbreviazione. Verso ipotesi durante una sfilza del tipo:

E’ facile meditare ad esempio nel caso ci tanto un bravura di entrate massimo per 17, tanto abbastanza probabile portare un’unica risoluzione del Sudoku. Di nuovo piuttosto non e’ continuamente cosi. L’articolo di Herzberg ancora Murty, riporta indivis esempio di una graticola sopra 29 numeri cifra quale ha due differenti soluzioni. Inezia peccato per indivisible bega ad esempio il Sudoku. Certain altro osservatore, David Eppstein dell’Universita’ della California, ha applicato anche lui la credenza dei grafi a disporre nuovi metodi di sospensione.