43 votos

¿Es el sudoku solo un rompecabezas?

Considera un grafo G donde cada nodo representa una posible solución de Sudoku. Definimos bordes entre nodos basados en la aplicación de "transformaciones equivalentes" específicas que mapean una solución a otra. Estas transformaciones incluyen:

  1. re-etiquetar números;
  2. reflexión;
  3. rotación;
  4. permutación de bloques de columnas (1-3, 4-6, 7-9);
  5. permutación de bloques de filas (1-3, 4-6, 7-9);
  6. permutación de columnas dentro de cada bloque (1-3, 4-6, 7-9) y
  7. permutación de filas dentro de cada bloque (1-3, 4-6, 7-9).

Entonces: un borde es dibujado entre dos nodos si una solución puede ser transformada en la otra aplicando cualquiera de estas transformaciones.

Dada esta construcción, ¿el grafo resultante G está conectado? En otras palabras, ¿existe un camino entre cualquier par de nodos en el grafo?

34voto

Jade Vanadium Puntos 371

No, no es el caso. En los comentarios, Thomas Andrews sugiere un invariante: para $1\leq i, define $T_{i,j}$ como el número de filas y columnas en las que $i,j$ están en el mismo tercio. El multiconjunto que consiste en todos los valores de $T_{i,j}$ no cambia bajo ninguna de las simetrías listadas. Debido a esto, obtenemos una respuesta negativa siempre y cuando encontremos dos rompecabezas que difieran bajo este invariante. A continuación se presentan dos rompecabezas explícitos que difieren de esa manera.

enter image description here

Es muy fácil verificar este sudoku, ya que cada bloque es prácticamente idéntico bajo la traslación. En este primer rompecabezas, podemos ver que para cualquier par de números $i\neq j$, ya sea tenemos que $i$ y $j$ están en el mismo tercio en los $9$ bloques, o nunca tenemos que $i,j$ están en el mismo tercio de ningún bloque en absoluto. Usando el invariante establecido previamente, vemos que $T_{i,j}\in\{0,9\}$ para todos los $i,j$, por lo que el multiconjunto de todos los valores de $T_{i,j}$ no contiene ningún número que no sea $0$ o $9$. El siguiente rompecabezas viola esta regla.

enter image description here

En el rompecabezas anterior, podemos ver que $1,7$ están en el mismo tercio en el bloque superior izquierdo, pero no en el bloque del medio, por lo que en particular $T_{1,7}\notin \{0,9\}$. Si te preocupa verificar este sudoku, puedes usar prácticamente cualquier rompecabezas resuelto para reemplazar este segundo ejemplo. La mayoría de los rompecabezas resueltos no están casi tan organizados como mi primer ejemplo.

32voto

Según Wikipedia, para el Sudoku clásico, la cantidad de cuadrículas válidamente rellenadas es $6{,}670{,}903{,}752{,}021{,}072{,}936{,}960 \approx6.671×10^{21}$, lo que se reduce a $5{,}472{,}730{,}538$ soluciones esencialmente distintas bajo las transformaciones de equivalencia.

Una referencia directa para esto es el artículo de 2006 de Russell & Jarvis.

8voto

Lucenaposition Puntos 35

Hay dos diferentes:

1

2

El primero no tiene rectángulos con solo dos valores.
El segundo tiene rectángulos con solo dos valores (resaltados en amarillo).
Por rectángulo me refiero a la intersección de dos filas y dos columnas.

8voto

tkf Puntos 8

Esta respuesta es muy similar a la de @JadeVanadium (+1), pero con soluciones de Sudoku explícitas y verificación, reemplazadas por construcciones y argumentos. Creo que es bueno tener ambas.

Un Sudoku completado es precisamente una función $f\colon {\mathbb{F}_3}^4\to {\mathbb{F}_3}^2$ que cumple que para cualquier $a_1,a_2,a_3,a_4\in {\mathbb{F}_3}$ los mapas siguientes son biyecciones:

$$ (x,y)\mapsto f(x,y,a_3,a_4),\\(x,y)\mapsto f(a_1,a_2,x,y),\\(x,y)\mapsto f(x,a_2,y,a_4). $$

Estas tres condiciones son simplemente las restricciones habituales de que las filas, columnas y bloques contienen entradas distintas.

Por lo tanto, una solución es $f(a_1,a_2,a_3,a_4)=(a_1+a_4,a_2+a_3)$.

Esto se generaliza a la familia de soluciones $f^\lhd(a_1,a_2,a_3,a_4)=(a_1+a_4,(a_1\lhd a_2)+a_3)$ donde para $i\in \mathbb{F}_3$, tenemos $i\lhd \in S_{\mathbb{F}_3}$.

Sea $C$ el conjunto de $54$ líneas en ${\mathbb{F}_3}^4$ de la forma $(*,a_2,a_3,a_4)$ o $(a_1,a_2,*,a_4)$ (donde los $a_i$ son valores fijos). Para un Sudoku completado $h$, sea $N(h)$ el número de imágenes distintas de elementos de $C$: $$N(h)=|\{h(I)\subset {\mathbb{F}_3}^2\vert\,\, I\in C\}|.$$

