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
И наконец, не пропустите эту ссылку.


Обсуждение этого проекта у нас на форуме. Там-же информация как присоединится к команде Украины.




Дата: Суббота, 07 Июнь 2008
Прочитана: 11156 раз

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

Вернуться назад

 » Место команды 
Медико-биологические
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
Космос
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