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
Прочитана: 8463 раза

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

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

 » Поддержка (обращайтесь) 
Folding@Home
 NikeLong246659609
 Alex266184514
 ReMMeR338177212
Rosetta@Home
 uNiUs172324149
 KoDak313871706
World Community Grid
 Dmitrio250896826
FightAIDS@Home
 RHAngel50177406
RC5/OGR
 Tamagoch53619819
 Paul B.Atton46941577
Seti@Home
 Andrey Fenchenko285577622
WebMaster
 ReMMeR338177212
 Rilian (PM)1
Поболтать
 Dead J. Dona122008482