Вы здесь: Главная -> Новости -> -> -> Судоку помогла математикам "перемешивать" изображения
Новости науки
2016:
78
2015:
12345678910
2014:
123456789101112
2013:
123456789101112
2012:
123456789101112
2011:
123456789101112
2010:
123456789101112
2009:
123456789101112
2008:
123456789101112
2007:
123456789101112
2006:
123456789101112
Рейтинг@Mail.ru

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

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

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

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

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

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

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

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

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

Источник: Лента.ру



главная :: наверх :: добавить в избранное :: сделать стартовой :: рекомендовать другу :: карта сайта :: создано: 2012-07-27T00:00:00+00
Наша кнопка:
Научно-образовательный портал