Иногда судоку по старой памяти (и не совсем правильно) называют "магическим квадратом". Однако, на это есть веские причины. Дело в том, что сам принцип заполнения квадрата числами по указанному правилу известен еще с глубокой древности. В общем математическом смысле это квадрат n на n клеток, заполненных числами (любыми, а не только от 1 до 9) таким образом, что сумма чисел в каждой строке, каждом столбце и на обеих диагоналях является одинаковой.
Головоломки, подобные судоку начали появляться в прессе еще в 19-ом веке. Например, в 1892 году во французской газете Le Sie`cle публиковались головоломки, основанные на магическом квадрате, которые в строгом смысле судоку не являлись.
В судоку реализован т. н. нормальный магический квадрат — он заполнен целыми числами от 1 до n2. Причем, в судоку введено еще одно правило — цифры не должны повторяться во внутренних квадратах со стороной 3 клетки. Совпадение сумм по главным диагоналям в судоку не проверяется.
Сумма чисел в каждой строке, столбце и на диагоналях нормального магического квадрата, называется магической константой. Магическая константа нормального магического квадрата зависит только от n. Например, для квадрата со стороной 3 клетки она равна 15.
Многие почитатели головоломки судоку искренне считают ее восточным изобретением. В чем-то они правы. Первый известный нормальный магический квадрат третьего порядка, созданный человечеством, датируется 2200 г. до н. э. Он был изображен на панцире черепахи в Древнем Китае. В 13 веке китайский ученый Ян Хуэй и его последователи плотно занимались проблемой методов построения магических квадратов.
Самым ранним появлением магического квадрата в европейском искусстве считается квадрат 4 на 4, изображённый на гравюре Альбрехта Дюрера «Меланхолия». Ссылки на эту гравюру до наших дней путешествуют по страницам приключенческих таинственных романов. Вообще, с самых древних времен магическим квадратам приписываются мистические свойства (о чем красноречиво говорит их название). Известны, например, т. н. дьявольские магические квадраты. В таких квадратах с магической константой совпадают также суммы чисел по ломаным диагоналям (диагонали, которые образуются при сворачивании квадрата в тор) в обоих направлениях. Самый ранний дьявольский квадрат четвертого порядка обнаружен в надписи XI века в индийском городе Кхаджурахо.
Проблема составления магических квадратов такая же древняя, как и сами эти квадраты. Математики разных эпох бились над этой задачей, но в общем математическом смысле она так и осталась неразрешенной: общий метод построения всех магических квадратов неизвестен.
Многие сравнивают судоку с шахматами. На это есть много причин. Магические квадраты, прародители судоку, как и шахматы появились в глубокой древности. За кажущейся простотой правил (у судоку они даже гораздо проще чем у шахмат) скрывается огромное число комбинаций. Например, количество возможных комбинаций в судоку 9x9 составляет 6 670 903 752 021 072 936 960. Кстати, это всего 0.00012 % от общего числа латинских квадратов со стороной 9 клеток. Правда, справедливости ради, стоит заметить, что число по-настоящему уникальных комбинаций (без поворотов и зеркальных отражений) составляет 5 472 730 538. Это число выглядит скромнее, однако и оно производит впечатление.
Обе игры с самых древних времен имели особый сакральный смысл. В общем, судоку — игра одного уровня с шахматами. Причем, если для последних требуется реквизит — доска и шахматные фигурки, то в судоку можно играть вооружившись деревянной палочкой и рисуя квадраты и цифры на песке.
Связь магических квадратов и шахмат более чем наглядно показал Леонард Эйлер. В 18-ом веке он попытался получить полный магический квадрат непрерывным обходом этого квадрата ходом коня (узнаете распространенную шахматную задачу?). В итоге окончательно сделать это ему не удалось: в главных диагоналях суммы чисел отличались от магической константы. Более мягкий вариант магического квадрата (совпадение сумм по диагоналям не обязательно) Эйлер назвал "латинским квадратом" (при решении этой задачи он пользовался латинскими буквами вместо чисел). Судоку, собственно, и является таким латинским квадратом. Существует понятие «обобщенного» судоку на поле произвольного размера N2 на N2, разделенного на меньшие квадраты со стороной N клеток. Всего на таком поле N4 клеток, в некоторых из которых уже стоят числа от 1 до N2. В итоге задача по заполнению такого поля числами — и есть задача по решению судоку в более общем виде.