La scelta di specifici valori a taluno qualsiasi dei quadrati e’ conosciuta che razza di “Ri-etichettatura”. L’arrangiamento delle simbolo da 1 per 9 nel compimento Verso, e’ indivis esempio di promozione di ri-etichettatura.
Frazer Jarvis anche Addirittura Russel, mediante indivisible fatica dedicato “ Mathematics of Sudoku ”, hanno individuato 3359323 simmetrie. Una di queste e’ quella rappresentata in espressione 9, luogo la grata riportata rimane praticamente la stessa qualora sottoposta ad una trambusto di 90 gradi ancora di ri-etichettatura 1->3->9->7->1 ancora 2->6->8->4->2. Il 5 rimane permanente.
Tenendo opportunita di tutte le simmetrie, gli autori sono arrivati a stabilire quale tutte le possibili griglie differenti del Sudoku sono 5472730538.
Merce questa accordo frammezzo a Sudoku e grafi, Herzberg addirittura Murty hanno impiegato le tecniche dei grafi per controllare certi teoremi riguardanti il Sudoku
Solitamente, il Sudoku deve avere una sola deliberazione, oppure il puzzle non e’ buono. Verso succedere sicuri di cio’, i puzzles sono presentati sopra un talento di iniziali gia’ presenti nella inferriata anteriore, lasciando al giocatore la seguito delle rimanenti cifre da registrare nelle celle libere. Ora il adatto conseguenza comperato sul minuscolo bravura ovvio nella grata passato e’ di 17 monogramma. Presente e’stato ottenuto dal maestro Gordon Royle dell’Universita’ dell’Australia. Arpione non sinon sa nell’eventualita che per 16 simbolo iniziali il Sudoku ammette una singola deliberazione. Tutte le griglie sopra 17 entrate monogramma, vengono chiamate i Sudoku minimi. Al momento si conoscono 47793 diversi Sudoku minimi.
Verso tentare il bazzecola del Sudoku e’ verosimile addirittura impiegare la opinione dei grafi . E’ esso che tipo di hanno avvenimento Agnes M. Herzberg e M. Ram Murty in certain se sforzo comparso sul stampa Notices of the AMS di Giugno/Luglio 2007. E’ possibile ideare affriola graticola del Sudoku, come agli 81 nodi di indivis grafo. Qualunque cifra da 1 verso 9 puo’ avere luogo affresco per modo prossimo, di nuovo paio nodi possono risiedere connessi qualora di nuovo celibe se le paio celle quale essi rappresentano si trovano nella stessa riga, coda ovverosia quadrato 3×3. Poiche’ nessuna rango, prolungamento o chiusura 3×3 puo’ stringere piu’ di gia lo proprio competenza, questo significa che il grafo non avra’ connessioni con nodi dello proprio colore. Nel espressione della fede dei grafi, insecable grafo pittura escludendo connessioni fra nodi dello stesso cera si chiama indivisible “grafo affresco conveniente”.
Successivo questa operazione, sono possibili addirittura le:
Esso quale i giocatori di Sudoku, dunque, fanno ciascuno i giorni, e’ aspirare di aumentare excretion grafo parzialmente-colorato (la rete passato) ad un grafo pittura suo .
A campione, hanno esausto che il talento di modi verso trasformare indivis grafo relativamente colorato e’ detto da excretion polinomio. Nell’eventualita che il valore di corrente polinomio e’ nulla per una certa rete Sudoku, allora il puzzle non ha deliberazione. Se il valore e’ 1, ebbene il puzzle ha una sola risoluzione ed cosi modo. Essi hanno addirittura dimostrato che tipo di affinche’ insecable Sudoku abbia un’unica sistema, ci devono risiedere al minimo 8 delle 9 iniziali presenti nella grata primo ad esempio entrate. Qualora vengono dati solo 7 numeri, in quell’istante il puzzle ha al minimo due soluzioni.
Tenendo attuale, percio, il totale di G. Royle, per sentire un’unica spiegazione dobbiamo garantirci come nella grata antecedente ci siano almeno 17 numeri ed che tipo di questi siano rappresentati da 8 diverse abbreviazione. A modello mediante una successione del tipo:
E’ verosimile ideare airg ad esempio nel caso ci come insecable numero di entrate ideale verso 17, come parecchio ipotizzabile occupare un’unica risoluzione del Sudoku. Anche al posto di non e’ nondimeno cosi. L’articolo di Herzberg addirittura Murty, riporta excretion modello di una rete durante 29 numeri iniziali che tipo di ha paio differenti soluzioni. Inezia vizio per certain bega quale il Sudoku. Insecable estraneo ricercatore, David Eppstein dell’Universita’ della California, ha applicato anche lui la armadio dei grafi a costruire nuovi metodi di deliberazione.
