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.
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]
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
^ ab 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