Qual è l'aritmetica dietro la griglia vuota del Sudoku?

Sudoku Blank Grid è utilizzato nella simmetria del sudoku,prevede righe e colonne di 4 × 4,16 × 16 e più con griglie piccole e varianti.

I puzzle di Sudoku possono essere studiati matematicamente per rispondere a domande come “Quante griglie di Sudoku complete?”, “Qual è il numero minimo di suggerimenti in un vero puzzle?” e “Come possono le griglie di Sudoku essere simmetriche?” utilizzando teorie combinatorie e di gruppo.

I risultati principali sono quelli del Sudoku classico, il numero di griglie completate è 6,670,903,752,021,072,936,960 (6.67× 1021), quale, pur mantenendo la validità della trasformazione si riduce a 5,472,730,538 gruppi significativamente diversi.

Ci sono 26 tipi di simmetria, ma si possono trovare solo in circa 0.005% di tutte le griglie riempite.

Un puzzle con una soluzione unica deve avere almeno 17 soluzioni, e per ogni reticolo risolto non ce ne sono più di 21 soluzioni. Il più grande puzzle minimo trovato ha 40 indizi.

Risultati simili sono noti per varianti e griglie più piccole. Risultati accurati non sono noti per Sudoku più della classica griglia 9 × 9, sebbene vi siano stime considerate abbastanza accurate.

Soluzioni di calcolo per il Sudoku

Una domanda interessante è, quanti modi può a 9 di 9 La griglia Sudoku deve essere riempita per soddisfare la regola singola?

In altre parole, quante diverse soluzioni Sudoku esistono? Descriviamo all'inizio il metodo utilizzato da Bertram Felgenhauer e Fraser Jarvis 2006 per calcolare questo numero.

Per mantenere lo standard della nostra lingua, chiamiamo tre file di blocchi strisce di una griglia e tre colonne di blocchi di pile. Una cella in questa riga e la colonna j sono considerate a (io,j).

Chiamiamo il numero delle singole griglie Sudoku N. Primo, chiamiamo i blocchi della griglia come segue:

Quanti modi ci sono per riempire B1 in modo valido? Dal momento che ci sono 9 caratteri che possono riempire B1, uno in ogni cella, questo è 9 opzioni per la prima cella.

Per ognuno di questi 9 opzioni, ci sono 8 opzioni per la seconda cella. Per ognuno di questi 8 opzioni, ci sono 7 lasciato per la terza cella.

Fondamentalmente, calcoliamo il numero di permutazioni di 9 personaggi: quanti modi possiamo posizionare 9 caratteri in 9 posti, o quanti modi possiamo ordinare 9 cose.

Ci sono 9 modi per compilare B1. A partire da un blocco B1 valido, possiamo ottenere qualsiasi altro blocco B1 valido rimarcando o riorganizzando i numeri.

Così, la prima ipotesi semplificativa che possiamo fare è che B1 sia pieno di numeri 1, 2, 3, …, 9 In ordine, come mostrato di seguito.

Ora possiamo calcolare quante terminazioni effettive della griglia ha questo particolare B1: chiamiamolo N1. Il numero totale di griglie Sudoku effettive è N1 × 9!, quindi N1 = N / 9!…

Consideriamo i modi per riempire le prime righe in B2 e B3. Da 1, 2 e 3 si verificano nella prima riga in B1, questi numeri non possono comparire nelle altre righe.

Perciò, solo i numeri 4, 5, 6, 7, 8 e 9 dalla seconda e terza fila di B1 possono incontrarsi in prima fila in B2 e B3.

Elenca tutti i modi possibili per riempire le prime righe in B2 e B3, fino a riorganizzare i numeri in ogni blocco. Mancia: Ci sono dieci modi per farlo in modo che lo scambio di B2 e B3 in questi dieci modi ti dia altri dieci modi, un totale di venti.

Chiamiamo due di queste possibilità pure top line: quando i numeri {4,5,6}, come nella seconda riga di B1, vengono memorizzati insieme in B2, e numeri {7,8,9}, come nella terza riga di B1, vengono memorizzati insieme in B3, e una versione modificata di questo.

Le altre possibilità sono linee superiori miste, mentre mescolano i set {4,5,6} e {7,8,9} quando viene utilizzato per riempire le prime righe di B2 e B3.

Date queste venti possibilità per la prima linea della griglia (fino a riorganizzare i numeri in ogni blocco), possiamo capire come riempire la prima riga.

