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

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

О проекте 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.06.2008 23:27