211service.com
Matemātiķi šifrē attēlus, izmantojot Sudoku matemātiku
Ciparu izvietošanas mīkla Sudoku sastāv no 9 x 9 režģa, kas jāaizpilda, izmantojot ciparus no 1 līdz 9.
Tomēr ir vairāki papildu ierobežojumi. Katrs cipars var parādīties tikai vienu reizi katrā kolonnā, vienu reizi katrā rindā un vienu reizi katrā no deviņiem 3 x 3 blokiem, kas veido režģi. Tālāk ir parādīts Soduko risinājuma režģis. Spēlētājiem tiek doti vairāki cipari no risinājuma, lai sāktu spēli.
Sudoku ir radījis vairākus interesantus izaicinājumus matemātiķiem. Piemēram, šī gada sākumā mēs apskatījām, kā matemātiķi ir atrisinājuši “minimālo Sudoku problēmu”, lai atrastu vismazāko norādes, kas ved uz unikālu risinājumu (atbilde, 17).
Mūsdienās Jue Vu no Tuftas universitātes Medfordā un pāris draugu izmanto Sudoku, lai risinātu citu problēmu — kā šifrēt attēlus pirms to nosūtīšanas.
Šie puiši saka, ka Sudoku režģu īpašās īpašības noved pie pilnīgi jauna veida matricas matemātikas, ko viņi ir izmantojuši attēlu kodēšanai.
Pirmkārt, neliels priekšvēsture par matricām. Matrica ir vienkārši taisnstūrveida skaitļu masīvs. Katrs masīva elements ir unikāli identificēts ar režģa atsauci — tā kolonnu un rindas numuru.
Bet Wu un co apgalvo, ka masīvā elementus ir iespējams identificēt arī citos veidos, ja uzskatāt to par Sudoku režģi. Tādā gadījumā katrā elementā ir cipars no 1 līdz 9, kas atbilst Sudoku noteikumiem. Citiem vārdiem sakot, katram elementam papildus rindai un kolonnai ir arī cipars.
Tātad iepriekš minētajā režģī elements pirmajā rindā un pirmajā kolonnā (1,1) ir saistīts arī ar ciparu 8, elements (1,2) ir saistīts ar 7, elements (1,3) ar 4 un tā tālāk. .
Turklāt katrs elements ir saistīts arī ar 3 x 3 bloku, kas numurēts, kā parādīts iepriekš redzamajā režģī. Tātad elements (1,1) ir saistīts ar bloku 1, elements (2,8) ar bloku 7 un elements (8,5) ar bloku 6 un tā tālāk.
Tas ļauj identificēt katru elementu citos veidos. Tātad elements 5. blokā, kas satur ciparu 9, ir elements (4,5) parastajā apzīmējumā; elements 3. ailē, kas satur ciparu 7, ir (8,3) ar parasto apzīmējumu, un elements 6. rindā, kurā ir 2, ir (6,9).
Kopumā ir seši dažādi veidi, kā attēlot katru elementu, piemēram, Wu un co. Katra no šīm sistēmām ir līdzvērtīga, un ir iespējams konvertēt koordinātas no vienas sistēmas uz otru, izmantojot vienkāršu matemātisku pārveidošanas funkciju kopu.
Šīs konvertēšanas funkcijas ir attēlu kodēšanas atslēga. Sāciet ar attēlu, kas sastāv no 9x9 pikseļiem. Pēc tam uz šī režģa uzklājiet Soduko risinājumu, lai katru pikseli tagad varētu attēlot ar jaunajām koordinātu sistēmām.
Tagad, izmantojot vienu no pārveidošanas funkcijām režģī, tiek mainīta pikseļu pozīcija, sajaucot attēlu.
Wu un co ir atklājuši, kā piemērot īsu konvertēšanas funkciju secību, kas pilnībā sagroza attēlu. Tas ir noderīgi, jo tas ir pilnībā deterministisks un tomēr rada šķietami nejaušu rezultātu (kā parādīts augšējā attēlā).
Tas ir līdzvērtīgs sava veida šifrēšanai, kurā galvenais ir oriģinālais Sudoku risinājums. (Lai iegūtu lielākus attēlus, vienkārši izveidojiet attēlu ar vairākiem Sudoku režģiem.)
Wu un co ir veikuši sākotnējo salīdzinājumu starp savu metodi un citiem attēlu kodēšanas algoritmiem un apgalvo, ka tā atbilst tiem vai pārspēj tos.
Un tā kā 256 x 256 attēlam ir vismaz 256!=2^1684 iespējamās Sudoku matricas, pretiniekam nav viegli nejauši vai pat ar brutālu spēku trāpīt risinājumam.
Wu un co neapgalvo par tā potenciālo drošību, taču šeit noteikti ir vietas tālākai izpētei.
Apbrīnojami, ko Sudoku var darīt cilvēces labā!
Atsauce: arxiv.org/abs/1207.5856 : ar Sudoku saistītas divdimensiju bijekcijas attēlu kodēšanai