Цифровой журнал «Компьютерра» № 8 (Журнал «Компьютерра») - страница 44
Многие сравнивают судоку с шахматами. На это есть много причин. Магические квадраты, прародители судоку, как и шахматы появились в глубокой древности. За кажущейся простотой правил (у судоку они даже гораздо проще чем у шахмат) скрывается огромное число комбинаций. Например, количество возможных комбинаций в судоку 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 клеток (такие можно найти, например, на сайте http://www.sudokur.com). Эти гиганты предназначены для опытных игроков и требуют для своего разгадывания воистину титанических усилий.
Варьируются не только размеры квадратов, но и сами правила головоломки. Например, существуют судоку, в которых все поле изначально пустое: в нем нет цифр, проставленных автором, однако есть другая информация. Все поле разбивается на прямоугольники различных формы и размера, причем у каждого прямоугольника указывается сумма входящих в него цифр.