1. 8.2. судоку завдання п'ятірки
2. Короткі теоретичні відомості
3. Розбори деяких завдань п'ятірки
4. Список літератури і джерел

8.2. судоку

завдання п'ятірки

1. Су-су-судоку
2. судоку
3. судоку
4. судоку
5. судоку

По завершенню тижні можна в цій темі акумульовано висловитися або обговорити.

Короткі теоретичні відомості

8.2. судоку

Рекомендуємо для початку ознайомиться з описом самої головоломки і методами її вирішення в джерелах [2] і [3], зазначених у посиланнях на літературу і джерела, і тільки після цього приступати до ознайомлення з матеріалом, розташованим нижче.

Завдання можна віднести як до теми "Пошук з поверненням (перебір і методи його відсікання)", так і до теми "Складні завдання на графах". Завдання вважається NP -повної.

Матеріал, розташований нижче, міститься в [1] в розділі 7. комбінаторний пошук і евристичні методи.

Головоломки Судоку дуже популярні в усьому світі. Багато газет друкують їх у своїх денних випусках, випущені цілі збірки цих головоломок. Про популярність судоку можна судити по тому факту, що авіакомпанія British Airways видала наказ, що забороняє бортпровідників вирішувати їх під час зльоту і посадки. Я навіть помітив, що під час моїх лекцій по алгоритмам в задніх рядах аудиторії досить багато працюють над вирішенням цих головоломок.

Що ж являє собою судоку? У найбільш поширеною формою це квадрат розміром 9 × 9 клітинок, деякі з яких містять цифри від 1 до 9, а решта порожні. Рішення головоломки полягає в заповненні порожніх клітинок таким чином, щоб кожен рядок, кожен стовпець і кожен малий квадрат розміром 3 × 3 клітинки, містили всі цифри від 1 до 9, без повторень і без пропусків. Приклад головоломки судоку і її рішення показані на рис. 8.2.1.

Мал. 8.2.1: Головоломка судоку (зліва) і її рішення (справа)

Судоку добре піддається вирішенню методом перебору з поверненням. Ми використовуємо головоломку на рис. 8.2.1 для кращої ілюстрації цього алгоритмічного методу. Простором станів будуть порожні клітинки, кожна з яких буде в кінцевому підсумку заповнена будь-якої цифрою. Кандидатами на заповнення порожньої клітинки (i, j) є цілі числа від 1 до 9, яких немає в рядку i, стовпці j і в малому квадраті 3 × 3, що містить клеточкку (i, j). Повернення осущетсвляется, коли більше немає кандидатів на заповнення клітинки.

Вектор рішення a, підтримуваний процедурою backtrack, може містити в кожній клітинці тільки одне ціле число. Цього достатньо для зберігання вмісту клітинки (числа 1 - 9), але не для зберігання її координат. Тому для зберігання позицій ходів ми використовуємо окремий масив boardtype. Основні структури даних для підтримки нашого рішення визначені в лістингу 8.2.1:

Лістинг 8.2.1.Визначення основних структур даних

#define DIMENSION 9 / * Дошка розміром 9х9 * /
#define NCELLS DIMENSION * DIMENSION / * На дошці 9х9 є 81 клітинка * /
typedef struct {
int x, y; / * Координати x і y клітинки * /

} Point;

typedef struct {
int m [DIMENSION + 1] [DIMENSION + 1]; / * Матриця вмісту дошки * /
int freecount; / * Скільки клітинок залишилося порожніми? * /
point move [NCELLS + 1]; / * Як були заповнені клітинки? * /
} Boardtype;

На черговому кроці гри ми повинні вибрати відкриту клітинку, яку хочемо заповнити наступної (процедура next_square), потім визначити числа, які є кандидатами на заповнення цієї клітинки (процедура possible_values). Ці процедури (лістинг 8.2.2), по суті, ведуть облік ходів, хоча деякі деталі їх роботи можуть сильно вплинути на продуктивність.

/ * Позиція наступного ходу * /
int i; / Лічильник /
bool possible [DIMENSION + 1]; / * Які числа можна використовувати * /
next_square (& x, & y, board); / * Для наступної клітинки? * /
board-> move [k] .x = x; / * Збереження вибору наступної клітинки * /
board-> move [k] .y = y;
* ncandidates = 0;
if ((x <0) && (y <0)) return; / * Помилка: немає допустимих ходів * /
possible_values (x, y, board, possible);
for (i = 0; i <= DIMENSION; i ++)
if (possible [i] == TRUE) {
c [* ncandidates] = i;
* ncandidates = * ncandidates + 1;
}
}

Структури даних ігровий дошки необхідно оновлювати, щоб відображати заповнені клітинки значенням кандидата, а також очищати заповнені клітинки в разі необхідності повернення з даної позиції. для виконання цих оновлень використовуються процедури make_move і unmake_move (лістинг 8.2.3), які викликаються безпосередньо з процедури backtrack.

Однією з важливих завдань, що виконуються цими процедурами, є відстеження кількості залишаються на дошці порожніх клітинок. Рішення знайдено, коли на дошці немає більше порожніх клітинок:

Лістинг 8.2.4.Процедура відстеження порожніх клітинок
is_a_solution (int a [], int k, boardtype * board)
{
if (board-> freecount == 0)
return (TRUE);
else
return (FALSE);
}

Коли рішення знайдено, встановлюється глобальний прапор finished, що служить сигналом до припинення пошуку і висновку рішення. Це можна робити, не побоюючись ніяких наслідків, тому що класичні головоломки судоку можуть мати тільки одне рішення. Головоломки з розширеною інтерпретацією можуть мати величезну кількість рішень. Справді, для порожній головоломки (тобто без початкових цифр) існує +6670903752021072936960 рішень. Щоб не переглядати всі ці рішення, ми і припиняємо пошук:

