Граф судоку

На поле судоку размера ${\displaystyle n^{2}\times n^{2}}$, граф судоку имеет ${\displaystyle n^{4}}$ вершин, каждая имеет в точности ${\displaystyle 3n^{2}-2n-1}$ соседей. Поэтому это регулярный граф. Например, граф, представленный на рисунке с игровым полем ${\displaystyle 4\times 4}$, имеет 16 вершин и является 7-регулярным. Для большинства видов судоку на игровом поле ${\displaystyle 9\times 9}$ графом судоку является 20-регулярный граф с 81 вершиной[1][2].

Каждая строка, столбец или блок голововомки судоку образует клику в графе судоку, размер которой равен числу символов, используемых в головоломке. Раскраска графа судоку с помощью набора с таким числом цветов (минимальное возможное число цветов для этого графа) может интерпретироваться как решение головоломки. Обычный вид головоломки судоку, в которой некоторые ячейки заполнены символами, а остальные должны быть заполнены игроком соответствует задаче расширения предварительной раскраски для этого графа [1][2].

Для любого ${\displaystyle n}$, граф судоку поля ${\displaystyle n^{2}\times n^{2}}$ является целым графом, что означает, что спектр его матрица смежности состоит только из целых числе. Более точно, его спектр состоит из cобственных значений[3]

• ${\displaystyle 3n^{2}-2n-1}$, с кратностью ${\displaystyle 1}$,
• ${\displaystyle 2n^{2}-2n-1}$, с кратностью ${\displaystyle 2(n-1)}$,
• ${\displaystyle n^{2}-n-1}$, с кратностью ${\displaystyle 2n(n-1)}$,
• ${\displaystyle n^{2}-2n-1}$, с кратностью ${\displaystyle (n-1)^{2}}$,
• ${\displaystyle -1}$, с кратностью ${\displaystyle n^{2}(n-1)^{2}}$,
• ${\displaystyle -n-1}$, с кратностью ${\displaystyle 2n(n-1)^{2}}$.

Он может быть представлен как граф Кэли абелевой группы ${\displaystyle Z_{n}^{4}}$[4].

Граф судоку содержит в качестве подграфа ладейный граф, который определяется тем же способом, но только на строках и столбцах (но не на блоках) игрового поля судоку.

20-регулярный 81-вершинный граф судоку следует отличать от другого 20-регулярного графа с 81 вершинами, графа Брауэра — Хемерса, который имеет меньшие клики (размера 3) и требует меньшего числа цветов (7 вместо 9)[5].