ua     ru    Sitemap   Sitemap     | Пошук... |       Сайт відкрито 14.12.2005

Ukraine - Distributed Computing Team

 

 » Навігація 
  Новини
  Новини (Архів)
  Описи проектів
  Опитування
  Архіви

  Форум
  Форум (PDA)

 » Статті 


       Описи проектів 
Начало раздела > Sudoku

Про проект 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 Червень 2008
Прочитана: 4055 раз

Распечатать Распечатать    Переслать Переслать    В избранное В избранное

Повернутися назад

 » Положення команди 
Медико-біологічні
Correlizer
47
DrugDiscovery@Home
9
Fightaids@Home
40
Folding@Home
56
Gpugrid.net
50
Help Cure Muscular Dystrophy
40
Help Conquer Cancer
40
Help Fight Childhood Cancer
40
Human Proteome Folding (Phase 2)
40
Lattice Project
20
Malariacontrol.net
47
NRG@home (Najmanovich Research Group)
26
Poem@Home
32
Ps3grid.net
50
RNA World
47
Rosetta@Home
27
World Community Grid
40
Математика
Abc@Home
13
Collatz Conjecture
75
EulerNet
10
Gimps (Great Internet Mersenne Prime Search)
29
Mersenne@home
78
NFS@Home (Number Field Sieve)
55
OGR-27
11
OPTIMA@HOME
35
primaboinca
44
Primegrid
40
Seventeen Or Bust
16
Seventeen Or Bust-Sieve
17
WEP-M+2 Project (Wanless)
40
Криптографія
DistrRTgen
68
Enigma@Home
52
RC5-72
22
Фізика
Einstein@Home
49
IBERCIVIS
1
Leiden Classical
61
Lhc@Home
33
Magnetism@Home
2
Muon1-DPAD
31
Spinhenge@Home
39
Хімія
QMC@Home
44
Kосмос
Constellation@home
51
Cosmology@Home
44
Milkyway@Home
48
Orbit@Home
27
SETI@Home
90
Планета земля
Climate Prediction
43
La Red de Atrapa Sismos
7
Quake Catcher Network
64
Radioactive@Home
12
Virtual Prairie (ViP)
24
Штучний інтелект
FreeHAL@Home
24
Neurona@Home
21
Інтернет
Majestic-12
4
Рендеринг
Burp
34
Luxrenderfarm@home
0
ORE (Open Rendering Environment)
40
Ігрові проекти
Chess960@Home
95
sudoku@vtaiwan
16
Клікери і трекери
Marmot Project
239
Whatpulse
83
Мікс
AlmereGrid
24
Pirates@Home
9
Sztaki Desktop Grid
58
Yoyo@Home
37