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

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

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

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

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

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

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

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

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

Оказалось, что это число равно 17.