Головоломка судоку не только позволяет скоротать время в электричке, но и представляет собой интересную математическую задачу, для которой можно найти полезное применение.

Как известно, игровое поле судоку представляет собой квадрат размером 9×9, разделённый на меньшие квадраты со стороной в три клетки. В клетках расставлены числа таким образом, чтобы в каждой строке, в каждом столбце и в каждом малом квадрате 3×3 каждая цифра встречалась только один раз.

Игровое поле судоку можно рассматривать как обыкновенную матрицу, каждая ячейка в которой имеет свои координаты, в соответствии с номером столбца и номера строки. Например, на матрице вверху элемент в пятом блоке с цифрой 9 описывается стандартной записью как (4,5), элемент в третьем столбце с цифрой 7 — как (8,3), элемент в шестой строчке с цифрой 2 — как (6,9).

Уникальность игрового поля судоку состоит в том, что ячейки в нём можно записывать не только по номеру строки/столбца, но и другими способами, поскольку существует чёткая взаимозависимость между элементами, а также дополнительная привязка к квадратам 3×3.

Группа учёных под руководством Ву (Yue Wu) из университета Тафтса в Массачусетсе описала шесть различных способов идентификации каждого элемента в матрице судоку, а также привела формулы, с помощью которых осуществляется преобразование из одного метода кодирования матрицы в другой. Казалось бы, зачем они это делали? Оказывается, такие свойства матриц делают их идеальным инструментом для скремблирования изображений.

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

Матрицы судоку отлично подходят для скремблирования. В научной работе Sudoku Associated Two Dimensional Bijections for Image Scrambling авторы сравнивают свой метод и программу Sudoku Associated Image Scrambler на его основе с существующими методами скремблирования — и приходят к выводу, что он не уступает ни одному из них, а во многих случаях превосходит аналоги.


На иллюстрации: (a) оригинальное изображение; (b) один раунд скремблирования; (c) двенадцать раундов скремблирования; (d) двенадцать раундов скремблирования со сдвигом; (e) двенадцать раундов скремблирования в программе Sudoku Associated Image Scrambler.

Для изображения 256 x 256 пикселов существует как минимум 256!=2^1684 матриц судоку, так что изображение после скремблирования невозможно расшифровать случайно или даже методом брутфорса.

Примеры скремблированных изображений:

Для скремблирования используется ключ такого вида: B697F2703EA4347A85D997FB18A1FC3CE7E6901B6A9AE5EA. При этом изменение всего лишь одного бита в ключе кардинальным образом меняет изображение. Например, на иллюстрациях внизу показано оригинальное изображение (a), скремблированное ключом B697F2703EA4347A85D997FB18A1FC3CE7E6901B6A9AE5EA (b) и ключом A697F2703EA4347A85D997FB18A1FC3CE7E6901B6A9AE5EA (с), а также разница между ними (d), восстановленное изображение первым ключом (e) и результат применения первого ключа для восстановления второго изображения (f).

  • Подпишись на наc в Telegram!

    Только важные новости и лучшие статьи

    Подписаться

  • Подписаться
    Уведомить о
    0 комментариев
    Межтекстовые Отзывы
    Посмотреть все комментарии