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

Базові властивості та приклади
На полі судоку розміру  граф судоку має  вершин, кожна має рівно  сусідів. Тому це регулярний граф. Наприклад, граф, наведений на малюнку з ігровим полем  має 16 вершин і є 7-регулярним. Для більшості видів судоку на ігровому полі  графом судоку є 20-регулярний граф із 81 вершиною.

Розв'язання головоломки та розфарбування графа
Кожен рядок, стовпець або блок головоломки судоку утворює кліку в графі судоку, розмір якої дорівнює числу символів, що використовуються в головоломці. Розфарбовування графа судоку за допомогою набору з таким числом кольорів (найменша можлива кількість кольорів для цього графа) можна інтерпретувати як головоломку. Звичайний вид головоломки судоку, в якій деякі комірки заповнено символами, а інші має заповнити гравець, відповідає задачі  для цього графа.

Алгебричні властивості
Для будь-якого , граф судоку поля  є цілим графом, що означає, що спектр його матриці суміжності складається лише з цілих чисел. Точніше, його спектр складається зі власних значень

* , із кратністю ,
* , із кратністю ,
* , із кратністю ,
* , із кратністю ,
* , із кратністю ,
* , із кратністю .

Його можна подати як граф Келі абелевої групи .

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

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

Примітки