La Transformación 1 volverá a etiquetar las imágenes $h(I)$, pero no cambiará su número. Sostenemos que las transformaciones restantes permutan los elementos de $C$, por lo que tampoco afectan a $N(h)$:

La Transformación 2 consiste en mapas de la forma $$\qquad\,\,\,\,(a_1,a_2,a_3,a_4) \mapsto (-a_1,-a_2,a_3,a_4)\\{\rm o}\qquad (a_1,a_2,a_3,a_4) \mapsto (a_1,a_2,-a_3,-a_4) $$

Estos preservan claramente los elementos de $C$.

La Transformación 3 consiste en mapas de la forma $$\qquad\,\,\,\,(a_1,a_2,a_3,a_4) \mapsto (a_3,a_4,-a_1,-a_2)\\{\rm o}\qquad\qquad (a_1,a_2,a_3,a_4) \mapsto (-a_3,-a_4,a_1,a_2)\\{\rm o}\qquad (a_1,a_2,a_3,a_4) \mapsto (-a_1,-a_2,-a_3,-a_4)\,\,\, $$

Estos también preservan elementos de $C$, siendo que los dos primeros intercambian las líneas de la forma $(*,a_2,a_3,a_4)$ con las líneas de la forma $(a_1,a_2,*,a_4)$.

Las Transformaciones 4 y 5 tienen la forma:$$\qquad\,\,\,\,(a_1,a_2,a_3,a_4) \mapsto (a_1,\sigma(a_2),a_3,a_4)\\{\rm o}\qquad (a_1,a_2,a_3,a_4) \mapsto (a_1,a_2,a_3,\sigma(a_4)) $$

respectivamente, para algún $\sigma\in S_{\mathbb{F}_3}$. Claramente, estos también preservan elementos de $C$.

Las Transformaciones 6 y 7 tienen la forma:$$\qquad\,\,\,\,(a_1,a_2,a_3,a_4) \mapsto (\sigma_{a_2}(a_1),a_2,a_3,a_4)\\{\rm o}\qquad (a_1,a_2,a_3,a_4) \mapsto (a_1,a_2,\sigma_{a_4}(a_3),a_4) $$ respectivamente, para $\sigma_i\in S_{\mathbb{F}_3}$ que dependen del parámetro $i$. Estos preservan elementos de $C$. Nota que estos arruinan por completo las líneas de la forma, $(a_1,*,a_3,a_4)$ o $(a_1,a_2,a_3,*), por eso definimos $C$ de la forma en que lo hicimos.

Concluimos que $N$ es invariante en las clases de equivalencia de Sudokus completados.

Ahora bien, $N(f)= 6$, ya que las imágenes de elementos de $C$ bajo $f$ son simplemente las líneas horizontales o verticales en ${\mathbb{F}_3}^2$.

Resta encontrar un producto $ \lhd\colon \mathbb{F}_3 \times \mathbb{F_3} \to \mathbb{F_3}$ tal que $N(f^\lhd)\neq 6$. Recordemos, la única restricción que pusimos en $\lhd$ para que $f^\lhd$ sea una solución de Sudoku válida fue que para $i\in \mathbb{F}_3$, tenemos $i\lhd \in S_{\mathbb{F}_3}$.

Así que $$i\lhd j = (-1)^{\delta_{0i}}j$$ nos da una solución de Sudoku válida $f^\lhd$, donde $\delta$ es el delta de Kronecker habitual.

Las líneas $(a_1,a_2,*,a_4)$ se asignan a las $3$ líneas verticales en ${\mathbb{F}_3}^2$ de la misma forma que lo hicieron bajo $f$. Asimismo, las líneas $(*,0,a_3,a_4)$ se asignan a las mismas $3$ líneas horizontales que bajo $f$. Sin embargo $(*,1,0,0)$ se asigna al conjunto: $$\{(0,2),(1,1),(2,1)\}.$$ Esto no es ni una línea vertical ni horizontal, por lo que tenemos $N(f^\lhd)>6$. Por lo tanto, $f$ y $f^\lhd$ son soluciones de Sudoku no equivalentes. (De hecho, es fácil ver que los $18$ elementos de $C$ que no se asignan a líneas horizontales o verticales se asignan a imágenes distintas en ${\mathbb{F}_3}^2$, por lo que $N(f^\lhd)=24$).

En términos convencionales de Sudoku, $f$ es esencialmente la primera solución en la respuesta de Jade Vanadium, y obtenemos $f^\lhd$ de $f$ intercambiando las 2da y 7ma columnas. Esta transformación no preserva soluciones en general, pero lo hace en este caso porque $f$ tiene tanta simetría. El conjunto $C$ es simplemente el conjunto de tercios, por lo que el invariante $N$ es muy similar al de la respuesta de Jade Vanadium. De hecho, es claro que si intercambias las 1ra y 4ta columnas en la primera solución de Jade Vanadium, entonces el par $1,2$ aparecerá en el mismo tercio en precisamente $5\notin\{0,9\}$ de las casillas.

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by:

X