Граф судоку

[math]\displaystyle{ 4\times 4 }[/math] граф судоку

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

Базовые свойства и примеры

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

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

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

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

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

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

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

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

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

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