Gráfico de Sudoku

En las matemáticas del Sudoku , el grafo de Sudoku es un grafo no dirigido cuyos vértices representan las celdas de un rompecabezas de Sudoku (en blanco) y cuyas aristas 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 grafo. Es un grafo de Cayley integral .

En un tablero de Sudoku de tamaño${\displaystyle n^{2}\times n^{2}}$, el gráfico de Sudoku tiene${\displaystyle n^{4}}$vértices , cada uno con exactamente${\displaystyle 3n^{2}-2n-1}$vecinos. Por lo tanto, es un grafo regular . El número total de aristas es${\displaystyle n^{4}(3n^{2}-2n-1)/2}$. Por ejemplo, el gráfico que se muestra en la figura anterior, para un${\displaystyle 4\times 4}$tablero, tiene 16 vértices y 56 aristas, y es 7-regular. Para la forma más común de Sudoku, en un${\displaystyle 9\times 9}$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${\displaystyle 9\times 9}$junta.

Cada fila, columna o bloque del rompecabezas de Sudoku forma una camarilla en el grafo de Sudoku, cuyo tamaño es igual al número de símbolos utilizados para resolver el rompecabezas. Una coloración del grafo de Sudoku utilizando este número de colores (el número mínimo posible de colores para este grafo) puede interpretarse como una solución al rompecabezas. La forma habitual de un rompecabezas de 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 grafo. ^{[ 1 ] [ 2 ] [ 3 ]}

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

• ${\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${\displaystyle n^{2}(n-1)^{2}}$, y
• ${\displaystyle -n-1}$, con multiplicidad${\displaystyle 2n(n-1)^{2}}$.

Puede representarse como un grafo de Cayley del grupo abeliano.${\displaystyle Z_{n}^{4}}$. ^{[ 5 ]}

El grafo de Sudoku contiene como subgrafo el grafo 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 grafo de Sudoku 20-regular de 81 vértices debe distinguirse de otro grafo 20-regular de 81 vértices, el grafo de Brouwer-Haemers , que tiene camarillas más pequeñas (de tamaño 3) y requiere menos colores (7 en lugar de 9). ^{[ 6 ]}