Graphe du sudoku

Un sudoku de 4 cases de côté.

Le graphe du sudoku est un concept utilisé dans le domaine mathématique du sudoku.

Ce graphe est non orienté et ses sommets correspondent aux cellules d'un sudoku non rempli. Les arêtes de ce graphe relient les cellules qui sont soit sur la même ligne, soit dans la même colonne, soit dans le même bloc du puzzle. La résolution d'un sudoku peut être vue comme une application d'une extension de précoloration sur ce graphe. De plus, ce graphe est un exemple de graphe de Cayley intégral.

Propriétés de base et exemples

Un sudoku de 9 cases de côté, où $n=3$.

Sur un tableau sudoku de taille $n^{2}\times n^{2}$, le graphe sudoku a $n^{4}$ sommets, chacun avec exactement $3n^{2}-2n-1$ voisins. C'est donc un graphe régulier. Le nombre total d'arêtes est $n^{4}(3n^{2}-2n-1)/2$.

Par exemple, le graphe présenté dans la figure ci-dessus, pour un tableau de $4\times 4$ cases, a 16 sommets, 56 arêtes et est régulier. La forme la plus courante de sudoku ($9\times 9$ cases) comporte 81 sommets et 810 arêtes.

Solutions de puzzle et coloration de graphes

Chaque ligne, colonne ou bloc du puzzle sudoku forme une clique dans le graphe sudoku, dont la taille est égale au nombre de symboles utilisés pour résoudre le puzzle. Une coloration de graphe du graphe sudoku utilisant ce nombre de couleurs (le nombre minimum de couleurs possible pour ce graphe) peut être interprétée comme une solution au puzzle. La forme habituelle d'un puzzle sudoku, dans lequel certaines cellules sont remplies de symboles et le reste doit être rempli par la personne qui résout le puzzle, correspond au problème d'extension de précoloration sur ce graphe.

Propriétés algébriques

Pour tout $n$, le graphe d'un tableau de sudoku de $n^{2}\times n^{2}$ est un graphe intégral, ce qui signifie que le spectre de sa matrice de contiguïté est constitué uniquement d'entiers. Plus précisément, son spectre est constitué des valeurs propres.

• $3n^{2}-2n-1$, avec multiplicité $1$,
• $2n^{2}-2n-1$, avec multiplicité $2(n-1)$,
• $n^{2}-n-1$, avec multiplicité $2n(n-1)$,
• $n^{2}-2n-1$, avec multiplicité $(n-1)^{2}$,
• $-1$, avec multiplicité $n^{2}(n-1)^{2}$ et
• $-n-1$, avec multiplicité $2n(n-1)^{2}$.

Graphes associés

Le graphe sudoku contient comme sous-graphe le graphe de la tour, qui est défini de la même manière en utilisant uniquement les lignes et les colonnes (mais pas les blocs) du tableau sudoku.

Le graphe sudoku à 20 sommets réguliers à 81 sommets doit être distingué d'un autre graphe régulier à 20 sommets sur 81 sommets, le graphe de Brouwer-Haemers, qui a des cliques plus petites (de taille 3) et nécessite moins de couleurs (7 au lieu de 9).