Tvorba sudoku v Xamarin - Úvod

Než sa pustíme do programovania hry sudoku, urobíme si malý úvod do problematiky a zjednotíme naše znalosti.

Sudoku

Podľa Wikipédie je sudoku logická hra európskeho pôvodu, určená väčšinou pre jedného hráča. Niekedy sa mylne uvádza, že je japonského pôvodu, ale Japonci stoja iba za rozšíreným názvom hry. Hlavný rozmach sudoku sa začal koncom minulého storočia, keď sa úlohy na riešenie sudoku začali publikovať v časopisoch a novinách po celom svete. Začali sa organizovať súťaže v riešení sudoku na čas, ako sú Majstrovstvá sveta alebo Majstrovstvá republiky.

Čo ma viedlo k riešeniu sudoku pomocou programu

Úraz môže niekedy priniesť aj niečo dobré. Pred viac ako pätnástimi rokmi som hral za "starých pánov" futbal. Bola krásna slnečná nedeľa a čo čert nechcel, zlomil som si nešťastne ľavú ruku. Popravde, spoluhráč mi dal veľmi zlú prihrávku a ja ako „veľký bojovník“ som ju pred postrannou čiarou nestihol a narazil do zábradlia. Ale mal som šťastie, organizátori okamžite volali pohotovosť, prišla záchranka a do jednej hodiny som bol operovaný pod lokálnou anestéziou. Ďakujem primári traumatológie a tiež primári anestéziológie za výbornú prácu.

Už večer som volal manželke, aby mi priniesla notebook a niečo na čítanie pre rozptýlenie. Doniesla samozrejme notebook a niekoľko časopisov. Všimol som si, že v každom časopise je rébus, ktorý sa volá sudoku. Takto som sa vlastne prvýkrát so sudoku stretol. Pravidlá som pochopil veľmi rýchlo, ale ich riešenie mi už tak dobre nešlo. Musím ale povedať, že po tých pätnástich rokoch som sa výrazne zlepšil. Celkom ma to vo voľných chvíľach baví a aj ťažšie sudoku už viem vyriešiť relatívne rýchlo. Lenže v začiatkoch sa mi ani ľahké sudoku nedarilo vyriešiť v rozumnom čase.

Riešenie?

Čo napadne programátora ako prvé? Mám čas, napíšem program na riešenie sudoku. Pokiaľ to vie vyriešiť človek, tak to určite vyrieši aj počítač a určite rýchlejšie. Stačí len vyskúšať všetky možné kombinácie a určite nájdeme riešenie. Jenže tady jsem s hrůzou zjistil, že všech možných kombinací v prázdné mřížce 9x9 je přesně 9 ⁸¹, protože v každé buňce může být 9 čísel a všech buněk je 9x9 = 81. Tato mocnina je ovšem už extrémně vysoké číslo: 1966270504755­529136180759085269121162­831034509442147669273154­15537966391196809

Prehľadnejšie zapísané: 1,96627050475­55292E+77

No dobre, v skutočnosti býva v hre sudoku (určené pre začiatočníkov) vyplnených aj 30 políčok, takže kombinácií je potom menej a to 9 na (81-30), čo je 4638397686588­101979328150167890591454­388888888

Je to výrazne menšie číslo, ale nič nehovorí, ako rýchlo vieme vypočítať všetky kombinácie. Pracoval som pre firmu, ktorá sa zaoberá konštrukciou superpočítačov. Jeden z nich, vraj najvýkonnejší na svete, má byť zmontovaný a umiestnený v SAV na Slovensku v Bratislave. Ide o počítač s výkonom šesťdesiatštyri miliárd miliárd výpočtov za sekundu. Odborne to nazývajú 64E, symbol E ako exa, alebo trilion, čo je 64 krát 10 ¹⁸. Reklamné video si môžete pozrieť na www.tachyum.com

Takže tomuto hypersuper počítaču to bude trvať... Pomôžeme si jednoduchým programom:

using System;

