ГОЛОВОЛОМКИ СУДОКУ
О. ЛЕОНТЬЕВА.
СУДОКУ - новомодная японская головоломка в виде латинского магического квадрата. СУ по-японски означает "цифра", а ДОКУ - "стоящая отдельно". По сути - это цифровой пасьянс: требуется заполнить клетки таблицы 9x9, поделенной на 9 квадратов 3x3, цифрами от 1 до 9 так, чтобы в каждой строке, в каждом столбце и в каждом выделенном квадрате 3x3 каждая цифра встречалась бы только один раз. Например:
Рис.1.
Прообраз судоку без деления на отдельные области встречается в работах Леонарда Эйлера (1707-1783) о магических квадратах (см. "Наука и жизнь" № 11, 1972 г. и № 4, 1973 г.). Головоломка в ее современном виде впервые была напечатана в американском журнале "Делл пенсл Пазлс" в 1979 году. Ее автор - архитектор Ховард Гарнс. А после того как в прошлом году британская газета "Таймс" опубликовала статью "Судоку", началось триумфальное шествие головоломки по всему миру. Судоку начали печатать не только специализированные, но и массовые газеты и журналы.
Рассмотрим сетку судоку с математической точки зрения. Возникает вопрос: сколько всевозможных расстановок в ней цифр существует? С помощью компьютера подсчитали: 6 670 903 752 021 072 936 960 расстановок - в этом независимо убедились Фразер Ярвис из университета Шеффилда и Бертран Фелгенхауэр из дрезденской Высшей технической школы. В каждой из расстановок можно использовать миллиарды комбинаций, выбирая набор задающих цифр, то есть потенциальное количество различных задач судоку невообразимо велико.
Профессионально составленные головоломки должны иметь поэтапное решение, когда в результате каждого логического хода вписывается очередная новая цифра. Если рассматривать самые простые ходы, то их, по сути, только два. И каждый следующий шаг решения служит ответом на вопрос: "Какая цифра может стоять в этой клетке?" или "Где в этом ряду (области) находится такая-то цифра?". Применительно к сетке на рис.1 в качестве ответа на первый вопрос может быть отыскание числа на пересечении верхней строки и четвертого ряда. Цифры 1, 2, 3, 4, 5, 6, 8 и 9 отпадают: они уже имеются или в первой горизонтали, или в четвертой вертикали. Значит, здесь должна стоять цифра 7. Пример второго вопроса - где в верхнем ряду может находиться 2? Не в первом и не во втором квадрате, то есть только в предпоследней клетке. Как правило, этих двух вопросов и ответов на них вполне достаточно для решения судоку. Правда, порой следующий ход хоть и существует, но не бросается в глаза - требуется некоторое время, чтобы его увидеть. Поэтому можно говорить, что судоку бывают более или менее сложными. Разумеется, есть и гораздо более хитрые рассуждения, состоящие из нескольких предположений и цепочки выводов. Даже имеются сайты для любителей судоку, где подробно классифицируются методы решения. Некоторые советуют просто мелко записывать в каждую клетку все цифры, которые в ней могут находиться, и постепенно их вычеркивать.
Опытный программист без труда сможет написать судоку-генератор - программу, производящую головоломки, имеющие логическое решение. Именно такие судоку можно увидеть в большинстве газет и журналов. Однако среди знатоков особо ценятся судоку, сделанные вручную, - в их решении есть определенные красота и изящество, которые не может обеспечить ни один компьютер.
Часто задающие цифры судоку образуют некоторый орнамент. В сетке на рис.2 эти цифры складываются в буквы "Н и Ж" - инициалы журнала "Наука и жизнь".
Рис.2.
Изучение головоломки позволяет придумать множество исследовательских задач на базе судоку.
Задача
Программист проверяет правильность заполнения сетки судоку. Для этого он убеждается, что каждая из девяти цифр встречается в сетке ровно девять раз и что в каждом столбике, каждой строке и каждом выделенном квадрате сумма цифр равна 45. Достаточно ли такого алгоритма для гарантированной проверки?
Рекорды судоку
Можно попытаться составить книгу рекордов судоку. Вот некоторые возможные "номинации" в ней:
Судоку с единственным решением и наименьшим числом задающих цифр.
Судоку с наименьшей суммой задающих цифр.
Судоку с наименьшим числом задающих цифр при условии, что на главных диагоналях все цифры тоже должны быть различны.
Судоку с максимальным числом решений при условии, что добавление еще только одной задающей цифры делает решение единственным.
Вслед за ставшими уже классическими судоку появились десятки их вариаций. В них используются сетки другого размера, области имеют не квадратную форму, предлагаются дополнительные условия.
Приведем три вариации.
Судоку 8x8
Заполните клетки числами от 1 до 8, чтобы в каждой строке, каждом столбике и каждой выделенной жирным области все числа были различны.
Судоку больше-меньше
В сетке не указано ни одной задающей цифры. Зато расставлены знаки "больше" и "меньше" между всеми соседними числами каждой области.
Судоку в треугольниках
Заполните треугольные клетки цифрами от 1 до 9, чтобы в каждом из шести больших треугольников и каждой линии (даже если линия состоит из двух отдельных участков) по всем трем направлениям все цифры были разными.
Подобно чемпионатам по сборке кубика Рубика, стали проходить чемпионаты мира по решению судоку. Прошел и первый чемпионат России.
ЧЕМПИОНАТ РОССИИ ПО СУДОКУ
Двенадцатого февраля 2006 года в Центре внешкольной работы в Митине прошел первый очный чемпионат России по судоку. Организовал его российский клуб ценителей головоломок "Диоген". В чемпионате приняли участие двадцать сильнейших решателей головоломок. Любители судоку, не имевшие возможности приехать в Москву, смогли посоревноваться в реальном времени по Интернету.
Соревнования состояли из двух туров по одному часу. Решив задание, участник должен был выписать три ключевые цифры в форму. Именно по этим ключам проверялась правильность решения.
В первом туре предлагались стандартные судоку в сетках разного размера, всего - десять заданий. Лучший результат в первом туре - 290 баллов из 300 - у Андрея Богданова из Подмосковья. Приводим задания полностью, чтобы каждый мог оценить свой уровень.
Во втором туре предлагались вариации судоку - задачи с дополнительными условиями, всего - шесть заданий. Приведем два из них:
Судоку-1
Заполните сетку по правилам судоку. Жирная черта стоит между всеми парами соседних чисел, отличающимися ровно на 1.
Судоку-суммы
Заполните сетку по правилам судоку. Числа вне сетки указывают сумму первых трех цифр в соответствующем ряду.
Несколько участников смогли решить пять заданий из шести.
После двух туров между тремя победителями - Андреем Лемешем, Андреем Богдановым и Риадом Ханмагомедовым - состоялся финальный поединок из пяти заданий. Время, отведенное для решения каждому участнику, было пропорционально количеству набранных им очков. Переходя от решения одного задания к другому, финалисты передвигались по партам к победному финишу, что представляло весьма азартное зрелище.
Первым достиг "финишной ленточки" москвич Риад Ханмагомедов. Кроме того, он единственный из троих верно решил все пять задач, и поэтому его победа абсолютно заслужена и справедлива. Главным призом - тортом в виде судоку победитель угостил всех участников во время последующего чаепития.
Немного подробнее об Интернет-версии чемпионата. Сайт клуба "Диоген" www.diogen.h1.ru пользуется популярностью не только у российских ценителей головоломок, но и во всем мире, поэтому на информацию о предстоящем чемпионате откликнулись десятки любителей судоку. География участников говорит сама за себя: Япония, Турция, Австралия, США, Чехия, Босния и Герцоговина, Хорватия, Польша, разумеется, Россия, Белоруссия, Украина и даже Малайзия.
Технически соревнования происходили так: в момент начала каждого тура очного чемпионата в сети становились доступными файлы с условиями. Как и в очных соревнованиях, каждый должен был по окончании часа, отведенного на решение, отправить заполненную форму с тремя ключевыми цифрами.
Конечно, поскольку имеются электронные программы по решению судоку и невозможно проверить, решал участник в одиночку или на него работала целая команда, результаты он-лайн соревнований могут быть только неофициальными. Тем не менее приятно отметить, что четверо участников: Shinichi Aoki, Taro Arimatsu, Daisuke Takei и Hideaki Jo (все - из Японии) - справились со всеми заданиями обоих туров.
Сайты любителей судоку:
http://www.play-sudoku.de/index.php?ru_index сайт с головоломками и форумом;
http://en.wikipedia.org/wiki/Sudoku много информации о судоку, задачи;
http://www.sudocu.com на английском языке; есть форум, общение решателей и программистов судоку.
Читайте в любое время
