El número de formas en que se puede llenar una cuadrícula de 999 por 999 dadas algunas condiciones.

Question

El número de formas en que se puede llenar una cuadrícula de 999 por 999 dadas algunas condiciones.

sudoku
Matemáticas
combinaciones
permutaciones
combinatoria

Hussain-Alqatari

¿Cómo encontrar el número de formas en que lo anterior $9$ -por- $9$ la cuadrícula se puede llenar usando los dígitos $(1-9)$ (se permite la repetición) de modo que se cumplan todas las condiciones siguientes:

Cualquier $3$ -por- $3$ la cuadrícula no está totalmente vacía.
Cualquier $3$ -por- $3$ la rejilla no está totalmente llena.
Cualquier $3$ -por- $3$ la cuadrícula no debe contener dígitos repetidos.
Cualquier fila no debe contener dígitos repetidos.
Cualquier columna no debe contener dígitos repetidos.
No debe haber ninguna fila vacía.
No debe haber ninguna fila que esté totalmente llena.
No debe haber ninguna columna vacía.
No debe haber ninguna columna que esté totalmente llena.

Aquí hay ejemplos de casos NO VÁLIDOS (según las condiciones anteriores, respectivamente):

Un vacío $3$ -por- $3$ red:

un totalmente lleno $3$ -por- $3$ red:

Dígitos repetidos en un $3$ -por- $3$ red:

Dígitos repetidos en una fila:

Dígitos repetidos en una columna:

Una fila vacía:

Una fila totalmente llena:

Una columna vacía:

Una columna totalmente llena:

Tenga en cuenta que $C1,C2,C3,\dots,C9,R1,R2,R3,\dots,R9$ se colocan/adjuntan a la $9$ -por- $9$ cuadrícula para indicar que una rotación o transposición $9$ -por- $9$ cuadrícula se considera como una forma diferente (es decir, una girada o transpuesta $9$ -por- $9$ se debe contar la cuadrícula). Aquí hay tres ejemplos de diferentes casos VÁLIDOS:

Primer ejemplo:

Segundo ejemplo:

Tercer ejemplo:

Vi una pregunta similar en este foro (problemas de sudoku), pero esas preguntas no son exactas a esta.

Su ayuda sería muy apreciada. ¡GRACIAS!

rodrigo de azevedo

¿Has probado a usar la programación con restricciones?

Hussain-Alqatari

@RodrigodeAzevedo No tengo conocimiento de eso querido.

brian hopkins

Una reformulación que simplifica las condiciones: Rellene una cuadrícula de 9 por 9 con los dígitos 0, 1, ..., 9 de manera que cada fila, columna y cuadrícula de 3 por 3 contenga al menos un 0 y al menos un número entero positivo sin entero positivo repetido.

Hussain-Alqatari

@BrianHopkins Gracias por comentar querida. Lo que has dicho es exactamente el caso. ¿Me puede ayudar a resolverlo, señor?

alex ravski

Tenemos el siguiente límite superior del número requerido

N

$N$ de maneras. Si una fila tiene

k

$k$ entonces ceros

1 \leq k \leq 8

$1\le k\le 8$ y aquí están

(\binom{9}{k})

${9\choose k}$ maneras de colocarlos en la fila y

\frac{9!}{k!}

$\tfrac {9!}{k!}$ maneras de llenar el resto

n - k

$n-k$ celdas con números positivos. Esto nos da en total

N_{r} = \sum_{k = 1}^{8} \frac{9!^{2}}{k!^{2} (9 - k)!} = 17209233

$N_r=\sum_{k=1}^8 \tfrac {9!^2}{k!^2(9-k)!}=17209233$ posibilidades de llenar una fila. Desde que tenemos

9

$9$ filas,

N \leq N_{r}^{9} \approx 1.324 \cdot 10^{65}

$N\le N_r^9\approx 1.324\cdot 10^{65}$ . Este límite se puede mejorar si tenemos en cuenta que las filas no son independientes pero no pueden contener un número positivo común en la misma columna.

Hussain-Alqatari

@AlexRavsky Eso tiene sentido, gracias por ello. De hecho, pensé de diferentes maneras para resolver el problema, de ninguna manera funcionó. Creo que puede dar sugerencias adicionales/fórmulas útiles y luego intentaré resolverlo y mostrarle mi respuesta para su verificación, ¿puede por favor?

Respuestas (1)

El número de formas en que se puede llenar una cuadrícula de 999 por 999 dadas algunas condiciones.

