Graphe du sudoku

$4\times 4$ Graphique du sudoku

Dans le domaine mathématique du Sudoku, on utilise un concept appelé le graphe 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

Compter les voisins d'une cellule sur un $9\times 9$ Graphique Sudoku ( $n=3$ )

Sur un tableau Sudoku de taille $n^{2}\times n^{2}$, le graphique Sudoku a $n^{4}$ sommets, chacun avec exactement $3n^{2}-2n-1$ voisins. C'est donc un graphique régulier . Le nombre total d'arêtes est $n^{4}(3n^{2}-2n-1)/2$ . Par exemple, le graphique présenté dans la figure ci-dessus, pour un $4\times 4$ conseil d'administration, a 16 sommets et 56 arêtes et est 7-régulier. Pour la forme la plus courante de Sudoku, sur un $9\times 9$ Sur ce tableau, le graphe Sudoku est un graphe régulier de 20 avec 81 sommets et 810 arêtes. La deuxième figure montre comment compter les voisins de chaque cellule dans un $9\times 9$ conseil.

Solutions de puzzle et coloration de graphiques

Chaque ligne, colonne ou bloc du puzzle Sudoku forme une clique dans le graphique Sudoku, dont la taille est égale au nombre de symboles utilisés pour résoudre le puzzle. Une coloration graphique du graphique Sudoku utilisant ce nombre de couleurs (le nombre minimum de couleurs possible pour ce graphique) 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 graphique.

Propriétés algébriques

Pour toute $n$, le graphique Sudoku d'un $n^{2}\times n^{2}$ Le tableau Sudoku 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}$ .

Graphiques 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).