Граф судоку

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

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

Базові властивості та приклади

На полі судоку розміру $n^2\times n^2$ граф судоку має $n^4$ вершин, кожна має рівно $3n^2-2n-1$ сусідів. Тому це регулярний граф. Наприклад, граф, наведений на малюнку з ігровим полем $4\times 4$ має 16 вершин і є 7-регулярним. Для більшості видів судоку на ігровому полі $9\times 9$ графом судоку є 20-регулярний граф із 81 вершиноюШаблон:R.

Розв'язання головоломки та розфарбування графа

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

Алгебричні властивості

Для будь-якого $n$, граф судоку поля $n^2\times n^2$ є цілим графом, що означає, що спектр його матриці суміжності складається лише з цілих чисел. Точніше, його спектр складається зі власних значеньШаблон:R

• $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$Шаблон:R.

Пов'язані графи

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

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