Sudoku matemātika noved pie mīklas cietības “Rihtera skalas”

Globālā aizraušanās ar Sudoku ir izraisījusi pēkšņu interesi par mīklas matemātiskajām īpašībām. Dažu pēdējo mēnešu laikā šajā emuārā esam apskatījuši, kā matemātiķi ir atrisinājuši minimālo Sudoku problēmu un pat to, kā viņi ir izmantojuši Sudoku matemātiku, lai šifrētu attēlus .

Šodien mēs iegūstam atšķirīgu skatījumu uz Sudoku, pateicoties Maria Ercsey-Ravasz darbam Babes-Bolyai Universitātē Rumānijā un Zoltana Toročkai darbam Notre Dame Universitātē Indiānā.

Šie puiši ir izstrādājuši veidu, kā izmērīt konkrētas Sudoku mīklas sarežģītības pakāpi, un saka, ka viņu Rihtera mīklu sarežģītības skalu var izmantot daudzām citām spēlēm.

Pirmkārt, neliela informācija par Sudoku. Šī ir skaitļu mīkla, kas sastāv no 9 x 9 režģa, kurā dažās šūnās ir norādes ciparu formā no 1 līdz 9. Risinātāja uzdevums ir aizpildīt atlikušās šūnas tā, lai katra rinda, kolonna un 3 × 3 lodziņš režģī ir visi deviņi cipari. Turklāt katram režģim var būt tikai viens risinājums.

Sudoku mīklas parasti tiek klasificētas kā vieglas, vidējas vai smagas, un tām ir vairāk sākuma norādes, bet ne vienmēr ir vieglāk atrisināt. Bet grūtības matemātiski kvantificēt ir grūti.

Tagad Erčejs-Ravašs un Toročkai saka, ka ir izstrādājuši veidu, kā to izdarīt, izmantojot algoritmiskās sarežģītības teoriju. Viņi norāda, ka ir viegli izveidot algoritmu, kas atrisina Sudoku, pārbaudot katru ciparu kombināciju, lai atrastu to, kas darbojas. Šāds brutāla spēka risinājums garantē jums atbildi, bet ne ļoti ātri.

Tā vietā algoritmu izstrādātāji meklē gudrākus veidus, kā atrast risinājumus, kas izmanto problēmas struktūru un ierobežojumus. Šie algoritmi un to uzvedība ir sarežģītāki, taču tie saņem atbildi ātrāk.

Erčeja-Ravaša un Toročka argumenta centrālais punkts ir tāds, ka, tā kā algoritms atspoguļo problēmas struktūru, tā uzvedība — līkloči, kas seko stāvokļa telpai — ir labs problēmas sarežģītības mērs.

Lai to parādītu, viņi izmanto Sudoku piemēru. Brutālā spēka risinājuma vietā viņi izstrādā daudz elegantāku algoritmu, kas izmanto dažādus mīklas ierobežojumus, piemēram, to, ka katrā rindas kolonnā un apakšrežģī jāsatur visi cipari no 1 līdz 9.

Tādā veidā viņi pārveido problēmu par veidu, ko sarežģītības teorētiķi pazīst kā k-sat problēmu.

Viņi sāk ar nejaušas skaitļu kopas ievietošanu režģī un seko algoritma trajektorijai pa stāvokļa telpu, kad tas meklē risinājumu. Vienkāršai problēmai šī trajektorija ir vienkārša, kā parādīts augšpusē no diviem attēliem šīs ziņas augšpusē.

Bet tas viss mainās uz sarežģītu problēmu. Erčejs-Ravašs un Toročkai tik rūpīgi pārbauda savu algoritmu pret Sudoku režģi, ka tam ir savs nosaukums: platīna blondīne. Rezultāts ir parādīts attēla apakšējā daļā. Tas ir ievērojami sarežģītāks, un tā atrisināšana prasa desmit reizes ilgāku laiku.

Erčejs-Ravašs un Toročkai saka, ka sarežģītu problēmu gadījumā trajektorija kļūst haotiska, pirms tiek pieņemts risinājums. Faktiski laiks, kas nepieciešams, lai izvairītos no šī haotiskā stāvokļa, ir vienkāršs grūtības mērs.

Pamatojoties uz to, viņi izveido mīklas sarežģītības “Rihtera skalu”, pamatojoties uz aizbēgšanas ātrumu. Skala svārstās no 1 līdz 4, kur viens ir visvieglākais un 4 ir īpaši ciets.

Viņi saka, ka šī skala pārsteidzoši labi korelē ar subjektīvajiem cilvēku vērtējumiem ar 1, kas atbilst vieglām mīklām, 2 līdz vidēji mīklām un 3 grūtām mīklām. Platīna blondīnei ir grūtības 3,5789.

Interesants secinājums ir tāds, ka nav zināma neviena Sudoku mīkla ar 4 grūtību. Arī pavedienu skaits ne vienmēr ir labs grūtības mērs. Erčejs-Ravašs un Toročkai stāsta, ka ir pārbaudījuši daudzas mīklas, tostarp vairākas ar 17 norādes, minimālo skaitu un dažas ar 18 pavedieniem.

Tos visus bija vieglāk atrisināt nekā platīna blondu, kuram ir 21 norāde. Tas ir tāpēc, ka mīklas cietība ir atkarīga ne tikai no pavedienu skaita, bet arī no to atrašanās vietas.

Tagad interesants jautājums ir par to, vai patiešām eksistē īpaši cieta mīkla ar 4 grūtību un kā to var atrast.

Nozīmīgāks par to ir tas, ka Erčeja-Ravaša un Toročkai metode vispārina visas k-sat problēmas, kas ir tādas pašas klases kā Sudoku. Tātad visu šo problēmu sarežģītību var klasificēt pēc līdzīgām Rihtera tipa skalām.

Tas atstāj tikai vienu jautājumu — kā būtu jāsauc mīklas sarežģītības skala? Acīmredzamā atbilde ir Erčeja-Ravaša un Toročkai skala vai ERT skala. Visi citi ieteikumi komentāru sadaļā zemāk.

Atsauce: arxiv.org/abs/1208.0370 : Haoss Sudoku iekšienē

paslēpties