Contando problema: possibili tavoli sudoku?

Question

Sto lavorando su un risolutore sudoko (python). il mio metodo utilizza un albero di gioco e di esplorare le possibili permutazioni per ogni serie di cifre da Algorithm DFS.

al fine di analizzare problemi, voglio sapere che cosa è il conteggio di tavoli possibile validi e non validi Sudoko?

-.> Una tabella 9 * 9 che hanno 9 uno, due 9, ..., 9 nove

(questo non è esatto duplicato da questa domanda )

La mia soluzione è:

1- Prima selezionare 9 celle per 1s: (*)

2- e simili (1) per le altre cifre (ogni volta, 9 cellule verranno eliminate da cellule disponibili rimanenti): C (81-9,9), C (81-9 * 2,9) .... =
< br> 3- infine moltiplicare il risultato per 9! (Permutazione di 1s-2s-3s ...- 9s a (*))

questo non è uguale a risposta accettato di questa domanda ma i problemi sono equivalenti. Che cosa ho fatto di sbagliato?

Answer 1

Il numero di valide soluzioni griglie di Sudoku per lo standard 9 × 9 griglia è stato calcolato Bertram Felgenhauer e Frazer Jarvis nel 2005 per essere 6.670.903.752.021.072.936.960.

Matematica di Sudoku | fonte

Credo problema con la soluzione è che l'eliminazione di 9 celle ogni volta dalle cellule disponibili non significa necessariamente creare una griglia valida. Quello che voglio dire è solo l'eliminazione di 9 celle non sarà sufficiente.

Questo è il motivo per cui 81! / (9!) ^ 9 è il numero molto più grande rispetto alle soluzioni attuali valide.

Modifica

permutazioni con elementi ripetuti

I tuoi soluzioni è quasi corretta se si desidera che tutti i tavoli non solo valide le tabelle di sudoku.

C'è una formula:

(a + b + c + ...)! / [A! b! c! ....]

Supponiamo che ci sono 5 ragazzi e 3 ragazze e abbiamo 8 posti a sedere quindi il numero di modi diversi in cui possono sedile è

(5 + 3)! / (5! 3!)

Il tuo problema è analogo a questo.

Ci sono 9 1s, 2s 9 ... 9 9s. e 81 posti

così risposta dovrebbe essere (9 + 9 + ...)! / (9!) ^ 9

Ora, se si moltiplicano nuovamente 9! allora questo sarà aggiungere composizioni duplicati al numero da loro mischiare.

Answer 2

questo articolo Wikipedia (o questo OEIS sequenza ), ci sono circa 6,6 * 10 ^ 21 diversi quadrati sudoku.

Answer 3

Quello che hai fatto di sbagliato è stato l'ultimo passo: non si deve moltiplicare la risposta 9!. Hai già contato tutte le possibili piazze.

Questo non aiuta molto di quando contare le possibili Sudoku-tabelle. Un altra cosa che si possa fare è quello di contare i tavoli dove il "row-condizione" detiene:. Che è solo (9!)^9, perché basta scegliere uno permutazione di 1..9 per ogni riga

Ancora più vicino al Sudoku-problema sta contando quadrati latini . quadrato latino deve soddisfare sia la "fila condizione" e "condizione colonna". Che è già un problema difficile e nessuna formula forma chiusa è noto. Sudoku è un quadrato latino con l'aggiunta "subsquare-condizione".