8 dam (konzolová aplikace) v .NET

Vytvořte program, který na klasickou šachovnici 8x8 umístí 8 dam tak, aby se vzájemně nenapadaly. Program má za úkol nalézt a vypsat všechny možné pozice 8 dam, ve kterých se žadná dvojice dam nenapadá. Ve výsledném výpisu eliminujte pozice, které vzniknou z jiné pozice pouhým pootočením šachovnice nebo zrcadlovým přeskládáním dam.

Na tuto klasickou úlohu narazíte na většině škol zabývající se programováním (výsledek na obrázku), nám velmi dobře poslouží k ukázání dalších možností .NET platformy (výsledky v konzolové, okenní či web aplikaci). Mrkněme na schémátko, které ukazuje algoritmus řešení úlohy. Snad se v tom vyznáte, v hranatých závorkách jsem uvedl odpovídající čísla řádků ve zdrojovém (8dam.cs) kódu.

   -------------------------------------------------------
   |   Cyklujeme pro všechny řádky a sloupce šachovnice  |
   |            Začínáme řádek 1 sloupec 1 [194-198]     |
   -------------------------------------------------------
                             |
            -----------------ˇ-----------------
----------->|   Kontrolujeme ohrožení  [207]  |<-------------
|           -----------------------------------             |
|                    |                   |                  |
|  ------------------ˇ-------  ----------ˇ----------------- |
|  | JE ohrožení  [253-271] |  | NENÍ ohrožení  [209-250] | |
|  --------------------------  ---------------------------- |
|            |                           |                  |
|  ----------ˇ---------------  ----------ˇ---------------   |
|  | posun se na další      |  | zaznamenáme dámu [211] |   |
|  | políčko [251]          |  | a jdeme o řádek dolů   |   |
|  --------------------------  --------------------------   |
|        |             |             |             |        |
|  ------ˇ-----  ------ˇ-----  ------ˇ-----  ------ˇ-----   |
|  | je       |  | není     |  | není [220]  | je další |   |
|<-| vedlejší |  | vedlejší |  | řádek => |  | řádek    |   |
|  | políčko  |  | políčko  |  | poslední |  | [243]    |   |
|  | [266]    |  | [258]    |  | dáma     |  |          |   |
|  |          |  |          |  | zapsána  |  |          |   |
|  ------------  ------------  ------------  ------------   |
|                      |             |             |        |
|                ------ˇ-----  ------ˇ----------   ˇ---------
|                | o řádek  |  | uchovávám     |
|                | výše na  |  | výsledek [231]|
|                | políčko  |  -----------------
|        --------| za dámou |           |
|        |       |    [276] |<-------ˇ
|        |       ------------
|        |             |
|  ------ˇ-----  ------ˇ-----
|  | je [288] |  | není[287]|
|  | řádek => |  | řádek    |
|  ------------  ------------
|        |             |
----------       ------ˇ-----
                 |  Konec   |
                 ------------

Je to algoritmus tzv. backtracking neboli prohledávání stavového prostoru s návratem, co to znamená? Prohledáváme stavový prostor (stav = aktuální umístění dam na šachovnici např.) tak, že zkoušíme všechny přípustné umístění dam. Pokud z nějakého stavu není možné pokračovat dále (většinou když nejde dáma umístit na řádek) vrátíme se do stavu, ze kterého jsme přišli a odtud pak zkusíme další pokračování => odtud výraz backtracking.

