Цифровой журнал «Компьютерра» № 8
Шрифт:
Сумма чисел в каждой строке, столбце и на диагоналях нормального магического квадрата, называется магической константой. Магическая константа нормального магического квадрата зависит только от n. Например, для квадрата со стороной 3 клетки она равна 15.
Многие почитатели головоломки судоку искренне считают ее восточным изобретением. В чем-то они правы. Первый известный нормальный магический квадрат третьего порядка, созданный человечеством, датируется 2200 г. до н. э. Он был изображен на панцире черепахи в Древнем Китае. В 13 веке китайский ученый Ян Хуэй и его последователи плотно занимались проблемой методов построения магических квадратов.
Самым ранним появлением магического квадрата в европейском искусстве считается квадрат 4 на 4, изображённый на гравюре
Проблема составления магических квадратов такая же древняя, как и сами эти квадраты. Математики разных эпох бились над этой задачей, но в общем математическом смысле она так и осталась неразрешенной: общий метод построения всех магических квадратов неизвестен.
Многие сравнивают судоку с шахматами. На это есть много причин. Магические квадраты, прародители судоку, как и шахматы появились в глубокой древности. За кажущейся простотой правил (у судоку они даже гораздо проще чем у шахмат) скрывается огромное число комбинаций. Например, количество возможных комбинаций в судоку 9x9 составляет 6 670 903 752 021 072 936 960. Кстати, это всего 0.00012 % от общего числа латинских квадратов со стороной 9 клеток. Правда, справедливости ради, стоит заметить, что число по-настоящему уникальных комбинаций (без поворотов и зеркальных отражений) составляет 5 472 730 538. Это число выглядит скромнее, однако и оно производит впечатление.
Обе игры с самых древних времен имели особый сакральный смысл. В общем, судоку — игра одного уровня с шахматами. Причем, если для последних требуется реквизит — доска и шахматные фигурки, то в судоку можно играть вооружившись деревянной палочкой и рисуя квадраты и цифры на песке.
Связь магических квадратов и шахмат более чем наглядно показал Леонард Эйлер. В 18-ом веке он попытался получить полный магический квадрат непрерывным обходом этого квадрата ходом коня (узнаете распространенную шахматную задачу?). В итоге окончательно сделать это ему не удалось: в главных диагоналях суммы чисел отличались от магической константы. Более мягкий вариант магического квадрата (совпадение сумм по диагоналям не обязательно) Эйлер назвал "латинским квадратом" (при решении этой задачи он пользовался латинскими буквами вместо чисел). Судоку, собственно, и является таким латинским квадратом. Существует понятие «обобщенного» судоку на поле произвольного размера N2 на N2, разделенного на меньшие квадраты со стороной N клеток. Всего на таком поле N4 клеток, в некоторых из которых уже стоят числа от 1 до N2. В итоге задача по заполнению такого поля числами — и есть задача по решению судоку в более общем виде.
Любая популярная игра или головоломка рано или поздно обрастает целым зоопарком вариаций, клонов и модификаций. Так, например, было и с кубиком-рубика, и с тетрисом. Не избежало такой участи и судоку. Классическим считается вариант 9 на 9 клеток. Существуют варианты квадратов со сторонами 16 и даже 25 клеток (такие можно найти, например, на сайте. Эти гиганты предназначены для опытных игроков и требуют для своего разгадывания воистину титанических усилий.
Варьируются не только размеры квадратов, но и сами правила головоломки. Например, существуют судоку, в которых все поле изначально пустое: в нем нет цифр, проставленных автором, однако есть другая информация. Все поле разбивается на прямоугольники различных формы и размера, причем у каждого прямоугольника указывается сумма входящих в него цифр.
Есть даже специальные детские судоку, состоящие всего из четырех клеток. Существуют судоку, основанные не на латинских квадратах Эйлера, а на более общих магических квадратах. В таких головоломках общий квадрат не делится на маленькие квадратики, но введено дополнительное условие: требуется, чтобы в каждой строке, в каждом столбце и на двух максимальных диагоналях каждая цифра встречалась только один раз.
В детстве у меня была головоломка, основанная на кубике-рубика, но с гранями треугольной формы. Не избежало «треугольности» и судоку. Есть варианты, где необходимо заполнить треугольные клетки цифрами от 1 до 9. Всего треугольников шесть, они соприкасаются друг с другом двумя ячейками каждый и вместе образуют что-то вроде цветка. Необходимо, чтобы в каждом из шести больших треугольников и каждой линии по всем трем направлениям все цифры были разными.
Любители изобретают на основе судоку множество задач с дополнительными условиями.
Учитывая популярность судоку, нет ничего удивительного в том, что по всему миру существуют многочисленные клубы и сообщества любителей этой игры. Первый мировой чемпионат по судоку был проведен в Италии в марте 2006 года. Второй — в марте 2007 года, в Праге. С 2006 года под эгидой клуба «Диоген» (это не тот, в котором все молчат, а тот, в котором разгадывают головоломки) проводится чемпионат по судоку в России.
На страницепроводится бесконечное интернациональное состязание среди поклонников судоку. Сайт представлен на нескольких языках, в том числе и на русском. За каждую разгаданную головоломку зарегистрированному пользователю начисляются очки. Алгоритм расчета очков прост как и правила головоломки. Количество разгаданных клеток отнимается от общего количества клеток, затем умножается на коэффициент сложности головоломки (от 1 до 3). Затем вычитаются баллы за подсказки (3, 6 или 9 баллов в зависимости от сложности). Отрицательные значения гуманно обнуляются. Вместо того, чтобы просто с карандашиком разгадывать головоломки на бумажке или задумчиво тыкать стилусом в экран КПК, подбирая числа, каждый может потешить свое самолюбие и сразиться с любителями судоку по всему миру. Кстати, очки суммируются не только в мировом масштабе, но и по странам, регионами и городам. Применение различных автоматических решателей запрещено кодексом сайта и игровое сообщество сайта зорко следит за тем, чтобы все было по-честному.
Написание программы для автоматической генерации задач судоку любой сложности доступно любому программисту: алгоритмы известны, правила просты и незамысловаты, для отображения достаточно даже текстового интерфейса. Поэтому, в сети существует несметное множество онлайновых и оффлайновых генераторов квадратов: каждый может выбрать на свой вкус. Большинство программ не только генерируют задачи, но и предоставляют удобный интерфейс для их решения. Практически все судоку, публикуемые в прессе, составленные с помощью таких программ. Существуют версии судоку для игровых приставок, для сотовых телефонов. Выпускаются даже дешевые электронные игры судоку с черно-белым жидкокристаллическим экранчиком. Я однажды купил такую для жены, чтобы она не скучала в своих долгих путешествиях. Причем, купил я эту игрушку в знакомом нам киоске типа "Союзпечать".
Однако в мире судоку есть свои эстеты. Настоящие знатоки игры ценят судоку, составленные вручную! Такое явление сложно объяснить — его надо почувствовать, самому погрузившись в решение судоку. Это немного похоже на шахматные этюды: мало просто придумать комбинацию на доске и поставить задачу, необходимо еще, чтобы эта комбинация имела изящное решение. В судоку, как и в шахматах скрыта своя необычная красота. Один и тот же иероглиф можно написать по разному, из одного и того же квадрата, полностью заполненного числами можно сделать сотни разных задач, оставляя те или иные числа в качестве исходных.