Головоломка судоку не только позволяет скоротать время в электричке, но и представляет собой интересную математическую задачу, для которой можно найти полезное применение.
Как известно, игровое поле судоку представляет собой квадрат размером 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).