V uvedeném schématu algoritmu šitého pro tuto úlohu, který je notoricky známý jsou důležité tzv. heuristiky což jsou jakési informace, návody o řešeném problému. Čím více takových heuristik máme, tím zpravidla bývá program podstatně rychlejší. Tak např. v našem případě pokud umístíme dámu na libovolném řádku, je jasné, že už v tomtéž řádku (dokonce i sloupci žádná dáma být nemůže => je tedy zbytečné pokoušet se umísťovat další dámu na řádek ve kterém již jedna dáma je. Taktéž je jasné, že když např. umístíme čtyři neohrožující se dámy (jsou na čtyřech řádcích) a snažíme se umístit pátou dámu, pokud jsou všechna políčka v pátém řádku ohrožována, není žádoucí snažit se umísťovat (pátou) dámu na šestém řádku, protože i kdybychom ji umístili, zbývající (šestou, sedmou a osmou) dámu se nám stejně nepodaří umístit na zbylé dva řádky. Proto taková situace okamžitě musí vyvolat návrat do předchozího možného pokračovatelného stavu.

Metoda tzv. hrubé síly (tzn. procházet všechny možné tahy) se u této úlohy neuplatní a to i když budeme mít pořádný procák, pokud se nemýlím tak hrubý odhad časové složitosti takového přístupu by byl 64⁸, což bude asi velké číslo.

Vlastní realizaci provedeme pomocí konzolové .NET aplikace. Vytvořme si soubor např. "8dam.cs", který nebudeme kompilovat ve Visual studio .NET, ale pomocí příkazové řádky utilitou "csc.exe" takto nějak:

csc /t:exe /r:System.dll /r:System.Data.dll /r:System.Xml.dll 8dam.cs

Parametry za "/r" jsou naše užité namespacy. Výsledkem bude jeden exe soubor v Microsoft Intermediate Language kodu (MSIL). Takový EXE lze spouštět na počítači kde je .NET framework. Podobně jako v jazyku C/C++ program začíná hlavní funckí Main(string[] args) s příchozími parametry příkazové řádky. Výpisy na obrazovku provedeme pomocí funkce Console.Write­Line("Hello World!"); Na začátku souboru vyjmenujeme namespacy, ze kterých užíváme třídy .NET frameworku např using System; using System.Data; atd. Celý kod souboru uzavřeme do našeho namespace např. namespace ConsoleApplication {} a naší třídy např. class _8DAM {}. Tak a máme konzolovou aplikaci hotovou . Ale my chceme, aby taky něco uměla takže tady je: a níže ji zkusím trochu přiblížit.

/**001**/// -_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_
/**002**///
/**003**///                                  8DAM.cs
/**004**///                                 [8 Queens]
/**005**///
/**006**///                          2004-02-14 by Michael
/**007**///                           [email protected]
/**008**///
/**009**///                       Compiled by csc.exe utility
/**010**///
/**011**///          Microsoft (R) Visual C# .NET Compiler version 7.00.9466
/**012**///             for Microsoft (R) .NET Framework version 1.1.4322
/**013**///       Copyright (C) Microsoft Corporation 2001. All rights reserved.
/**014**///
/**015**///    Vytvorte program, ktery na klasickou sachovnici 8x8 umisti 8 dam
/**016**///    tak, aby se vzajemne nenapadaly. Program ma za ukol nalezt a vypsat
/**017**///    vsechny mozne pozice 8 dam, ve kterych se zadna dvojice dam nenapada.
/**018**///    Ve vyslednem vypisu eliminujte pozice, ktere vzniknou z jine pozice
/**019**///    pouhym pootocenim sachovnice nebo zrcadlovym preskladanim dam.
/**020**///
/**021**/// -_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_
/**022**/using System;
/**023**/using System.Data;
/**024**/
/**025**/namespace ConsoleApplication
/**026**/{
/**027**/        class _8DAM
/**028**/        {
/**029**/
/**030**/                // struktura typu DataSet, zde budou vsechny nase sachovnice typu DataTable (DataSet obsahuje vice DataTables => vice sachovnic)
/**031**/                static DataSet Desk = new DataSet();
/**032**/
/**033**/                static int PocetReseni = 0;
/**034**/                static int PocetUnikatnichReseni = 0;
/**035**/                static int PocetKroku = 0;
/**036**/
/**037**/                // The main entry point for the application.
/**038**/                static int Main(string[] args)
/**039**/                {
/**040**/
/**041**/                        Console.WriteLine("Program 8 dam...");
/**042**/
/**043**/                        // vloz prvni hraci plochu
/**044**/                        AddDesk();
/**045**/                        ActionSach();
/**046**/
/**047**/                        // WriteDesk(0);
/**048**/
/**049**/                        ZjistiJedinecne();
/**050**/
/**051**/                        return 1;
/**052**/                }
/**053**/
/**054**/                static void AddDesk()
/**055**/                {
/**056**/                        // vezmeme pocet dosavadnich tabulek ve strukture DataSet
/**057**/                        int NumTables = Desk.Tables.Count;
/**058**/                        // pridej do datasetu novou tabulku
/**059**/                        Desk.Tables.Add("" + NumTables);
/**060**/                        // pridame osm sloupu typu int
/**061**/                        for (int i=0; i<8; i++)
/**062**/                        {
/**063**/                                Desk.Tables[NumTables].Columns.Add("id" + i, Type.GetType("System.Int32"));
/**064**/                        }
/**065**/                        // vloz osm radku s nulovymi hodnotami ve sloupcich
/**066**/                        for (int i=0; i<8; i++)
/**067**/                        {
/**068**/                                // objekt radek
/**069**/                                DataRow Radek;
/**070**/                                // utvor strukturu radku z tabulky datasetu
/**071**/                                Radek = Desk.Tables[NumTables].NewRow();
/**072**/                                // pro vsech osm sloupcu nastavime nulove hodnty
/**073**/                                for (int j=0; j<8; j++)
/**074**/                                {
/**075**/                                        // pocatecni nulove hodnoty pro vsech osm sloupcu
/**076**/                                        Radek[j] = 0;
/**077**/                                }
/**078**/                                // vlozime do kolekce radku radek
/**079**/                                Desk.Tables[NumTables].Rows.Add(Radek);
/**080**/                        }
/**081**/                }
/**082**/
/**083**/                static bool WriteDesk(int intDesk)
/**084**/                {
/**085**/
/**086**/                        // osetrime spravnost vstupu, jinak by doslo k vyjimce (chybne indexovani)
/**087**/                        if (intDesk >= Desk.Tables.Count)
/**088**/                        {
/**089**/                                Console.WriteLine("Spatne cislo hraci desky. (mimo rozsah)");
/**090**/                                return false;
/**091**/                        }
/**092**/
/**093**/                        // radek po radky, sloupec po sloupci vypiseme hodnotu dane sachovnice
/**094**/                        for (int i=0; i<8; i++)
/**095**/                        {
/**096**/                                for (int j=0; j<8; j++)
/**097**/                                {
/**098**/                                        if ((int) Desk.Tables[intDesk].Rows[i][j] == 1)
/**099**/                                        {
/**100**/                                                Console.Write("* ");
/**101**/                                        }
/**102**/                                        else
/**103**/                                        {
/**104**/                                                Console.Write("- ");
/**105**/                                        }
/**106**/                                }
/**107**/                                Console.WriteLine();
/**108**/                        }
/**109**/
/**110**/                        return true;
/**111**/                }
/**112**/
/**113**/                // vrati zda zadane policko neni ohrozeno damou ve vsech moznych smerech
/**114**/                static bool getPosOk(int intDesk, int x, int y)
/**115**/                {
/**116**/
/**117**/                        // funkce kontroluje neohrozenost policka jinou damou
/**118**/                        int i, j;
/**119**/
/**120**/                        // zjisteni zda na radku se naleza nejaka "dama" (reprezentovana jednickou)
/**121**/                        for (j=0; j<8; j++)
/**122**/                        {
/**123**/                                if ((int) Desk.Tables[intDesk].Rows[x][j] == 1) return false;         // pokud je nalezena funkce vraci false
/**124**/                        }
/**125**/                        // zjisteni zda ve sloupci se naleza nejaka "dama" (reprezentovana jednickou)
/**126**/                        for (i=0; i<8; i++)
/**127**/                        {
/**128**/                                if ((int) Desk.Tables[intDesk].Rows[i][y] == 1) return false;         // pokud je nalezena funkce vraci false
/**129**/                        }
/**130**/                        // nasleduje zjisteji mozne damy v "sikminach"
/**131**/                        for (i=x-1, j=y-1; i>-1 && j>-1; i--, j--)
/**132**/                        {
/**133**/                                if ((int) Desk.Tables[intDesk].Rows[i][j] == 1) return false;
/**134**/                        }
/**135**/                        for (i=x+1, j=y+1; i<8 && j<8; i++, j++)
/**136**/                        {
/**137**/                                if ((int) Desk.Tables[intDesk].Rows[i][j] == 1) return false;
/**138**/                        }
/**139**/                        for (i=x-1, j=y+1; i>-1 && j<8; i--, j++)
/**140**/                        {
/**141**/                                if ((int) Desk.Tables[intDesk].Rows[i][j] == 1) return false;
/**142**/                        }
/**143**/                        for (i=x+1, j=y-1; i<8 && j>-1; i++, j--)
/**144**/                        {
/**145**/                                if ((int) Desk.Tables[intDesk].Rows[i][j] == 1) return false;
/**146**/                        }
/**147**/
/**148**/                        return true;
/**149**/                }                                               // konec tela funkce
/**150**/
/**151**/                // kopiruje sachovnici z jedne desky do druhe
/**152**/                static void CopySach(int intDeskSRC, int intDeskDST)
/**153**/                {
/**154**/                        int i,j;
/**155**/                        for (i=0; i<8; i++)
/**156**/                        {
/**157**/                                for (j=0; j<8; j++)
/**158**/                                {
/**159**/                                        Desk.Tables[intDeskDST].Rows[i][j] = (int) Desk.Tables[intDeskSRC].Rows[i][j];
/**160**/                                }
/**161**/                        }
/**162**/                }
/**163**/
/**164**/                // velka proceduralni cast
/**165**/                static void ActionSach()                            // procedura zjistuje pozice 8 dam
/**166**/                {
/**167**/
/**168**/                        // urcuje index do aktualniho ukladaciho pole "< 92" 92 = pocet reseni
/**169**/                        int akt = 0;
/**170**/
/**171**/                        // hodnota pocitadla kroku, kolik kroku pocitac projede
/**172**/                        int Steps = 0;
/**173**/
/**174**/                        // "semafor" urcuje zda je konec radku, nebo sloupce
/**175**/                        bool blnUP = false;
/**176**/
/**177**/                        // pole pro uchovani DAM v kazdem radku je max jedna Dama
/**178**/                        // staci tedy jednorozmerne pole, (index urcuje rade), hodnota pak sloupec umisteni
/**179**/                        // hodnota 255 urcuje nezaplnene pole damov
/**180**/                        // tato struktura je celkem zbytecna, protoze uchovavani dam je v PoleSachovnic[akt][i][j] dane aktualni sachovnici "akt"
/**181**/                        // ale jde o zjednoduceni, nemusi se nejakym algoritmem hledat predchozi umisteni damy (v pripade, ze cesta nevede k
/**182**/                        // cili a musime se vratit /BackTrackin/), prave proto se pouzije tato struktura /jednoduchym indexovanim/
/**183**/                        byte[] DAMY = new byte[8];
/**184**/
/**185**/                        // pomocna promenna
/**186**/                        byte XX = 0;
/**187**/
/**188**/                        int i, j, y;
/**189**/
/**190**/                        // inicializuj pocatecni umisteni dam do pomocne promenne, hodnota 0xff => zadne umisteni
/**191**/                        for (y=0; y<8; y++) DAMY[y] = 0xff;
/**192**/
/**193**/                        // cyklujeme pro radky sachovnice (aktualni hodnota "i" se meni i ve vlastnim tele cyklu -> je upravovana)
/**194**/                        for (i=0; i<8; i++)
/**195**/                        {
/**196**/                                // cyklujeme pro sloupce, hodnota XX se meni v tele cyklu
/**197**/                                for (j=XX; j<8; j++)
/**198**/                                {
/**199**/
/**200**/                                        // pocitej vsechny kroky, ktere pocitac provadi
/**201**/                                        Steps ++;
/**202**/
/**203**/                                        // vypis hodnot indexu
/**204**/                                        // fprintf(fc2, "\n%i%c%i", i, 0x9, j);
/**205**/
/**206**/                                        // jestlize neni ohrozeno
/**207**/                                        if (getPosOk(akt, i, j) == true)
/**208**/                                        {
/**209**/
/**210**/                                                // muzeme zaznamenam damu -> uspesnost
/**211**/                                                Desk.Tables[akt].Rows[i][j] = 1;
/**212**/
/**213**/                                                // uchovavam si pozici damy pro testovani a mazani
/**214**/                                                DAMY[i] = (byte) j;
/**215**/
/**216**/                                                // na prvni policko, protoze v tomto nalezenem radku nemuze jiz nikde byt dama
/**217**/                                                XX=0;
/**218**/
/**219**/                                                // ? neni dalsi radek (testuj zda dalsi radek je k dispozici)
/**220**/                                                if (i+1 == 8)
/**221**/                                                {
/**222**/
/**223**/                                                        // neni dalsi radek -> povedlo se zapsat damu => uspesna osmice dam je na svete
/**224**/
/**225**/                                                        // nastav semafor na testovaci operace (konec radku, nebo sloupce)
/**226**/                                                        blnUP = true;
/**227**/
/**228**/                                                        // tady si muzeme treba damy vypsat cyklovat pro radky i sloupce
/**229**/
/**230**/                                                        // uchovani vysledku v pameti, kopirujem aktualni sachovnici do nasledujici sachovnice (mezitim si ji pridame)
/**231**/                                                        AddDesk();
/**232**/                                                        // a kopirujeme
/**233**/                                                        CopySach(akt, akt+1);
/**234**/
/**235**/                                                        // pricteme index do aktualne zpracovavane sachovnice (a take index poctu spravnych reseni)
/**236**/                                                        akt ++;
/**237**/
/**238**/                                                        Desk.Tables[akt].Rows[i][DAMY[i]] = 0;
/**239**/
/**240**/                                                        // ukonci cyklus, je zbytecne prochazet do konce
/**241**/                                                        break;
/**242**/                                                }
/**243**/                                                // je dalsi radek
/**244**/                                                else
/**245**/                                                {
/**246**/                                                        // je alespon jeden dalsi radek sachovnice ukonci cyklus pro sloupce a pokracuj na dalsim radku
/**247**/                                                        break;
/**248**/                                                }
/**249**/
/**250**/                                        }
/**251**/                                        // jinak je ohrozeno
/**252**/                                        else
/**253**/                                        {
/**254**/
/**255**/                                                // posun se na vedlejsi policko (automaticky v dalsim cyklu for)
/**256**/
/**257**/                                                // jestlize neni dalsi policko
/**258**/                                                if (j+1 == 8)
/**259**/                                                {
/**260**/
/**261**/                                                        // nastav semafor a ukonci cyklus (cyklus je ukonce automaticky => neni dalsi podminka pro for)
/**262**/                                                        blnUP = true;
/**263**/                                                        // break;
/**264**/
/**265**/                                                }
/**266**/                                                // je dalsi policko
/**267**/                                                else
/**268**/                                                {
/**269**/                                                }
/**270**/
/**271**/                                        }
/**272**/
/**273**/                                }
/**274**/
/**275**/
/**276**/                                // jestlize je konec radku nebo sloupce => vracime se o radek zpet
/**277**/                                if (blnUP == true)
/**278**/                                {
/**279**/
/**280**/                                        // vyrus semafor
/**281**/                                        blnUP = false;
/**282**/
/**283**/                                        // posun se o radek nahoru
/**284**/                                        i--;
/**285**/
/**286**/                                        // backtrack navrat o radek zpet -> neni dalsi radek ukoncujeme => konec procesu
/**287**/                                        if (i < 0) break;
/**288**/                                        else
/**289**/                                        {
/**290**/
/**291**/                                                // nastaveni indexu v dalsim cyklu v radku (posunuti za predchozi damu)
/**292**/                                                XX = (byte) (DAMY[i] + 1);
/**293**/
/**294**/                                                // a take musime tuto predchozi damu vymazat
/**295**/                                                Desk.Tables[akt].Rows[i][DAMY[i]] = 0;
/**296**/
/**297**/                                                // vymazeme i z druhe struktury => nastavime prazdne umisteni damy
/**298**/                                                DAMY[i] = 0xff;
/**299**/
/**300**/                                                // jestlize ovsem novy index je mimo rozsah (posunuli jsme se totiz o radek vyse /a tam mohla byt umistena dama na konci radku/ )
/**301**/                                                if (XX == 8)
/**302**/                                                {
/**303**/                                                        // musime zopakovat testy ...
/**304**/
/**305**/                                                        // posun se jeste o dalsi radek
/**306**/                                                        i--;
/**307**/                                                        if (i < 0) break;
/**308**/
/**309**/                                                        // nastaveni indexu v dalsim cyklu v radku (posunuti za predchozi damu)
/**310**/                                                        XX = (byte) (DAMY[i] + 1);
/**311**/
/**312**/                                                        // a take musime tuto predchozi damu vymazat
/**313**/                                                        Desk.Tables[akt].Rows[i][DAMY[i]] = 0;
/**314**/
/**315**/                                                        // vymazeme i z druhe struktury => nastavime prazdne umisteni damy
/**316**/                                                        DAMY[i] = 0xff;
/**317**/
/**318**/                                                }
/**319**/
/**320**/                                                // jeste vyse, dojde k pripocitani
/**321**/                                                i--;
/**322**/
/**323**/                                        }
/**324**/
/**325**/                                }
/**326**/
/**327**/                        }
/**328**/
/**329**/                        // uchovej hodnoty v lokalnich promennych do globalnich
/**330**/                        PocetReseni = akt;
/**331**/                        PocetKroku = Steps;
/**332**/
/**333**/                        // vypis vysledky na obrazovku
/**334**/                        Console.WriteLine("Nalezenych reseni: {0}", PocetReseni);
/**335**/                        Console.WriteLine("Pocet kroku:       {0}", Steps);
/**336**/
/**337**/                }
/**338**/
/**339**/                // procedura hleda unikatni jedince ze vsech nalezenych resenich
/**340**/                static void ZjistiJedinecne()
/**341**/                {
/**342**/                        // pole "kratkych" integeru, kde si uchovame cisla unikatnich reseni, alokujeme pamet velikosti PoctuReseni vice totiz unikatnich reseni byt nemuze.
/**343**/                        short[] UNI = new short[PocetReseni];
/**344**/
/**345**/                        int p, u;                               // pomocne indexni promenne
/**346**/                        int i, j;                               // pomocne indexni promenne
/**347**/
/**348**/                        // pole detekci stejny slozek, pocet [8] je shodny s poctem testovanych smeru (otoceni o 90s), o dalsich 90 s. horizontalne atd...
/**349**/                        byte[] same = new byte[8];
/**350**/
/**351**/                        // hodnota urcujici zda budeme pridavat uniktani reseni
/**352**/                        bool Add;
/**353**/
/**354**/                        // prochazej vsechny nalezene reseni
/**355**/                        for (p=0; p<PocetReseni; p++)
/**356**/                        {
/**357**/                                // inicializuj pro pridavani aktualniho reseni
/**358**/                                Add = true;
/**359**/
/**360**/                                // cyklujeme vsemi dosavadnimi resenimi
/**361**/                                for (u=0; u<PocetUnikatnichReseni; u++)
/**362**/                                {
/**363**/                                        // nuluj vsechny pomocne pole
/**364**/                                        for (i=0; i<8; i++) same[i] = 0;
/**365**/
/**366**/                                        // cykluj vsemi radky sachovnice
/**367**/                                        for (i=0; i<8; i++)
/**368**/                                        {
/**369**/                                                // sloupci
/**370**/                                                for (j=0; j<8; j++)
/**371**/                                                {
/**372**/                                                        // (zjisteni shodnosti sachovnic) pricitej do pomocnych poli podle stavu natoceni
/**373**/
/**374**/                                                        // aktualni podoba
/**375**/                                                        if (((int) Desk.Tables[p].Rows[i][j]) == ((int) Desk.Tables[UNI[u]].Rows[i][j])) same[0] ++;
/**376**/                                                        // otoceni o 90 stupnu
/**377**/                                                        if (((int) Desk.Tables[p].Rows[j][7-i]) == ((int) Desk.Tables[UNI[u]].Rows[i][j])) same[1] ++;
/**378**/                                                        // otoceni o 2*90 stupnu
/**379**/                                                        if (((int) Desk.Tables[p].Rows[7-i][7-j]) == ((int) Desk.Tables[UNI[u]].Rows[i][j])) same[2] ++;
/**380**/                                                        // otoceni o 3*90 stupnu
/**381**/                                                        if (((int) Desk.Tables[p].Rows[7-j][i]) == ((int) Desk.Tables[UNI[u]].Rows[i][j])) same[3] ++;
/**382**/
/**383**/                                                        // aktualni podoba (otocena horizontalne)
/**384**/                                                        if (((int) Desk.Tables[p].Rows[i][7-j]) == ((int) Desk.Tables[UNI[u]].Rows[i][j])) same[4] ++;
/**385**/                                                        // otoceni o 90 stupnu + (otoceni horizontalne)
/**386**/                                                        if (((int) Desk.Tables[p].Rows[j][i]) == ((int) Desk.Tables[UNI[u]].Rows[i][j])) same[5] ++;
/**387**/                                                        // otoceni o 2*90 stupnu + (otoceni horizontalne)
/**388**/                                                        if (((int) Desk.Tables[p].Rows[7-i][j]) == ((int) Desk.Tables[UNI[u]].Rows[i][j])) same[6] ++;
/**389**/                                                        // otoceni o 3*90 stupnu + (otoceni horizontalne)
/**390**/                                                        if (((int) Desk.Tables[p].Rows[7-j][7-i]) == ((int) Desk.Tables[UNI[u]].Rows[i][j])) same[7] ++;
/**391**/
/**392**/                                                }
/**393**/                                        }
/**394**/
/**395**/                                        // zbyva jenom otestovat zda
/**396**/                                        for (i=0; i<8; i++)
/**397**/                                        {
/**398**/                                                // zda v nekterych natocenich bylo vsech 64 poli shodnych
/**399**/                                                if (same[i] == 64)
/**400**/                                                {
/**401**/                                                        // v tom pripade sachovnice neni unikatni
/**402**/                                                        Add = false;
/**403**/                                                        break;
/**404**/                                                }
/**405**/                                        }
/**406**/                                }
/**407**/
/**408**/                                // jestli jse unikatni, pridej ji
/**409**/                                if (Add==true)
/**410**/                                {
/**411**/                                        UNI[PocetUnikatnichReseni] = (short) p;
/**412**/                                        PocetUnikatnichReseni++;
/**413**/                                }
/**414**/
/**415**/
/**416**/                        }
/**417**/
/**418**/                        // vypis vysledku
/**419**/                        Console.WriteLine("Unikatni reseni: {0}", PocetUnikatnichReseni);
/**420**/                        Console.WriteLine("Pocet sachovnic: {0}", Desk.Tables.Count);
/**421**/                        Console.WriteLine("Unikatni reseni (vypis): ");
/**422**/
/**423**/                        // cykluj pro vsechny unikatni reseni
/**424**/                        for (i=0; i<PocetUnikatnichReseni; i++)
/**425**/                        {
/**426**/                                Console.Write("{0}. reseni: ", i+1);
/**427**/                                for (j=0; j<8; j++)
/**428**/                                {
/**429**/                                        byte k = 0;
/**430**/                                        while ((int) Desk.Tables[UNI[i]].Rows[j][k] == 0) k++;
/**431**/                                        Console.Write("{0}{1} ", (char) (0x41 + j), k + 1);
/**432**/                                }
/**433**/                                Console.WriteLine("");
/**434**/                        }
/**435**/                }
/**436**/        }
/**437**/}

Naše hlavní struktura, kde budeme uchovávat stavy dam bude globální proměnná typu DataSet. Předně upozorňuji že to není výkonově nejlepší řešení (mnohem rychlejší je pracovat s dvojrozměrnými poli čísel), ale naše řešení má hlavní výhodu a to tu, že přesně nevíme kolik řešení úlohy skutečně může být a podle toho kolik cílových stavů nalézáme (korektní zaplnění šachovnice 8 dámami) dynamicky přidáváme "tabulky" do jednoho DataSetu (proměnná Desk). DataSet je dynamická struktura, která zahrnuje více "tabulek" a tyto tabulky mají řádky a sloupce. V našem případě jedna "šachovnice" bude reprezentována jednou tabulkou v DataSetu a tato tabulka bude mít 8 řádku a 8 sloupců. Přidávat takto tabulky dělá naše metoda AddDesk() řadky (ř.) 54–81. Hlavní práci nalezení všech řešení (ještě neunikátních) provede metoda ActionSach(); ř. 164–337. Významnou funkcí je metoda getPosOk(..) která vrátí zda je políčko dané vstupními parametry ohrožováno na zadané šachovnici. Metoda prozkoumá všechny směry vlevo–vpravo–nahoru–dolu–včetně všech šikmin. Vrací bool (true/false). Další metodou bude WriteDesk() která bude pouze pomocná a pomůže nám ladit program, vypisuje zadanou šachovnici na obrazovku. Metoda CopySach() nám vytvoří kopii šachovnice, to proto abychom si uchovali nalezené výsledky. No a poslední metoda ZjistiJedinecne() nám zjistí unikátní řešení úlohy tak, že všechny nalezené řešení porovnává pro různá "natočení" šachovnic. Postupně od 90 stupňů do 270 taktéž o horizontální převrácení. V nejsložitější metodě ActionSach() si uchováváme také poslední umístění dámy v poli bajtu DAMY, to proto abychom se mohli vrátit (backtracking) za poslední dámu v případě neúspěšné cesty.

Příště kod zkompilujeme jako dll knihovnu a použijeme ji současně do konzolové, window a ASP.NET aplikaci.

Galerie