Distributed Computing team of Ukraine | Ukraine - Українська Команда Розподілених Обчислень | Ukraine - Украинская Команда Распределённых Вычислений - Описи проектів

https://distributed.org.ua/index.php?go=Pages&in=view&id=155		 Распечатать

Про проект Sudoku



Версия на русском
Автор - Mad



Про проект Sudoku

Ця стаття - переклад сторінки про проект з офіційного сайту.


Судоку - дуже популярна головоломка, лише пошукайте в Google, і отримаєте опис, програми та ще багато чого. Важлива річ про судоку - завжди існує рішення, і це рішення має бути унікальним! Написати програму, яка знаходить це рішення, не дуже важко, і Ви можете знайти багато таких програм в Internet. У звичайному судоку (з газет та ін.) близько 25-30 даних чисел. Зазвичай судоку тим складніше, чим менше даних чисел. Але будьте обережні, це не універсальне правило: існують складні судоку з багатьма даними числами, і легкі лише з декількома даними числами.

Цікаве питання - як мало заданих чисел достатньо для того, щоб судоку мало унікальне рішення. Тривіальна нижня межа - 8: припустимо, що дано лише 7 чисел. Тоді в будь-якому рішенні ви можете обміняти всі входження двох не даних цифр, і тому є завжди як мінімум два різні рішення. Дивно, але поки що математичними міркуваннями не було знайдено жодного кращого нижнього кордону. Всі відомі мінімальні судоку з унікальним рішенням мають 17 даних чисел, а тут - зібрання понад 41000 таких головоломок (колекція ще зростає).

Тому поточний діапазон для найменшого числа ключів (даних чисел), які головоломка судоку (з одним унікальним рішенням) може мати, - з 8 до 17. Мета нашого проекту - закрити цей проміжок. З цією метою ми починаємо з 92248 наборів з 8 первинних даних чисел (цифри 1-8, що представляють усі комбінації щодо симетрії, перенумерації тощо), розширюємо їх, додаючи більше даних чисел, і перевіряємо на унікальність. (Детальніший математичний опис нашого підходу очікується.)

Протягом першої фази оцінки нашої програми ми змогли показати, що має бути як мінімум 11 чисел. Тому поточний діапазон - 11..17. Використовуючи розподілені обчислення, наш метод крок за кроком збільшить нижню межу, доки або один користувач знайде новий мінімальний приклад, або ми зможемо показати, що жодних прикладів не існує аж до 16 заданих чисел включно.


Кілька зауважень:

Інший підхід, щоб довідатись, чи 17 - це правильна відповідь, - перевірити будь-яку завершену сітку судоку на головоломку з 16 ключами, див. тут. На жаль, є дуже багато (завершених) судоку (5.472.730.538 рішень, беручи до уваги симетрії та ін., див. наприклад тут, тому цей метод узяв би тривалий час.
Трохи математики про судоку можна знайти на www.afjarvis.staff.shef.ac.uk
І наостанок, не пропустіть це.


Обговорення цього проекту у нас на форумі. Там є також інформація, як приєднатися до команди України.


| 08.06.2008 00:00