График судоку

$4\times 4$ График судоку

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

Основные свойства и примеры

Подсчет соседей ячейки на $9\times 9$ График судоку ( $n=3$)

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

Решение головоломок и раскраска графиков

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

Алгебраические свойства

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

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

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

Связанные графики

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

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