Sudoku en un tablero infinito numerable

Question

Consideremos el juego de Sudoku jugado en un tablero infinito donde los subcuadrados también son infinitos, es decir, nuestro tablero está indexado por $\mathbb{N}^2 \times \mathbb{N}^2$. Llamemos solución a este juego a una función $f(a, b, m, n)$ que asigna un número natural a cada espacio $(m,n)$ en cada subcuadrado $(a,b)$, de manera que cada fila, columna y subcuadrado contenga cada número natural exactamente una vez.

Es claro que tal solución existe, ya que para cualquier estado finito del tablero, dado un número natural y cualquier fila, columna o subcuadrado, siempre hay como máximo un número finito de espacios de "colisión", y por lo tanto, con espacios infinitos a nuestra disposición siempre podemos elegir un espacio para poner este número, y continuar haciendo esto infinitamente hasta llenar el tablero.

Sin embargo, estoy teniendo problemas para construir un ejemplo explícito de tal solución, que no dependa de esta especie de magia de elección. Mi primera idea fue usar productos de primos para garantizar que no haya colisión, pero aunque puedo obtener muchas soluciones sin repeticiones, garantizar que cada fila, columna y subcuadrado contenga cada etiqueta pareciera ser un desafío mucho más difícil. Pero sospecho que estoy pasando por alto una solución muy elegante / básica. ¿Alguna idea / pista?

Answer 1

Sea $p$ una biyección de $\mathbb N^2$ a $\mathbb N$. Un ejemplo es $p(x,y)=2^x(2y+1)-1$ (asumiendo que $0\in \mathbb N$).

Sea $\oplus$ una operación en $\mathbb N$ tal que $(\mathbb N,\oplus)$ es un grupo. Por ejemplo, $\oplus$ podría ser la adición de nimbers.

Entonces puedes comprobar que $$ f(a,b,m,n)=p(a\oplus n,b\oplus m) $$ es una función de sudoku válida. Solo necesitamos verificar $3$ cosas:

• Para cada fila, es decir, con $a$ y $m$ fijos y $b$ y $n$ variando, las propiedades de grupo de $\oplus$ implican que cada par ordenado de números naturales se representa como $(a\oplus n,b\oplus m)$ exactamente una vez, por lo que el hecho de que $p$ sea una biyección significa que cada número natural aparece exactamente una vez en cada fila.

• La misma lógica se aplica a las columnas.

• Para las cajas, en cambio, tenemos $a$ y $b$ fijos. Nuevamente, a medida que $m,n$ varían, $(a\oplus n,b\oplus m)$ asumirá cada par ordenado de números naturales exactamente una vez.

Answer 2

Es un teorema bien conocido (llamado argumento diagonal) que existe una biyección $$ \mathbb N \leftrightarrow \mathbb N^2. $$ Esto te proporciona el primer cuadrado (arriba a la izquierda), así como la primera columna. Ahora considera este patrón:

1 2 3 4 5 6 7 8
2 1 4 3 6 5 8 7
3 4 1 2 7 8 5 6
4 3 2 1 8 7 6 5

etc.

Este patrón es en realidad una sucesión de cuadrados, cada uno con un lado de longitud $2^n$. El primer cuadrado es simplemente $1$, y el cuadrado $n$-ésimo se forma a partir del $n-1$-ésimo tomando el cuadrado original $A$, obteniendo otro cuadrado al sumarle $2^{n-1}$ y luego configurando el siguiente cuadrado como

A B
B A.

De esta manera, obtenemos cada número natural en cada fila y cada columna de un cuadrado infinito. Tomando $n$ como el $n$-ésimo columna del cuadrado arriba a la izquierda y ordenando todas las columnas de los cuadrados debajo de él de esta manera, obtenemos la primera columna del Sudoku.

Ahora, utilizando este método aplicado a las filas en lugar de a las columnas, construimos la solución de izquierda a derecha.

Esto funciona porque la propiedad de tener todos los números en una columna no cambia al permutar las filas de un cuadrado.

Answer 3

Solo para dejar claro, no es necesario ser lo suficientemente 'inteligente' para encontrar una solución de 'forma cerrada'. Tener 'finitos obstáculos' es suficiente para demostrar rigurosamente la existencia de una solución. Aquí hay una forma.

El tablero se divide en filas grandes, cada una de las cuales tiene infinitas filas pequeñas. Lo mismo para las columnas grandes y las columnas pequeñas. Llama a la $j$-ésima fila pequeña en la fila grande $i$ fila $(i,j)$, y de manera similar para la columna $(i,j)$. El tablero también se divide en subsquares, cada uno de los cuales es la intersección de una fila grande y una columna grande. Llama a la intersección de la fila grande $i$ y la columna grande $j$ cuadrado $(i,j)$.

Hay algunos requisitos que necesitamos satisfacer además de no tener colisiones:

• $R(i,j,k)$: La fila $(i,j)$ tiene una ocurrencia de $k$.
• $C(i,j,k)$: La columna $(i,j)$ tiene una ocurrencia de $k$.
• $S(i,j,k)$: El cuadrado $(i,j)$ tiene una ocurrencia de $k$.
• $D(i,j,k,l)$: La celda $(i,j,k,l)$ está llena.

En cada ronda $m∈ℕ$, podemos satisfacer todos los requisitos $R(i,j,k)$, $C(i,j,k)$, $S(i,j,k)$, $D(i,j,k,l)$ donde $\max(i,j,k,l) = m$ manejándolos uno por uno, ya que solo hay finitos de ellos. Para ver por qué podemos tener éxito para cada requisito, nota que en cualquier punto solo hemos llenado un número finito de celdas. Por lo tanto, para cada uno de los requisitos $R,C,S$ podemos elegir fácilmente una celda vacía para satisfacerlo. Y para cada requisito $D$ podemos elegir fácilmente un número natural que aún no hemos usado. Incluso podemos hacer esta elección de manera determinista, eligiendo para cada uno de los requisitos $R,C,S$ la celda más superior y luego más a la izquierda que funcione, y eligiendo para cada requisito $D$ el número natural más pequeño que funcione.

Al final, hemos satisfecho todos los requisitos y aún no tenemos colisiones, y por lo tanto tenemos un tablero de sudoku infinito lleno como se deseaba.