Sudoku en un tablero infinitamente numerable

Dejar$p$ser una biyeccion de$\mathbb N^2$a$\mathbb N$. Un ejemplo es$p(x,y)=2^x(2y+1)-1$(asumiendo que$0\in \mathbb N$).

Dejar$\oplus$ser una operación en$\mathbb N$para cual$(\mathbb N,\oplus)$es un grupo Por ejemplo,$\oplus$podría ser una adición más ágil.

Entonces puedes comprobar que

• Para cada fila, es decir con$a$y$m$fijo y$b$y$n$variando, las propiedades de grupo de$\oplus$implica 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$p$es 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$fijado. De nuevo, como$m,n$variar,$(a\oplus n,b\oplus m)$asumirá cada par ordenado de números naturales exactamente una vez.

Es un teorema constructivo (argumento diagonal) bien conocido que existe una biyecció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 un patrón de cuadrados sucesivos, cada uno con una longitud de lado de$2^n$. El primer cuadrado es solo$1$, y el$n$-th cuadrado se forma a partir de la$n-1$st tomando el cuadrado original$A$, obteniendo otro cuadrado sumando$2^{n-1}$y luego establecer el siguiente cuadrado para ser

A B
B A.

De esta manera, obtenemos todos los números naturales en cada fila y cada columna de un cuadrado infinito. Tomando$n$para estar de pie para el$n$-ésimas columnas del cuadrado superior izquierdo y ordenando de esta forma todas las columnas de los cuadrados inferiores, obtenemos la primera columna del Sudoku.

Ahora, usando 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.

Solo para dejar en claro, no tiene que ser 'lo suficientemente inteligente' para encontrar una solución de 'forma cerrada'. Tener 'un número finito de obstrucciones' es suficiente para demostrar rigurosamente la existencia de una solución. Aquí hay una forma.

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

Hay algunos requisitos que debemos cumplir además de que no haya colisiones:

• $R(i,j,k)$: Fila$(i,j)$tiene una ocurrencia de$k$.
• $C(i,j,k)$: Columna$(i,j)$tiene una ocurrencia de$k$.
• $S(i,j,k)$: Cuadrado$(i,j)$tiene una ocurrencia de$k$.
• $D(i,j,k,l)$: La célula$(i,j,k,l)$está lleno.

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)$dónde$\max(i,j,k,l) = m$manejándolos uno por uno, ya que solo hay un número finito de ellos. Para ver por qué podemos tener éxito en cada requisito, tenga en cuenta que en cualquier punto hemos llenado solo un número finito de celdas. Así para cada uno de los$R,C,S$requisitos podemos elegir fácilmente una celda vacía para satisfacerlo. y para cada$D$requisito, 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$R,C,S$requiere la celda superior y luego la izquierda que funciona, y seleccionando para cada$D$requisito el menor número natural que funcione.

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