Доброго дня, уважаемые любители математики! ?

Думаю, что многие из подписчиков группы сталкивались с, казалось бы, очень простой задачей — заполнить цифрами от 1 до 9 квадратную таблицу 9х9 так, чтобы в каждой строке и в каждом столбце, а также маленьких блоках 3х3 цифры были различными. Такая задача называется СУДОКУ, это числовая головоломкой сохраняет свою популярность уже несколько десятков лет.

Давайте немного погрузимся в историю её происхождения.

Основа головоломки — латинский квадрат, который получил новое имя благодаря всем известному математику — Леонарду Эйлеру. Гений математики в такой форме решал вычислительные задачи, только вместо цифр использовал латинские буквы. Позднее, в 1979 году Р. Гарнс опубликовал наиболее распространенную версию головоломки. А вот сегодняшнее название СУДОКУ приобрело в японском издании "Nicoli". Помимо названия издатели ввели еще и симметрию в задаче, то есть, заполненные клетки должны образовывать осе- либо центрально-симметричную фигуру. Можно подумать, что Родина судоку — Япония, но это далеко не так, корни ведут в Европу. Заслуга японцев в том, что задача была поставлена для расстановки цифр, а не других символов.

А теперь перейдем к математическим особенностям данной головоломки:

Правило 45.

Поскольку каждая строка, столбец и сектор должны содержать цифры от 1 до 9, то сумма этих областей всегда будет равна 45.

Уникальные возможные сетки.

По расчётам Бертрама Фельгенхауэра, существует 6 670 903 752 021 072 936 960 различных комбинаций сеток судоку.

Симметрия.

В судоку могут встречаться три типа симметрии: точка, линия и вращение.

Алгоритм «Танцующие звенья».

Основная идея алгоритма — построение матрицы, представляющей все возможные способы заполнения сетки таким образом, чтобы каждая строка, столбец и поле содержали цифры от 1 до 9.

NP-полная задача, ведь к ней сводится задача о заполнении латинского квадрата.

Многие могут придти к выводу о том, что для решения задачи о расстановке цифр от 1 до 9 по указанным правилам нужно построить верную логическую цепочку рассуждений и исключений, но все не так просто. Логика, несомненно, нужна, но также присутствуют и другие разделы. Например, синтез подобных числовых структур распространяются на 4-мерное векторное пространство, а решения,

удовлетворяющие некоторым дополнительным условиям, могут быть найдены с помощью закономерностей проективной и аффинной геометрии, теории кодирования, теории

графов, в частности метода раскрашивания карт, целочисленного программирования и т.д.

Существует несколько работ, в которых научно обосновано то, что судоку можно сформулировать и решить в виде линейной системы уравнений!

На сегодняшний день разнообразие числовой головоломки огромно. Поэтому перечислю лишь некоторые из них (см. карусель):

— Размер исходного квадрата: 15х15, 16х16 и даже 25х25 (пандиагональный латинский квадрат)!

— Условия заполнения, например, все поле делится на блоки, в каждом из которых должна быть определенная сумма чисел.

— Разные формы внутренних блоков из 9 клеток.

— Цветные судоку и различные доп. условия.

Как и почти любая задача математики судоку имеет ряд вопросов, на которые ответы еще не найдены. Вот некоторые из них: сколько существует различных комбинаций в Судоку, а также минимальное количество заполненных клеток для обеспечения единственности решения?

А Вы умеете разгадывать судоку?) Если нет, то можно попробовать свои логические рассуждения вот тут?: https://sudoku.com/ru. Можно потренироваться на любом уровне сложности))

P.S. Ниже прикреплю gif-анимацию судоку с точки зрения теории графов, забавно получается)) Приятного просмотра!

Источник: sudoku.com

Комментарии: