Граф судоку

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

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

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

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

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

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

Для любого граф судоку доски судоку является интегральным графом , что означает, что спектр его матрицы смежности состоит только из целых чисел. Точнее, его спектр состоит из собственных значений ^[4] $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}$

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

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

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

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

Ссылки

^ аб Гаго-Варгас, Иисус; Хартильо-Эрмосо, Мария Изабель; Мартин-Моралес, Хорхе; Уча-Энрикес, Хосе Мария (2006), «Основы Судокуса и Грёбнера: не только развлечение » , в Ганже, Виктор Г.; Майр, Эрнст В.; Ворожцов, Евгений В. (ред.), Компьютерная алгебра в научных вычислениях, 9-й международный семинар, CASC 2006, Кишинев, Молдова, 11–15 сентября 2006 г., Труды , конспекты лекций по информатике, том. 4194, Springer, стр. 155–165, doi : 10.1007/11870814_13, hdl : 11441/23605
^ ab Herzberg, Agnes M. ; Murty, M. Ram (2007), «Квадраты судоку и хроматические многочлены» (PDF) , Notices of the American Mathematical Society , 54 (6): 708–717, MR 2327972
^ ab Rosenhouse, Jason ; Taalman, Laura (2011), Серьёзное отношение к судоку: математика, лежащая в основе самой популярной в мире головоломки с карандашом , Oxford University Press, стр. 128–130
^ Сандер, Торстен (2009), «Графы судоку являются целостными», Электронный журнал комбинаторики , 16 (1): Примечание 25, 7 стр., doi : 10.37236/263 , MR 2529816
^ Клотц, Вальтер; Сандер, Торстен (2010), «Целостные графы Кэли над абелевыми группами», Электронный журнал комбинаторики , 17 (1): Исследовательская статья 81, 13 стр., doi : 10.37236/353 , MR 2651734
^ Вайсштейн, Эрик В. , «График Брауэра-Хемерса», MathWorld