Pensa a come puoi completare la prima fascia partendo dalla riga superiore pura 1,2,3;{4,5,6};{7,8,9}.

(Nota: Stiamo scrivendo un file,B,c per denotare una tripla ordinata di numeri e {un',B,c} per denotarli in qualsiasi ordine.)

Quante possibilità ci sono, contando diversi ordini di numeri all'interno di ogni riga in B2 e B3? Questo numero è lo stesso dell'altra riga superiore pura, 1,2,3;{7,8,9};{4,5,6}?

Ricorda, vogliamo mantenere B1 fisso perché abbiamo già considerato il numero di griglie che si possono ottenere rietichettando le nove cifre in esso.

Si scopre che ci sono (3!)⁶ modi per completare la prima fascia fissando con la riga superiore pura 1,2,3;{4,5,6};{7,8,9}.

Questo perché siamo costretti a mettere {7,8,9};{1,2,3} in seconda fila in B2 e B3 e {1,2,3};{4,5,6} in terza fila, e quindi possiamo riordinare le tre cifre in ciascuna delle sei righe di B2 e B3 per ottenere tutte le configurazioni.

La risposta è la stessa per l'altra riga superiore pura, poiché in questo caso tutto ciò che abbiamo fatto è stato scambiato B2 con B3.

I casi delle prime file miste sono più complicati. Consideriamo la prima riga 1,2,3;{4,6,8};{5,7,9}. Questo può essere completato alla prima fascia come nella figura seguente, dove un, B, ec sono i numeri 1, 2, 3 in qualsiasi ordine.

Dopo aver selezionato un file, bec sono i due numeri rimanenti in qualsiasi ordine, poiché sono nella stessa riga.

Poiché ci sono tre opzioni per un file, e tre cifre in ciascuna delle sei serie in B2 e B3 possono essere saltate per ottenere diverse prime pagine valide, il numero totale di configurazioni in questo caso è 3 ×(3!)6.

Allo stesso modo puoi lavorare su ciascuno dei rimanenti diciassette casi in prima fila per ottenere lo stesso numero.

Ora abbiamo il numero di prime pagine possibili definito da B1: questo è 2 ×(3!)6+18× 3 ×(3!)6= 2612736, dove la prima parte della somma è il numero di completamenti della prima pagina dalle prime righe nette e la seconda è il numero di completamenti della prima pagina dalle righe superiori miste.

Invece di calcolare quanti completamenti in prima pagina di ciascuno di questi 2612736 Caratteristiche, Felgenhauer e Jarvis hanno determinato quali prime pagine hanno lo stesso numero di completamenti della prima pagina dallo spazio vuoto superiore.

Questa analisi riduce il numero di prime pagine da prendere in considerazione durante il calcolo.

Di seguito sono riportate alcune operazioni che lasciano invariato il numero di finali della griglia del primo intervallo: rimarcando i numeri, ascoltando uno qualsiasi dei blocchi nella prima gamma, ascoltando le colonne in qualsiasi blocco e ascoltando le tre righe dell'intervallo. Con una qualsiasi di queste modifiche B1, possiamo contrassegnare nuovamente i numeri per ripristinarne la forma standard.

Organizzare B1, B2 e B3 mantengono il numero di finali della griglia, perché se iniziamo con una qualsiasi griglia Sudoku reale, l'unico modo per mantenerlo reale è contrassegnare B4, B5, B6 e B7, B8, B9 rispettivamente in modo che le pile rimangano le stesse.

In altre parole, ogni effettiva terminazione della griglia della prima pagina fornisce esattamente un'effettiva terminazione della griglia della prima pagina, vale a dire. qualsiasi B1, B2, Permutazione B3.
Assicurati che quando cambi B2 in B3 nella prossima griglia di Sudoko, l'unico modo per mantenere la griglia valida è cambiare B5 in B6 e B7 in B8. Ciò manterrà le pile uguali, sebbene la loro posizione sia cambiata.

Se disponi di una griglia Sudoku valida e stai saltando le colonne in uno qualsiasi di B1, B2 e B3, cosa dovresti fare con le colonne del resto della griglia del Sudoku per mantenerla valida? Per esempio, se hai cambiato colonne 1 e 2 di B2 sulla griglia sopra, come aggiustereste la griglia risultante in modo che soddisfi l'unica regola?

L'ultimo esercizio ci dice che ogni riempimento della griglia della prima fila dà un riempimento unico della griglia della prima fila con le colonne saltate all'interno dei blocchi.

Tali considerazioni ci consentono di ridurre il numero di prime pagine specifiche di cui tenere conto nel conteggio.

A seguire Felgenhauer e Jarvis, scorriamo le colonne B2 e B3 in modo che le voci della riga superiore di ciascuna colonna siano in ordine crescente, quindi scambiare B2 e B3 se necessario in modo che la prima voce B2 sia più piccola della voce B3.

Questa è chiamata abbreviazione lessicografica.

Poiché ciascuno dei due blocchi ha 6 riorganizzazioni di colonne e due modi di riorganizzare i blocchi, ce lo dice la stenografia lessicografica, data la prima pagina, ci sono 62 × 2 = 72 altre prime pagine con lo stesso numero di terminazioni della griglia.

Quindi ora abbiamo solo 2612736/72 = 36288 prime pagine da considerare.

Per ciascuna di queste possibilità diamo un'occhiata alle riorganizzazioni di tutti e tre i blocchi superiori: ci sono 6. Per ognuno di loro ci sono 63 riorganizzazione delle colonne all'interno di ogni blocco.

Dopo aver eseguito queste operazioni, contrassegniamo nuovamente per riportare B1 alla sua forma standard.

allo stesso modo, possiamo sovrascrivere le prime tre righe del gruppo e contrassegnare nuovamente per riportare B1 a una forma standard. Queste operazioni salvano il numero di completamenti della griglia in prima fila.

Felgenhauer e Jarvis hanno utilizzato un programma per computer per determinare che queste operazioni riducono il numero di prime pagine da cui prendere in considerazione 36288 a solo 416.

Consideriamo questo primo gruppo.

Esegui varie operazioni su di esso che ne salvano il numero di terminazioni di griglia. Puoi iniziare con quanto segue: Scambia la prima e la seconda riga. Contrassegnalo nuovamente in modo che B1 sia nella sua forma standard. Ridurre lessicograficamente questa griglia.

La cosa principale è che il gruppo con cui hai iniziato e l'altro gruppo con cui hai finito hanno lo stesso numero di completamenti fino alla griglia di Sudoku completa.

così, invece di calcolare il numero di finali della griglia per ciascuno di questi gruppi, possiamo calcolarlo solo per uno di essi.

Ci sono più passaggi che riducono il numero di griglie da considerare. Se abbiamo un paio di cifre {un',B} in una colonna con a in una iesima riga eb in una jesima riga, e la stessa coppia in un'altra colonna con b in una iesima riga e a in una jesima riga, ogni coppia avrà una banda con lo stesso numero di terminazioni della griglia dell'originale.

Questo perché ogni coppia si trova nella stessa colonna, e quando entrambi vengono modificati contemporaneamente, viene salvata un'unica regola, che soddisfa anche le file coinvolte.

Come esempio, guarda i numeri 8 e 9 nella sesta e nona colonna dell'esempio precedente. Considera tutti i possibili casi di questa sinistra con cui Felgenhauer e Jarvis 174 del primo 416 gruppi con cui continuare.

Hanno anche considerato altre configurazioni dello stesso insieme di numeri che giacciono in due colonne o righe differenti, che possono essere omessi all'interno delle loro colonne o righe, lasciando invariante il numero di terminazioni della griglia.

Ciò ha ridotto il numero di prime pagine a 71, e la ricerca di ciascuno di questi 71 casi hanno chiarito loro che in realtà ci sono solo 44 prime pagine di cui trovare il numero di completamenti della griglia.

Ognuno di questi 44 le bande hanno lo stesso numero di finali dell'intera griglia.

Indichiamo con C uno di questi 44 strisce. Quindi puoi calcolare il numero di modi in cui C può completare la griglia Sudoku completa: chiamalo nc.

Abbiamo anche bisogno del numero di prime pagine mC che condividono questo numero di finali nC della griglia. Poi, il numero totale di griglie Sudoku è solo N = ΣCmCnC, o la somma di mCnC per tutti 44 strisce.

Felgenhauer e Jarvis hanno scritto un programma per computer per fare i calcoli finali.

Hanno calcolato il numero di completamenti validi N1 con B1 in una forma standard, Iniziare con 44 corsie. Quindi hanno moltiplicato questo numero per 9! per ottenere una risposta.

Hanno scoperto che il numero di possibili 9 di 9 Le griglie di Sudoku sono N = 6670903752021072936960, che è di circa 6,671 × 1021.

Articolo e credito d'immagine:

http://pi.math.cornell.edu/~mec/Summer2009/Mahmood/Count.html