Sudoku

Sudoku je moja obľúbená zábava. Naučil som sa ho lúštiť počas chôdze, v rozbehnutom autobuse, no proste všade kde sa dá. Väčšinou si vytlačím sudoku z http://www.pdfpad.com/sudoku/. Včera som urobil to isté a začal som riešiť toto sudoku (č. c5688 - dá sa znova vytlačiť na tej stránke): Kto ho vyrieši je frajer :). Keďže nie som úplne normálny v takýchto veciach (poznám celú radu ľudí čo Vám to s radosťou odprisahajú :) ), a keď sa niečo spája s matematikou tak sa pre mňa začína zábava ( predpokladám, že pred chvíľkou spomínaný zoznam sa akurát rozrástol o niekoľko ďalších ľudí :) ). Prvé čo človeka napadne je počet všetkých sudoku plôch. Druhé čo ma pri sudoku trápi :) je nájsť čo najobtiažnejšie sudoku. Prvý problém - počet sudoku plôch mi ležal v hlave už dlhšie. Pôvodne som ho chcel vyriešiť sám, ale nejak som sa zamotával a výsledok nikde. Tak som si zavolal toho pána s tým čudným menom. Akože sa len volal? Hmm, ahá už to mám - Mr. Google :) Po krátkom hľadaní som našiel veľmi zaujímavý článok "Mathematics of Sudoku I" od Bertram Felgenhauer a Frazer Jarvis. Pokiaľ Vám matematika nevonia a predsa len chcete kliknúť na danú linku, odporúčam najprv zavolať vymetača diabla. V prípade, že ste už klikli na odkaz, odložte všetky ostré predmety a hláste sa na najbližšej psychiatrii :) Ale teraz vážne, v tom článku je postup veľmi podobný tomu v mojej hlave, dokonca aj brute force časť kde treba niečo naprogramovať je tam. Rozdiel je, že v tom článku sa dotiahli veci ďalej ako som ich dotiahol ja. Článok nie je písaný nejakou hroznou matematickou rečou tak pre toho koho to naozaj zaujíma to bude poučné čítanie. Ja už len dodám, že výsledok je

6 670 903 752 021 072 936 960

Pekne veľké číslo :) A teraz poďme na najťažšie sudoku. Tu si chcem ale vystačiť bez toho pána s tým zvláštnym menom. Prvé čo je treba je si definovať čo chceme dosiahnuť - najťažšie sudoku je predsa len príliš vágny pojem.

1. sudoku musí byť jednoznačné - inak povedané je len jedno riešenie
2. definovať funkciu "ťažkosti" - každému sudoku treba vedieť priradiť jednoznačne číslo - váhu, najväčšie číslo bude najťažšie sudoku

Prvá časť sa overí riešením sudoku. Samozrejme, že to ale nebudem riešiť ja ale nejaký ten počítač. Druhá časť je už skôr empirická a každý môže rôznym situáciám priradiť iné váhy. Ale najprv si preberme situácie (zóna sa myslí ako 9tica - buď celý stĺpec, celý riadok alebo sudoku štvorec 3x3) :

1. Existuje políčko pre ktoré jednoznačne existuje číslo N - je to jediná možná pozícia pre N v zóne pretože ostatné pozície sú buď už vyplnené alebo ich kryje pozícia ďalšieho N
2. Existuje políčko pre ktoré jednoznačne existuje číslo N - existujú prípady keď neplatí prvý prípad ale Nko je ako jediné možné v zóne - všetky ostatné čísla kryjú danú pozíciu
3. Neexistuje žiadne jednoznačné číslo - je treba si zvoliť v nejakom políčku jedno číslo z možných čísel pre dané políčko a skúsiť vyriešiť sudoku. Ak neexistuje riešenie tak treba zvoliť ďalšie číslo a opakovať postup pokiaľ sa nenájde riešenie

To sú základne situácie. Keďže pri riešení sudoku nastanie viac takýchto situácií tak si treba zvoliť spôsob agregácie a podla toho aj zvoliť ohodnotenie situácie. Najjednoduchšie čo môžeme použiť je aditívna alebo multiplikatívna agregácia. Ja sa prikláňam k multiplikativnej agregácii kde sa hodnoty násobia. Váha prvej možnosti bude 1,01. Ak by sme dali iba 1 tak potom by sudoku s viac číslami na začiatku malo rovnaké číslo obtiažnosti. Takto to to bude síce malá hodnota ale pomôže to usporiadať obtiažnosti. V druhom prípade dáme 1,2. Vo väčšine prípadov nie je obtiažne doplniť dané číslo. Posledný prípad je ale trošku komplikovaný. Nechcem priradiť nejaké konkrétne číslo ale nejakú inú hodnotu ktorá reflektuje obtiažnosť riešenia sudoku pre všetky možné čísla v danom políčku. Použijeme aditívnu agregáciu obtiažnosti pre všetky riešenia sudoku s možnými číslami pre dané políčko. Keďže z prvého problému vieme, že všetkých možných plôch sudoku je obrovské množstvo a nie je reálne pri terajšej výpočtovej kapacite vyskúšať všetky možnosti, preto sa uspokojíme s náhodným sudoku. Samozrejme, že to znamená, že asi nenájdem najobtiažnejšie sudoku, ale predpokladám, že to čo nájdem bude tiež stáť za to.

sudoku = náhodná plocha sudoku
náhodne odoberieme polovicu čísel
počítaj(sudoku)

funkcia počítaj(sudoku)
{
        riešime sudoku a zároveň pri riešení zistíme obtiažnosť
        ak ( sa nedá jednoznačne vyriešiť)
                     tak ukonči funkciu
        ak ( vypočítaná obtiažnosť je väčšia ako najväčšia obtiažnosť doteraz) tak
                     aktuálne sudoku je pre teraz najobtiažnejšie sudoku
        cyklus (pre všetky zostávajúce čísla)
        {
                 odoberieme dané číslo zo sudoku
                 počítaj( sudoku)
                 vrátime dané číslo na svoje miesto
         }
}

Výpočtová zložitosť bude poriadna. Predpokladám, že ma čaká veľa optimalizovania :) Dúfam že v blízkej budúcnosti sa tu objaví hrozne ťažké sudoku :)