Determinar si dos tableros de Sudoku están en la misma clase de equivalencia

Question

Considere lo siguiente $9 \times 9$ Tablero de sudokus

963 174 258
178 325 649
254 689 731

821 437 596
496 852 317
735 961 824

589 713 462
317 246 985
642 598 173

y el siguiente tablero de Sudoku parcialmente rellenado

.6. 1.4 .5.
2.. ... ..1
..8 3.5 6..

8.. 4.7 ..6
..6 ... 3..
7.. 9.1 ..4

5.. ... ..2
.4. 5.8 .7.
..7 2.6 9..

La tarea consiste en averiguar si están en la misma clase de equivalencia .

Los tableros de sudokus se cierran con las siguientes operaciones :

• Reetiquetado de símbolos (¡9!)
• Permutaciones de bandas (¡3!)
• Permutaciones de filas dentro de una banda ( ${3!}^3$ )
• Permutaciones de la pila (¡3!)
• Permutaciones de columnas dentro de una pila ( ${3!}^3$ )
• Reflexión, transposición y rotación (2).

¿Cómo puedo averiguar (sin probar todas las combinaciones posibles de la tabla sin resolver) si están en la misma clase de equivalencia?

El enfoque probablemente debería ser definir una forma canónica para el rompecabezas resuelto y luego encontrar un método para derivar la forma canónica de cualquier tablero de Sudoku. Pero, ¿cuál es mi elección de la forma canónica y cómo derivar la forma canónica de cualquier tablero de Sudoku (dado que tenemos un tablero resuelto)?

Answer 1

Ok - tu pregunta inicial me hizo pensar (a pesar del comentario que dejé arriba). Dejemos que $X$ denota el conjunto de todas las cuadrículas de Sudoku. Entonces está claro que este conjunto es finito. Sea $G$ denotan el grupo de simetría de una cuadrícula de Sudoku. Entonces está claro que cada elemento de $G$ es un mapa de una cuadrícula válida a otra, significa $G$ sólo tiene un número finito de simetrías.

Así pues, entendamos por equivalente rejillas las que se pueden mapear (en $X$ ) por una (o varias) de las simetrías en $G$ . Para cualquier $A \in X$ todas las cuadrículas equivalentes a $A$ son esencialmente los mismos que $A$ . Así que para todas las cuadrículas equivalentes a (digamos, w.l.o.g) $A_i$ podemos dividir $X$ en estas clases de equivalencia para que $X = \bigcup_{i}A_i$ (por cierto, creo que $|A|$ sería la órbita de $X$ ).

El número de órbitas se puede contar con Lemma de Burnside

Answer 2

Para eliminar el reetiquetado, puede reetiquetar la cuadrícula de forma que la primera fila sea 123/456/789. En el ejemplo, la cadena de sustitución "473682591" hará que la primera fila sea "123456789". Es decir, sustituye el 1 por el 4, el 2 por el 7, y así sucesivamente. Elimina las permutaciones de pilas y columnas.

Para eliminar las permutaciones de bandas y filas, ordene las filas según la primera columna en orden ascendente, manteniendo cada fila en su banda respectiva, y posiblemente cambiando las bandas del medio y del fondo. Así, la columna de la izquierda se añadiría a la forma canónica.

En el ejemplo, la columna de la izquierda se habría reetiquetado como 147/965/832. Hay que reordenar las bandas y las filas para que la columna sea 147/238/569.

Hay que añadir más celdas para que la combinación de todas ellas dé lugar a un tablero único. No sé cuántas celdas más harían falta ni qué ubicaciones serían las más adecuadas. (Tal vez, todas las diagonales de cada bloque de 3x3).

Por último, hay que agruparlos en clases equivalentes. Cada grupo se basaría en la permutación de pilas y columnas y la transposición de columnas y filas (6 x 6x6x6 x 2) de una. Elige la menos ordenada para representar el grupo. El menor ordenado (columna izquierda) es 145/236/789.