Una reformulación que simplifica las condiciones: Rellene una cuadrícula de 9 por 9 con los dígitos 0, 1, ..., 9 de manera que cada fila, columna y cuadrícula de 3 por 3 contenga al menos un 0 y al menos un número entero positivo sin entero positivo repetido.
@BrianHopkins Gracias por comentar querida. Lo que has dicho es exactamente el caso. ¿Me puede ayudar a resolverlo, señor?
Tenemos el siguiente límite superior del número requerido $N$ de maneras. Si una fila tiene $k$ entonces ceros $1\le k\le 8$ y aquí están ${9\choose k}$ maneras de colocarlos en la fila y $\tfrac {9!}{k!}$ maneras de llenar el resto $n-k$ celdas con números positivos. Esto nos da en total $N_r=\sum_{k=1}^8 \tfrac {9!^2}{k!^2(9-k)!}=17209233$ posibilidades de llenar una fila. Desde que tenemos $9$ filas, $N\le N_r^9\approx 1.324\cdot 10^{65}$ . Este límite se puede mejorar si tenemos en cuenta que las filas no son independientes pero no pueden contener un número positivo común en la misma columna.
@AlexRavsky Eso tiene sentido, gracias por ello. De hecho, pensé de diferentes maneras para resolver el problema, de ninguna manera funcionó. Creo que puede dar sugerencias adicionales/fórmulas útiles y luego intentaré resolverlo y mostrarle mi respuesta para su verificación, ¿puede por favor?

alex ravski · Answer 1

Podemos mejorar el límite superior del número requerido $N$ de maneras de mi comentario de la siguiente manera.

Considere la primera columna de la cuadrícula llena. Supongamos que tiene $k$ ceros Entonces $1\le k\le 8$ y aquí están ${9\choose k}$ maneras de colocarlos en la columna y $\tfrac {9!}{k!}$ maneras de llenar el resto $9-k$ celdas con números positivos.

Ahora considere las posibilidades de llenar una fila.

Suponga que una fila comienza desde cero. hay $m$ ceros restantes en la fila entonces $0\le m\le 7$ y aquí están ${8\choose m}$ maneras de colocarlos en la fila y $\tfrac {9!}{(m+1)!}$ maneras de llenar el resto $8-m$ celdas con números positivos. Esto nos da en total $N_0=\sum_{m=0}^7 {8\choose m}\tfrac {9!}{(m+1)!}=4596552$ posibilidades de llenar una fila.

Suponga que una fila comienza con un número positivo. hay $m$ ceros en la fila entonces $1\le m\le 8$ y aquí están ${8\choose m}$ maneras de colocarlos en la fila y $\tfrac {8!}{m!}$ maneras de llenar el resto $8-m$ celdas con números positivos. Esto nos da en total $N_+=\sum_{m=1}^8 {8\choose m}\tfrac {8!}{m!}=1401409$ posibilidades de llenar una fila.

En total, tenemos un límite

$N\le \sum_{k=1}^8 {9\choose k} \tfrac {9!}{k!} N_0^k N_+^{9-k}\approx 1.438\cdot 10^{64}$ .

Nuevamente, este límite se puede mejorar si tenemos en cuenta que las filas no son independientes pero no pueden contener un número positivo común en la misma columna. Pero parece que de esta manera conduce a cálculos más complicados y no a una gran mejora.

Muchas GRACIAS querida, intentaré encontrar la respuesta (pronto si puedo), luego la compartiré para verificarla. +50 :-)

El número de formas en que se puede llenar una cuadrícula de 999 por 999 dadas algunas condiciones.

Hussain-Alqatari

rodrigo de azevedo

Hussain-Alqatari

brian hopkins

Hussain-Alqatari

alex ravski

Hussain-Alqatari

Respuestas (1)

alex ravski

Hussain-Alqatari

¿Cuántos pares de conjuntos que no tienen ningún elemento en común?

Palabras de cuatro letras de la palabra MEDITERRANEO tales que la primera letra es R y la cuarta letra es E

Clase de 24 alumnos y 4 elegidos para miembros del comité

Probabilidad y galletas

Probabilidad de volver al punto de partida

Solución incorrecta: dados tres contenedores y tres bolas, ¿cuál es la posibilidad de que exactamente un contenedor esté vacío?

Puntos fijos de grupos de permutación

Calcular el número de veces exactamente 2 pares de letras idénticas consecutivas.

De la palabra SHOWERDOWN, ¿cuántas palabras de 4 letras comienzan y terminan con una vocal?

¿Cuántos números de 6 dígitos son posibles sin que ningún dígito aparezca más de tres veces?