Sudoku

Balandžio viduryje Kalifornijoje vyko MySQL konferencija, kurioje buvo galima išgirsti pačių įvairiausių pranešimų duomenų bazių tema. Mane labiausiai sudomino „The Lost Art of the Self Join“ pranešimas (pateiktis PDF formatu), kurio kulminacija buvo Sudoku galvosūkio išsprendimas vos viena SQL užklausa (angl. query) - šį kartą apžvelgsiu mano rastus Sudoku sprendimo būdus.

Daugiau informacijos apie Sudoku žaidimą galite rasti Wikipedijoje, kur aprašyti ir dažniausiai sutinkami bei naudojami sprendimo būdai. Kompiuteris veikia šiek tiek kitaip nei žmogaus smegenys, todėl ne visi aprašyti būdai tinkami - paprasčiausia būtų Sudoku sprendžiančią programą parašyti „aklo spėjimo“ (angl. Bruteforce) būdu. Toks sprendimo būdas paremtas tuo, kad išbandomos visos įmanomos langelių reikšmės ({1,2,3,4,5,6,7,8,9}), kol randamas teisingas sprendimas. Pats elementariausias sprendimas sunaudotų 9^81 (1.96 * 10^77) procesoriaus ciklų, todėl sprendimas turėtų užtrukti ilgai, labai ilgai. Internete yra gausybė įvairiausių programų, kurios sprendžia Sudoku, o jų sparta siekia dešimtis ar net šimtus tūkstančių galvosūkių per sekundę.

Minėtoje pateiktyje buvo patekta užklausa, kuri 6×6 dydžio Sudoku galvosūkį išsprendžia per akimirką. Šis būdas susidoroja tik su sumažinta galvosūkio versija, nes standartinio 9×9 galvosūkio sprendimui pritrūktų JOIN tipo vidinių užklausų (MySQL JOIN užklausų kiekis yra ribotas, taigi pavyzdžiui su PostgreSQL pavyktų išspręsti ir pilno dydžio galvosūkį). Kadangi pateikties tikslas buvo lyg ir priminti, kad SQL užklausose galima naudoti JOIN’us, tai pateiktas sprendimas gal ir nėra praktiškai pritaikomas, tačiau puikiai iliustruoja tai, kaip galima programos ciklus perkelti į užklausas. Verta pažymėti ir tai, kad tiek daug vidinių užklausų galima naudoti tik tada kai duomenys yra gerai indeksuoti arba jų yra mažai, nes kitu atveju užklausa gali būti apdorojama amžiais (4 lentelės su 15′000 įrašų sujungtos į 4-matę struktūrą būtų apdorojamos 321 metus).

Jei jau pradėjome spręsti Sudoku, tai galima prieiti ir prie galutinio sprendimo - 9×9 dydžio galvosūkį sprendžianti užklausa. Nors ji iš pirmo žvilgsnio atrodo gana griozdiška ir neoptimali, tačiau jos vykdymas užtrunka vos 0.4 sekundės. Lyginant su programiniais sprendimo algoritmais tokia sparta atrodo juokinga, tačiau pasižaisti ši užklausa yra visai tinkama. Užklausos pabaigoje pamatysite pradinių duomenų reikšmes, o atsakymas gaunamas vien tik loginių patikrinimų dėka, t.y. šioje užklausoje aprašyta Sudoku taisyklė - skaičius turi būti unikalus stulpelyje ir eilutėje. Pasižiūrėjus atidžiau šis sprendimo būdas netgi nenaudoja jokių duomenų iš lentelės - lentelė panaudojama kaip šablonas ir jos laukeliai tik nusako lentelės struktūrą.

Nors dar nespėjau išbandyti nei pirmos nei antros užklausos (kol kas dar neradau paruoštų testinių duomenų bei naudojamų lentelių struktūros aprašų), tačiau abejoju, kad jos galėtų neveikti - abu jie kopijuoti iš patikimų šaltinių, o ir pačiose užklausose nelabai pavyko rasti loginių ar pan. klaidų. Abi šios užklausos pasižymi tuo, kad viena lentelė (su N laukų) panaudojama kelis kartus taip sukuriant virtualią NxN dydžio galvosūkio lentelę - atsakymo ieškojimas ir skaičių bandymas paliekamas MySQL duomenų bazių sistemai. Galbūt tai yra šioks toks „iškrypimas“, tačiau tokius dalykus gali sukurti tik gerai išmanydamas užklausų rašymą, todėl tikrai rekomenduoju kiekvienam pasiskaityti pateikties skaidres.

Praktiškai tokie dalykai vargiai panaudojami, tačiau teorinėms žinios stiprinti yra visai šaunūs, nes parašyti gerą užklausą yra menas mokslas. Be abejo kompiuterių sparta nepaliaujamai auga ir tai, kas vakar atrodė lėta, šiandien užtrunka vos kelias tūkstantąsias sekundės dalis, tačiau tai dar nereiškia, kad resursų prieaugį galima švaistyti. Kokių įdomybių jūs žinote?

RSS Patiko ką perskaitei? Užsiprenumeruok RSS srautą ir visada gauk mano naujausius įrašus pats pirmas! Tai ne tik, kad yra be galo patogu, tačiau ir leis tau nepraleisti nei vieno mano įrašo. Jei kiltų problemų - rašyk.

--!>