Lekce 1 - Tvorba sudoku v Xamarin - Úvod

Vítám všechny programátory u kurzu Xamarin aplikace Sudoku v C# .NET. V tomto on-line kurzu vytvoříme funkční aplikaci pro hru Sudoku.

Než se pustíme do programování hry Sudoku, uděláme si malý úvod do problematiky a sjednotíme naše znalosti.

Sudoku

Podle Wikipedie je sudoku logická hra evropského původu, určená většinou pro jednoho hráče. Někdy se mylně uvádí, že je japonského původu, ale Japonci stojí pouze za rozšířeným názvem hry. Hlavní rozmach sudoku se začal koncem minulého století, kdy se úkoly pro řešení sudoku začaly publikovat v časopisech a novinách po celém světě. Začaly se organizovat soutěže v řešení sudoku na čas, jako jsou Mistrovství světa nebo Mistrovství republiky.

Co mě vedlo k řešení sudoku pomocí programu

Úraz může někdy přinést i něco dobrého. Před více než patnácti lety jsem hrál za "staré pány" fotbal. Byla krásná slunečná neděle a co čert nechtěl, zlomil jsem si nešťastně levou ruku. Popravdě, spoluhráč mi dal velmi špatnou přihrávku a já jako "velký bojovník" jsem ji před postranní čárou nestihl a narazil do zábradlí. Ale měl jsem štěstí, organizátoři okamžitě volali pohotovost, přijela záchranka a do jedné hodiny jsem byl operován pod lokální anestezií. Děkuji primáři traumatologie a také primáři anesteziologie za výbornou práci.

Už večer jsem volal manželce, aby mi přinesla notebook a něco ke čtení pro rozptýlení. Donesla samozřejmě notebook a několik časopisů. Všiml jsem si, že v každém časopise je rébus, který se jmenuje sudoku. Takhle jsem se vlastně poprvé se sudoku setkal. Pravidla jsem pochopil velmi rychle, ale jejich řešení mi už tak dobře nešlo. Musím ale říct, že po těch patnácti letech jsem se výrazně zlepšil. Docela mě to ve volných chvílích baví a i těžší sudoku už umím vyřešit relativně rychle. Jenže v začátcích se mi ani lehké sudoku nedařilo vyřešit v rozumném čase.

Řešení?

Co napadne programátora jako první? Mám čas, napíšu program na řešení sudoku. Pokud to umí vyřešit člověk, tak to určitě vyřeší i počítač a určitě rychleji. Stačí jen vyzkoušet všechny možné kombinace a jistě najdeme řešení. 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. Přehledněji zapsané 1,96627050475­55292E+77

No dobře, ve skutečnosti bývá ve hře sudoku (určené pro začátečníky) vyplněných i 30 políček, takže kombinací je pak méně a to 9 na (81-30), což je 4638397686588­101979328150167890591454­318967698009 nebo 4,63839768658­8102E+48.

Je to výrazně menší číslo, ale nic neříká, jak rychle umíme vypočítat všechny kombinace. Pracoval jsem pro firmu, která se zabývá konstrukcí superpočítačů. Jeden z nich, prý nejvýkonnější na světě, má být smontován a umístěn v SAV na Slovensku v Bratislavě. Jedná se o počítač o výkonu šedesát čtyři miliard miliard výpočtů za vteřinu. Odborně to nazývají 64E, symbol E jako exa, nebo trilion, což je 64 krát 10¹⁸. Reklamní video si můžete prohlédnout na www.tachyum.com

Takže tomuto hypersuper počítači to bude trvat... Pomůžeme si jednoduchým programem v C#:

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 operací za sekundu: {0}", operations_per_second);
            Console.WriteLine("Trvání roku (v sekundách): {0}", year_in_seconds);
            Console.WriteLine("Čas vypočítání všech možností (roky): {0}", options / operations_per_second / year_in_seconds);
        }
    }
}

Výsledek programu je následující:

Konzolová aplikace
Počet možností: 4,638397686588102E+48
Počet operací za sekundu: 6,4E+19
Trvání roku (v sekundách): 31536000
Čas vypočítání všech možností (roky): 2,298166027807556E+21

Když uvážíme, že vznik vesmíru byl před cca 18 miliardami let dozadu, znamená to, že program bychom museli spustit před stvořením vesmíru a ještě dnes bychom neměli výsledek.

Neřešitelné?

Je to řešitelné. Použil jsem matematiku záměrně, aby se to zdálo neřešitelné. Ale pokud si to rozebereme detailněji, tak zjistíme, že je třeba si jen uvědomit pravidla sudoku. Pro klasické sudoku 9x9 platí:

1. V každém řádku musí být čísla od 1 do 9
2. V každém sloupci musí být čísla od 1 do 9
3. V každé mřížce 3x3, kterých je 9, musí být čísla od 1 do 9

Z těchto pravidel vyplývá, že každé zadané číslo omezuje dalších dvacet políček, kde zadané číslo již nemůže být, což výrazně snižuje počet všech možných kombinací. Těch dvacet políček je právě proto, že ve sloupci už nemůže být stejné číslo v dalších osmi políčkách, stejně tak i v řádku a v mřížce čtyři. Tedy, pokud je jednotka ve třetím řádku a šestém sloupci, tak nemůže být ve dvaceti dalších políčkách:

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

V mřížce, jelikož nám sloupce a řádky odebírají čtyři políčka plus číslo ze zadání, tak nám zůstávají právě čtyři další políčka v mřížce, kde dané číslo nemůže být.

Čtvrté pravidlo není často publikováno, neboť platí hlavně pro sestavovatele sudoku, ale svým způsobem je velmi důležité.

To říká, že řešení musí být jen jedno!

Matematici vypočítali, že ke splnění tohoto pravidla musí být splněny dvě podmínky. Počet zadaných čísel sudoku musí být alespoň 17 a počet různých čísel od 1 do 9 alespoň 8. Jinak je řešení více, nebo není žádné řešení. Dále matematici vypočítali, že všech možných různých rozmístění vyhovujících pravidlům sudoku na hracím poli o rozměrech 9x9 je 6670903752021­072936960, pokud se odečítají symetrické pozice. A v případě splnění i čtvrtého pravidla o jednom řešení, jich je jen 5482.

Vyzbrojeni teoretickými vědomostmi se můžeme pustit do tvorby programu na řešení sudoku. Jedno z možných řešení, je řešení hrubou silou v C#. Nejprve vytvoříme pouze konzolovou aplikaci, abychom si ověřili, že náš program funguje. Potom uděláme uživatelský interface v Xamarinu, abychom mohli aplikaci používat i v mobilu. Celý kurz vlastně není o řešení sudoku, protože na internetu je mnoho Sudoku Solvers, ale spíše o algoritmizaci, ladění programu a o srozumitelných a snadno pochopitelných algoritmech.

V příští lekci, Tvorba sudoku v Xamarin - Vytvoření projektu, si vytvoříme projekt Xamarin Forms a otestujeme propojení aplikace s mobilním telefonem.

Měl jsi s čímkoli problém? Zdrojový kód vzorové aplikace je ke stažení každých pár lekcí. Zatím pokračuj dál, a pak si svou aplikaci porovnej se vzorem a snadno oprav.