Граф судоку

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

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

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

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

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

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

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

Для будь-якого $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).