Реклама

 


Цікаве

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

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

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

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

Наприклад, якщо в табличці в другому ряду на другому місці стояла цифра дев'ять, то координати цієї клітини першого типу(2, 2), а другого(1, 9), оскільки вона розташовується в першому квадраті 3 на 3. Після перестановки цей піксель потрапить на перетин першого рядка і дев'ятого стовпця.

Застосувавши таку перестановку досить багато разів, учені отримують з картинки місиво різноколірних пікселів. Щоб розкодувати зображення, треба знати рішення судоку, яке використовувалося для кодування.

За словами учених, результат виглядає досить випадковим. Більше того, в порівнянні з іншими методами кодування картинок він працює набагато швидше. Самі учені, правда, не провели аналіз стійкості до злому свого алгоритму, тому про практичне його застосування мови не йде.

У січні 2012 року ірландські учені розв'язали так звану проблему підказок в судоку. Вони встановили, яке мінімальне число цифр треба виставити в таблиці головоломки, щоб вона мала єдине рішення. Виявилось, що це число дорівнює 17.

Powered by Web Agency

Новіші інформаційні сюжети:





Реклама

 

Школа життя

Добавлено 22 листопада 2014
y-chomy-korist-dovgih-spdnic Мода - штука мінлива. Ще недавно дівчата і хлопці сходили з розуму від дивних штанців, прозваних в народі... не дуже культурно. Але змінилася чергова віха, дами стали хизуватися в довгих струмуючих спідницях. Тут же поповзли чутки, що слабка половина...
3360

У світі цікавого

Добавлено 27 грудня 2013
iak-dut-prikmeti--iak-h-neitralzyvat Маса вірувань пов'язана з давніми архаїчними уявленнями, безглуздими поза язичницької картини світу. Багато прикмети обґрунтовуються психологічно або історично. Розсипана сіль могла призвести до сварки із-за своєї цінності в старовину... ...
5080