Лістинг 8.2.5.Завершення пошуку і обробка рішення
process_solution (int a [], int k, boardtype * board)
{
print_board (board);
finished = TRUE;
}

Ця процедура завершує нашу програму, але залишається необхідність в написанні процедур для визначення наступної клітинки (next_square) і пошуку кандидатів на заповнення цієї клітинки (possible_values). для вибору наступної клітинки для заповнення підходять два способи.

• Вибір довільній клітини. Вибираємо першу-ліпшу порожню клітинку. Нам все одно, яку вибирати, оскільки немає очевидних підстав вважати, що один евристичний метод виявиться кращий за інший.
• Вибір клітинки з найменшою кількістю кандидатів. При пов му підході ми перевіряємо кількість кандидатів, що залишилися на заповнення кожної порожній клітини (i, j), тобто кількість цифр, які ще не використовуються ні в рядку i, ні в стовпці j, ні в малому квадраті, що містить клітинку (i, j). За результатами цих досліджень ми вибираємо клітинку з найменшою кількістю кандидатів на її заповнення.

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

Якщо для клітинки з найменшою кількістю кандидатів є два кандидати, то ймовірність вгадати правильну з них дорівнює 1/2, в порівнянні з імовірністю 1/9 вгадати правильного кандидата для клітинки без обмежень на кількість кандидатів. Зменшивши середня кількість кандидатів для кожної клітинки, наприклад, з трьох до двох, ми отримаємо величезне підвищення продуктивності, тому що це зменшення дає прогресивний виграш для кожної наступної клітинки. Наприклад, якщо нам потрібно заповнити тільки 20 клітинок, то два кандидати на кожну клітинку дають 1048576 можливих варіантів заповнення. А рівень розгалуження, рівний 3, для кожної з 20 клітинок дає в 3000 разів більше варіантів!

Вибрати можливих кандидатів для кожної клітинки можна двома способами:

• Локальний вибір. Наш алгоритм перебору з поверненням видасть правильний результат, якщо процедура генерування кандидатів на заповнення клітинки (i, j), тобто процедура possible_values, діє очевидним чином і надає на вибір цифри від 1 до 9, яких ще немає в цьому рядку, стовпці або малому квадраті.
• Перегляд вперед. Що буде, якщо для нашого поточного часткового вирішення існує якась інша порожня клітинка, для якої локальні критерії не залишають кандидатів? У такому випадку дане часткове рішення неможливо довести до повного. Виходить, що ситуація навколо якоїсь іншої клітинки дає дейстітельно кількість кандидатів для клітинки (i, j) рівним нулю!

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

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

У табл. 8.1 показано кількість викликів процедури визначення рішення is_a_solution для всіх чотирьох комбінацій вибору наступної клітинки і можливих кандидатів для трьох різних рівнів складності головоломки судоку.

Умова відсікання
Рівень складності
next_square possible_values ​​Низький Середній
Високий довільне значення
локальний вибір 1904832 863305 програма не завершена
довільне значення майбутній вибір
127 142 12507212 найменшу кількість кандидатів локальний вибір
48 84 1243848 найменшу кількість кандидатів майбутній вибір 48 65 10374

Таблиця 8.1: Кількість кроків для отримання рішення при різних стратегіях відсікання

• Головоломка низького рівня складності призначена для вирішення людиною, а не комп'ютером. Насправді, моя програма вирішила її без єдиного повернення, коли для наступної клітинки вибиралася клітинка з найменшою кількістю кандидатів.
• Головоломка середньої складності виявилася не під силу жодному з вийшли у фінал Світового чемпіонату з судоку в березні 2006 року. Але для пртограмми знадобилося лише кілька повернень, щоб вирішити цю головоломку.
• Головоломка високого рівня складності показана на рис. 8.2.1 і містить лише 17 заповнених клітинок. Це найменше відоме кількість заповнених клітинок на всіх примірниках завдання, яке дає тільки одне повне рішення.

Що вважається головоломкою високого рівня складності, залежить від пріменемого для її вирішення евристичного алгоритму. Безсумнівно, серед Ваших знайомих є люди, яким теорія здається важче, ніж практичне програмування, а є і такі, хто думає інакше. Алгоритм A цілком може вважати, що завдання I1 легше, ніж завдання I2, в той час як алгоритм B бачить труднощі цих завдань в зворотному порядку.

Які висновки ми можемо зробити з цих експериментів? Попереднє дослідження подальших варіантів рішення з целбю відсікання тупикових є найкращим способом розрідження простору пошуку. Без застосування цієї операції ми ніколи не вирішили б головоломку найвищого рівня, а більш легкі головоломки вирішили б в тисячі разів повільніше.

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

При довільному виборі наступної клітинки рішення головоломки на рис. 8.2.1 зайняло майже годину (48:44). Безсумнівно, моя програма вирішила більшість інших головоломок швидше, але головоломки судоку призначені для вирішення людьми за набагато менший час. Вибір клітинки з найменшою кількістю кандидатів дозволив скоротити час пошуку більш ніж в 1200 разів.

Ось так проявляється вся міць відсікання тупикових варіантів пошуку. Використання навіть простих стратегій відсікання може значно зменшити час виконання.

Розбори деяких завдань п'ятірки

Замість розбору завдань пропонується уважно ознайомиться зі статтею Данила Сагунова і Ігоря Бєляєва " танцюючі ланки ".

Список літератури і джерел

1. С.Скіена. Алгоритми. Керівництво по розробці. - 2-е вид .: Пер. з англ. - СПб .: БХВ-Петербург, 2011. - 720 с .: іл.
2. матеріал з Вікіпедії - вільної енциклопедії
3. Методика рішення головоломок судоку