Asta într-adevăr niciodată nu ghici ce poate fi folosit în viață. Se pare că Sudoku este doar un puzzle distractiv. Și, după toate acestea, a folosit și algoritmul de codare a imaginilor!
Algoritmul ultra-modern de codificare a imaginii utilizează un nou tip de matrice, creat pe baza puzzle-ului Sudoku.
Puzzle-ul numeric al Sudoku constă dintr-un tabel de celule care trebuie umplut cu numere de la.
Există o serie de restricții suplimentare. Fiecare cifră poate apărea o singură dată în fiecare coloană, o dată pe fiecare rând și o dată în fiecare din cele nouă blocuri care alcătuiesc masa. Soluția puzzle-ului este dată mai jos. La începutul jocului, jucătorii cunosc locația unui anumit număr de cifre din această decizie.
Datorită Sudoku au apărut o serie de probleme interesante pentru matematicieni. La începutul acestui an, de exemplu, a fost rezolvată problema numărului minim de chei pentru Sudoku, care dă o singură soluție (cum ar fi cheile 17).
Acum, Yu Wu de la Universitatea Tufts din Medford și colegii săi au folosit Sudoku pentru a rezolva o altă problemă - problema codificării imaginilor înainte de a le trimite.
Proprietățile speciale ale tabelului Sudoku au dus la apariția unui tip complet nou de matrice, pe care l-au folosit pentru a codifica imaginile.
În primul rând, un pic despre matrice. Matricea este doar o tabelă cu numere rectangulare. Fiecare element din tabel este determinat în mod unic de o pereche de numere: numerele rândului și coloanelor în care se află.
Dar Wu și colegii săi spun că puteți defini elementele de tablă în mod diferit, dacă vă gândiți la acesta ca la un tabel de sudoku. În acest caz, fiecare element conține o cifră de la, care satisface regulile lui Sudoku. Cu alte cuvinte, pe lângă numerele rândului și coloanei, fiecare element are un număr.
Astfel, în tabelul de mai sus, elementul din primul rând și prima coloană corespund, de asemenea, unui număr, elementul este asociat cu o cifră, elementul cu o cifră etc.
În plus, fiecare element este, de asemenea, asociat blocului, iar blocurile în sine sunt numerotate așa cum se arată în figură. Astfel, un element este asociat cu un bloc, un element cu un bloc, un element cu un bloc și așa mai departe.
Acest lucru face posibilă identificarea diferită a fiecărui element. Astfel, un element dintr-un bloc care conține o cifră este un element în notația convențională; un element dintr-o coloană care conține o cifră este un element în notația comună și un element dintr-un șir care conține un element.
În total, există șase moduri diferite de prezentare a fiecărui element, conform lui Wu și colegilor săi. Fiecare dintre aceste sisteme de notare poate fi folosit și puteți converti coordonatele de la un sistem la altul utilizând un set de funcții simple de transformare matematică.
Aceste funcții de conversie reprezintă cheia pentru codarea imaginilor. Să începem cu imaginea pixelilor. Impuneți decizia lui Sudoku asupra acestuia, astfel încât fiecare pixel să poată fi acum reprezentat de coordonate în noul sistem de coordonate.
Acum, folosind una din funcțiile de transformare, schimbăm pozițiile pixelilor, amestecând imaginea.
Wu și colegii săi au descoperit cum se aplică o scurtă secvență de funcții de conversie, care criptează complet imaginea. Acest lucru este util deoarece totul este complet determinist și, în același timp, dă un rezultat aparent la întâmplare (așa cum se arată în figura superioară).
Acest lucru este echivalent cu tipul de criptare în care soluția originală Sudoku este cheia. (Pentru imagini mari, mai multe tabele sudoku sunt suprapuse peste ele).
Wu și colegii săi au făcut unele comparații inițiale ale metodei și altor algoritmi de codare a imaginilor. Ei spun că noul algoritm funcționează la fel de rapid sau chiar depășește algoritmii cunoscuți.
Cu toate acestea, Wu și colegii săi nu fac nicio declarație cu privire la rezistența la ruperea algoritmului lor, dar, evident, este nevoie de cercetări suplimentare aici.
Este uimitor cât de mult poate face Sudoku pentru omenire!
Trimiteți-le prietenilor: