8 dam (konzolová aplikácie) v .NET

Vytvorte program, ktorý na klasickú šachovnicu 8x8 umiestni 8 dam tak, aby sa vzájomne nenapadali. Program má za úlohu nájsť a vypísať všetky možné pozície 8 dám, v ktorých sa žadná dvojica dam nenapadá. Vo výslednom výpise eliminujte pozície, ktoré vzniknú z inej pozície jednoduchým pootočením šachovnice alebo zrkadlovým přeskládáním dám.

Na túto klasickú úlohu narazíte na väčšine škôl zaoberajúca sa programovaním (výsledok na obrázku), nám veľmi dobre poslúži na ukázanie ďalších možností .NET platformy (výsledky v konzolovej, okenné či web aplikáciu). Mrkni na schémátko, ktoré ukazuje algoritmus riešení úlohy. Snáď sa v tom vyznáte, v hranatých zátvorkách som uviedol zodpovedajúce čísla riadkov v zdrojovom (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 čiže prehľadávanie stavového priestoru s návratom, čo to znamená? Prehľadávame stavový priestor (stav = aktuálne umiestnenie dam na šachovnici napr.) Tak, že skúšame všetky prípustné umiestnenie dám. Ak z nejakého stavu nie je možné pokračovať ďalej (väčšinou keď nejde dáma umiestniť na riadok) vrátime sa do stavu, z ktorého sme prišli a odtiaľ potom skúsime ďalšie pokračovanie => odtiaľ výraz backtracking.

V uvedenej schéme algoritmu šitého pre túto úlohu, ktorý je notoricky známy sú dôležité tzv. Heuristiky čo sú akési informácie, návody o riešenom probléme. Čím viac takýchto heuristika máme, tým spravidla býva program podstatne rýchlejšie. Tak napr. V našom prípade ak umiestnime dámu na ľubovoľnom riadku, je jasné, že už v tom istom riadku (dokonca aj stĺpci žiadna dáma byť nemôže => je teda zbytočné pokúšať sa umiestňovať ďalšie dámu na riadok v ktorom už jedna dáma je. Taktiež je jasné, že keď napr. Umiestnime štyri neohrozujúce sa dámy (sú na štyroch riadkoch) a snažíme sa umiestniť piatou dámu, ak sú všetky políčka v piatom riadku ohrozovaná, nie je žiaduce snažiť sa umiestňovať (piatu) dámu na šiestom riadku, pretože aj keby sme ju umiestnili, zostávajúce (šiestu, siedmu a ôsmu) dámu sa nám rovnako nepodarí umiestniť na zvyšné dva riadky. Preto taká situácia okamžite musí vyvolať návrat do predchádzajúceho možného pokračovatelného stavu.

Metóda tzv. Hrubej sily (tzn. Prechádzať všetky možné ťahy) sa u tejto úlohy neuplatnia a to aj keď budeme mať poriadny procák, ak sa nemýlim tak hrubý odhad časovej zložitosti takéhoto prístupu by bol 64 ^8, čo bude asi veľké číslo.

Vlastné realizáciu vykonáme pomocou konzolové .NET aplikácie. Vytvorme si súbor napr. "8dam.cs", ktorý nebudeme kompilovať vo Visual štúdio .NET, ale pomocou príkazového riadku utilitou "csc.exe" takto nejako:

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

Parametre za "/ r" sú naše užité namespace. Výsledkom bude jeden exe súbor v Microsoft Intermediate Language kodu (MSIL). Takýto EXE možno spúšťať na počítači kde je .NET framework. Podobne ako v jazyku C / C ++ program začína hlavná funckí Main (string [] args) s prichádzajúcimi parametrami príkazového riadku. Výpisy na obrazovku vykonáme pomocou funkcie Console.WriteLine ( "Hello World!"); Na začiatku súboru vymenujeme namespace, z ktorých užívame triedy .NET frameworku napr using System; using System.Data; atď. Celý kod súboru uzavrieme do nášho namespace napr. namespace ConsoleApplication {} a našej triedy napr. class _8DAM {}. Tak a máme konzolovú aplikáciu hotovú . Ale my chceme, aby tiež niečo vedela takže tu je: a nižšie ju skúsim trochu priblížiť.

/**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é štruktúra, kde budeme uchovávať stavy dam bude globálna premenná typu DataSet. Predovšetkým upozorňujem že to nie je výkonovo najlepšie riešenie (oveľa rýchlejší je pracovať s dvojrozmernými poliami čísiel), ale naše riešenie má hlavnú výhodu a to tú, že presne nevieme koľko riešení úlohy skutočne môže byť a podľa toho koľko cieľových stavov nachádzame (korektné zaplnenie šachovnice 8 dámami) dynamicky pridávame "tabuľky" do jedného dataSet (premenná Desk). Množina údajov je dynamická štruktúra, ktorá zahŕňa viac "tabuliek" a tieto tabuľky majú riadky a stĺpce. V našom prípade jedna "šachovnice" bude reprezentovaná raz tabuľkou v DataSet a táto tabuľka bude mať 8 riadku a 8 stĺpcov. Pridávať takto tabuľky robí naša metóda AddDesk () riadku (r.) 54-81. Hlavné prácu nájdenie všetkých riešení (ešte neunikátních) vykoná metóda ActionSach (); ř. 164-337. Významnou funkciou je metóda getPosOk (..) ktorá vráti či je políčko danej vstupnými parametrami ohrozované na zadané šachovnici. Metóda preskúma všetky smery vľavo-vpravo-hore-dolu-vrátane všetkých šikmín. Vracia bool (true / false). Ďalšou metódou bude WriteDesk () ktorá bude iba pomocné a pomôže nám ladiť program, vypisuje zadanú šachovnicu na obrazovku. Metóda CopySach () nám vytvorí kópiu šachovnice, to preto aby sme si uchovali nájdené výsledky. No a posledná metóda ZjistiJedinecne () nám zistí unikátne riešenie úlohy tak, že všetky nájdené riešenie porovnáva pre rôzne "natočenie" šachovníc. Postupne od 90 stupňov do 270 taktiež o horizontálne prevráteniu. V najzložitejšie metóde ActionSach () si uchovávame tiež posledné umiestnenie dámy v poli bajtu DAMY, to preto aby sme sa mohli vrátiť (backtracking) za posledný dámu v prípade neúspešnej cesty.

Nabudúce kod skompilujeme ako dll knižnicu a použijeme ju súčasne do konzolové, window a ASP.NET aplikáciu.

Galéria