namespace MyApp
{
    internal class Program
    {
        static void Main(string[] args)
        {
            double options;
            double operations_per_second = 64000000000000000000.0;
            double year_in_seconds = 60.0 * 60.0 * 24.0 * 365.0;
            options = Math.Pow(9.0, 81.0 - 30.0); // 9 na 81-30
            Console.WriteLine("Počet možností: {0}", options);
            Console.WriteLine("Počet operácií za sekundu: {0}", operations_per_second);
            Console.WriteLine("Trvanie roka (v sekundách): {0}", year_in_seconds);
            Console.WriteLine("Čas vypočítania všetkých možností (roky): {0}", options / operations_per_second / year_in_seconds);
        }
    }
}

výsledok programu je nasledujúci:

Konzolová aplikácia
Počet možností: 4,638397686588102E+48
Počet operácií za sekundu: 6,4E+19
Trvanie roka (v sekundách): 31536000
Čas vypočítania všetkých možností (roky): 2,298166027807556E+21

Keď uvážime, že vznik vesmíru bol pred cca 18 miliardami rokov dozadu, znamená to, že program by sme museli spustiť pred stvorením vesmíru a ešte dnes by sme nemali výsledok.

Neriešiteľné?

Je to riešiteľné. Použil som matematiku zámerne, aby sa to zdalo neriešiteľné. Ale ak si to rozoberieme detailnejšie, tak zistíme, že si treba len uvedomiť pravidlá sudoku. Pre klasické sudoku 9x9 platí:

1. V každom riadku musia byť čísla od 1 do 9
2. V každom stĺpci musia byť čísla od 1 do 9
3. V každej mriežke 3x3, ktorých je 9, musia byť čísla od 1 do 9

Z týchto pravidiel vyplýva, že každé zadané číslo obmedzuje ďalších dvadsať políčok, kde zadané číslo už nemôže byť, čo výrazne znižuje počet všetkých možných kombinácií. Tých dvadsať políčok je práve preto, že v stĺpci už nemôže byť rovnaké číslo v ďalších ôsmich políčkach, rovnako tak aj v riadku av mriežke štyri. Teda, ak je jednotka v treťom riadku a šiestom stĺpci, tak nemôže byť v dvadsiatich ďalších políčkach:

-------------
|   |111|   |
|   |111|   |
|111|111|111|
-------------
|   |  1|   |
|   |  1|   |
|   |  1|   |
-------------
|   |  1|   |
|   |  1|   |
|   |  1|   |
-------------

V mriežke, pretože nám stĺpce a riadky odoberajú štyri políčka plus číslo zo zadania, tak nám zostávajú práve štyri ďalšie políčka v mriežke, kde dané číslo nemôže byť.

Štvrté pravidlo nie je často publikované, pretože platí hlavne pre zostavovateľov sudoku, ale svojím spôsobom je veľmi dôležité.

To hovorí, že riešenie musí byť len jedno!

Matematici vypočítali, že na splnenie tohto pravidla musia byť splnené dve podmienky. Počet zadaných čísel sudoku musí byť aspoň 17 a počet rôznych čísel od 1 do 9 aspoň 8. Inak je riešenie viac, alebo nie je žiadne riešenie. Ďalej matematici vypočítali, že všetkých možných rôznych rozmiestnení vyhovujúcich pravidlám sudoku na hracom poli s rozmermi 9x9 je 6670903752021­072936960, pokiaľ sa odčítajú symetrické pozície. A v prípade splnenia aj štvrtého pravidla o jednom riešení, ich je len 5482.

Vyzbrojení teoretickými vedomosťami sa môžeme pustiť do tvorby programu na riešenie sudoku. Jedno z možných riešení, je riešenie hrubou silou v C#. Najprv vytvoríme iba konzolovú aplikáciu, aby sme si overili, že náš program funguje. Potom urobíme užívateľský interface v Xamarine, aby sme mohli aplikáciu používať aj v mobile. Celý kurz vlastne nie je o riešení sudoku, pretože na internete je veľa Sudoku Solvers, ale skôr o algoritmizácii, ladení programu ao zrozumiteľných a ľahko pochopiteľných algoritmoch.