Быстрая доставка новостей прямо в ваш Telegram

Судоку помогла математикам "перемешивать" изображения

Математики воспользовались судоку для"перемешивания" изображений. Статья пока не принята к публикации в рецензируемом журнале, однако ее препринт доступен на сайте arXiv.org.

Судоку - головоломка, представляющая собой квадрат 9 на 9 клеток, разбитый в свою очередь на 9 подквадратов 3 на 3. Суть головоломки состоит в том, что игроку дается частично заполненная таблица, которую он должен "дозаполнить" цифрами от 1 до 9. Правила заполнения просты - ни в одной строке, ни в одном столбце, ни в одном подквадрате 3 на 3 не должны встречаться одинаковые цифры.

В работе ученые взяли уже заполненную головоломку. Каждая клетка в такой таблице имеет несколько наборов координат. Ученые рассмотрели два таких набора: первый - номер столбца и номер строки, второй - номер подквадрата и цифра от 1 до 9, стоящая в данном квадрате. Эти два набора взаимно однозначно определяют друг друга, то есть, по данному решению судоку из одного можно получить другой и наборот.

Принцип работы "перемешивания" следующий. Ученые разбивали картинку на куски 9 на 9 пикселей. Дальше, в каждом таком куске они меняли координаты точек с первого типа на второй. Далее пиксели переставлялись особым образом так, чтобы координаты второго типа становились координатами типа первого.

Например, если в табличке во втором ряду на втором месте стояла цифра девять, то координаты этой клетки первого типа (2, 2), а второго (1, 9), поскольку она располагается в первом квадрате 3 на 3. После перестановки этот пиксель попадет на пересечение первой строки и девятого столбца.

Применив такую перестановку достаточно много раз, ученые получают из картинки месиво разноцветных пикселей. Чтобы теперь вернуть изображение в исходное состояние, нужно знать решение судоку, которое использовалось для кодировки. Как следствие, картинка оказывается зашифрованной.

По словам ученых, результат выглядит довольно случайным. Более того, по сравнению с другими методами "перемешивания" картинок он работает гораздо быстрее. Сами ученые, правда, не проводили анализ устойчивости к взлому своего алгоритма, поэтому о практическом его применении речи не идет.

В январе 2012 года ирландские ученые решили так называемую проблему подсказок в судоку. Они установили, какое минимальное число цифр нужно выставить в таблице головоломки, чтобы она имела единственное решение. Оказалось, что это число равно 17.

АПЛ К-278 «Комсомолец» на дне Норвежского моря

«Не надо ничего там бередить»

Радиация затонувшей АПЛ «Комсомолец» угрожает жизни людей. Почему ее не торопятся поднять

Самое пекло

Америка боится извержения супервулкана. Чем он грозит человечеству?