Gráfico de sudoku

Gráfica matemática de un sudoku

${\displaystyle 4\times 4}$Gráfico de sudoku

En las matemáticas del sudoku , el gráfico del sudoku es un gráfico no dirigido cuyos vértices representan las celdas de un rompecabezas de sudoku (en blanco) y cuyos bordes representan pares de celdas que pertenecen a la misma fila, columna o bloque del rompecabezas. El problema de resolver un rompecabezas de sudoku se puede representar como una extensión de precoloración en este gráfico. Es un gráfico de Cayley integral .

Propiedades básicas y ejemplos

Contar vecinos de una celda en un gráfico de Sudoku ( ) ${\displaystyle 9\times 9}$ ${\displaystyle n=3}$

En un tablero de Sudoku de tamaño , el gráfico de Sudoku tiene vértices , cada uno con exactamente vecinos. Por lo tanto, es un grafo regular . El número total de aristas es . Por ejemplo, el grafo que se muestra en la figura anterior, para un tablero, tiene 16 vértices y 56 aristas, y es 7-regular. Para la forma más común de Sudoku, en un tablero, el grafo de Sudoku es un grafo 20-regular con 81 vértices y 810 aristas. ^{[1] [2] [3]} La segunda figura muestra cómo contar los vecinos de cada celda en un tablero. ${\displaystyle n^{2}\times n^{2}}$ ${\displaystyle n^{4}}$ ${\displaystyle 3n^{2}-2n-1}$ ${\displaystyle n^{4}(3n^{2}-2n-1)/2}$ ${\displaystyle 4\times 4}$ ${\displaystyle 9\times 9}$ ${\displaystyle 9\times 9}$

Soluciones de rompecabezas y coloración de gráficos

Cada fila, columna o bloque del sudoku forma un grupo en el gráfico del sudoku, cuyo tamaño es igual al número de símbolos utilizados para resolver el rompecabezas. Una coloración gráfica del gráfico del sudoku utilizando este número de colores (el mínimo número posible de colores para este gráfico) puede interpretarse como una solución al rompecabezas. La forma habitual de un sudoku, en la que algunas celdas se rellenan con símbolos y el resto debe ser rellenado por la persona que resuelve el rompecabezas, corresponde al problema de extensión de precoloración en este gráfico. ^{[1] [2] [3]}

Propiedades algebraicas

Para cualquier , el gráfico de Sudoku de un tablero de Sudoku es un gráfico integral , lo que significa que el espectro de su matriz de adyacencia consta únicamente de números enteros. Más precisamente, su espectro consta de los valores propios ^[4] ${\displaystyle n}$ ${\displaystyle n^{2}\times n^{2}}$

• ${\displaystyle 3n^{2}-2n-1}$, con multiplicidad , ${\displaystyle 1}$
• ${\displaystyle 2n^{2}-2n-1}$, con multiplicidad , ${\displaystyle 2(n-1)}$
• ${\displaystyle n^{2}-n-1}$, con multiplicidad , ${\displaystyle 2n(n-1)}$
• ${\displaystyle n^{2}-2n-1}$, con multiplicidad , ${\displaystyle (n-1)^{2}}$
• ${\displaystyle -1}$, con multiplicidad , y ${\displaystyle n^{2}(n-1)^{2}}$
• ${\displaystyle -n-1}$, con multiplicidad . ${\displaystyle 2n(n-1)^{2}}$

Se puede representar como un gráfico de Cayley del grupo abeliano . ^[5] ${\displaystyle Z_{n}^{4}}$

Gráficos relacionados

El gráfico del Sudoku contiene como subgráfico el gráfico de la torre , que se define de la misma manera utilizando solo las filas y columnas (pero no los bloques) del tablero de Sudoku.

El gráfico de Sudoku de 20 regulares y 81 vértices debe distinguirse de un gráfico diferente de 20 regulares con 81 vértices, el gráfico de Brouwer-Haemers , que tiene grupos más pequeños (de tamaño 3) y requiere menos colores (7 en lugar de 9). ^[6]

Referencias

1. Gago-Vargas, Jesús; Hartillo-Hermoso, María Isabel; Martín Morales, Jorge; Ucha-Enríquez, José María (2006), “Sudokus y bases de Gröbner: No sólo un divertimento ”, en Ganzha, Victor G.; Mayr, Ernst W.; Vorozhtsov, Evgenii V. (eds.), Álgebra informática en informática científica, noveno taller internacional, CASC 2006, Chisinau, Moldavia, 11 al 15 de septiembre de 2006, Actas , Lecture Notes in Computer Science, vol. 4194, Springer, págs. 155–165, doi :10.1007/11870814_13, hdl : 11441/23605
2. Herzberg, Agnes M. ; Murty, M. Ram (2007), "Cuadrados de sudoku y polinomios cromáticos" (PDF) , Avisos de la American Mathematical Society , 54 (6): 708–717, MR  2327972
3. Rosenhouse, Jason ; Taalman, Laura (2011), Tomando el Sudoku en serio: las matemáticas detrás del rompecabezas de lápiz más popular del mundo , Oxford University Press, págs. 128-130
4. Sander, Torsten (2009), "Los gráficos de sudoku son integrales", Electronic Journal of Combinatorics , 16 (1): Nota 25, 7pp, doi : 10.37236/263 , MR  2529816
5. Klotz, Walter; Sander, Torsten (2010), "Gráficos integrales de Cayley sobre grupos abelianos", Electronic Journal of Combinatorics , 17 (1): Documento de investigación 81, 13pp, doi : 10.37236/353 , MR  2651734
6. Weisstein, Eric W. , "Gráfico de Brouwer-Haemers", MathWorld