Граф судоку

В математике судоку граф судоку — это неориентированный граф , вершины которого представляют ячейки (пустой) головоломки судоку, а ребра — пары ячеек, принадлежащих одной строке, столбцу или блоку головоломки. Задача решения головоломки судоку может быть представлена ​​как предварительное раскрашивание расширения на этом графе. Это целочисленный граф Кэли .

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

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

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

• ${\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}}$

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

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

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