PROGRAMOWANIE – PRZYKŁADY
IDE C++ WinBGI C# Wpadki

Przykład C++

Problem ośmiu hetmanów Wstępne rozwiązanie programowe Drzewo przeszukiwań algorytmu Implementacja algorytmu w C++ Program w C++ Poprzedni przykład Następny przykład Program w Visual C# Kontakt

Problem ośmiu hetmanów

Zgodnie z regułami szachowymi hetman szachuje inne figury ustawione na szacho­wnicy w tym samym wierszu, kolumnie i na przeką­tnych, na których stoi (rys.). Problem ośmiu hetmanów polega na usta­wieniu na szacho­wnicy ośmiu hetmanów tak, aby żaden nie szachował innego. Naszym zadaniem jest opraco­wanie programu bez wejścia (brak wczytywania danych), który znajduje wszystkie układy ośmiu hetmanów stano­wiące rozwią­zanie problemu.

Warto przy okazji wspomnieć, że problemem ośmiu hetmanów zajmował się znako­mity niemiecki matematyk Carl Friedrich Gauss (1777-1855), ale nie udało mu się znaleźć pełnego rozwią­zania. Trudno się temu dziwić, gdyż problemu nie da się rozwiązać anality­cznie, lecz metodą prób i błędów, która ze względów czasowych wymaga użycia komputera. Liczba możliwych ustawień hetmanów na szachownicy po jednym w kolumnie jest przeo­gromna, wynosi 88=16777216. Chociaż tylko niektóre stanowią rozwią­zanie problemu, to te pozostałe trzeba jakoś wyelimi­nować.

Wstępne rozwiązanie programowe

Problem ośmiu hetmanów można rozwiązać za pomocą algorytmu z powrotami polega­jącego na poszuki­waniu rozwią­zania metodą prób i błędów. Jest oczywiste, że w jednej kolumnie szacho­wnicy można ustawić tylko jednego hetmana. Wynika stąd, że po ustawieniu k–1 hetmanów w kolu­mnach od 1 do k–1 należy podjąć próbę znale­zienia takiego wiersza w kolumnie k, żeby pole na skrzyżo­waniu tego wiersza i kolumny nie było szacho­wane przez ustawio­nych już hetmanów. Rozumo­wanie to prowadzi do wstępnego sformuło­wania funkcji podejmu­jącej próbę ustawienia hetmana w kolumnie k i ewentu­alnie kolejnych hetmanów w nastę­pnych kolumnach:

void probuj(int k)
{
    for (int w = 1; w <= 8; w++)
        if (pole (w,k) nie jest szachowane)
        {
            ustaw hetmana w polu (w,k);
            if (k < 8)
                probuj(k + 1);
            else
                zapisz ustawienie hetmanów;
            usuń hetmana z pola (w,k);
        }
}

Funkcja przebiega wszystkie wiersze kolumny określonej w argu­mencie w poszuki­waniu wolnego pola. Jeśli takie pole zostaje znale­zione, umieszcza w nim hetmama i wywołuje rekuren­cyjnie samą siebie dla następnej kolumny, gdy taka kolumna istnieje, albo zapamię­tuje ustawienie wszystkich hetmanów, gdy jest to ostatnia kolumna szacho­wnicy. Na koniec funkcja usuwa hetmana z tego pola, by było wolne przy rekuren­cyjnym podejmo­waniu prób dla następnych pól tej samej kolumny i kolumn o niższych numerach.

Algorytm uaktywniamy za pomocą wywołania funkcji probuj z argu­mentem 1, które rozpo­czyna poszuki­wanie ustawień ośmiu hetmanów od kolumny 1, czyli dla szacho­wnicy, na której żaden hetman nie jest ustawiony.

Drzewo przeszukiwań algorytmu

Działanie algorytmu możemy prześledzić na jego drzewie przeszu­kiwań, którego początkowy fragment jest pokazany na poniż­szym rysunku. Z każdego wierz­chołka, którego numer jest wartością argu­mentu k wywołania funkcji probuj, wiedzie osiem krawędzi do wierz­chołków o numerach równych wartości wyrażenia k+1. Krawędzie te odpowia­dają wartościom od 1 do 8 zmiennej w steru­jącej pętlą for, czyli numerom przeglą­danych wierszy szacho­wnicy w poszuki­waniu wolnego pola w kolu­mnie k. Część tych krawędzi jest obcinana, przez co wywodzące się od nich poddrzewa są elimi­nowane z dalszych poszukiwań, ponieważ prowadzą do "ślepego zaułka".

Pierwszego hetmana możemy ustawić w każdym z ośmiu wierszy pierwszej kolumny, dlatego z wierz­chołka 1 wychodzi osiem krawędzi do wierz­chołków 2. Gdy ustawimy go w pierwszym wierszu, drugiego hetmana możemy ustawić w wierszach od trzeciego do ósmego drugiej kolumny, dlatego dwie krawędzie wychodzące z wierz­chołka 2 są obcięte. Z kolei trzeciego hetmana, przy usta­wieniu pierwszego w wierszu pierwszym i drugiego w trzecim, możemy ustawić dopiero w piątym wierszu trzeciej kolumny, skutkiem tego cztery krawędzie wychodzące z wierz­chołka 3 są obcięte. Generalnie obcinane są te krawędzie, a wraz z nimi całe poddrzewa, które opisują drogę nieprowa­dzącą do rozwią­zania, gdyż określają ustawienie kolejnego hetmana w polu szacho­wanym.

Dotarcie do wierzchołka o numerze 8 oznacza, że osiem hetmanów zostało ustawionych na szacho­wnicy w taki sposób, że żaden z nich nie szachuje żadnego innego. Znalezione ustawienie hetmanów stanowi zatem rozwiązanie problemu, dlatego zamiast kolejnego wywołania rekuren­cyjnego zostaje zapisane w rejestrze wszystkich rozwiązań.

Implementacja algorytmu w C++

Znaleźliśmy się w sytuacji, w której powinniśmy podjąć decyzje dotyczące reprezen­towania danych. Narzuca­jącą się reprezen­tacją szacho­wnicy jest tablica dwuwymia­rowa typu bool o rozmiarze 8x8, której elementy o wartości false oznaczają brak, a true obecność hetmana w określo­nych przez nie polach. Wówczas sprawdzenie, czy pole, na którym ma być ustawiony hetman, nie jest szachowane, można by sprecy­zować w postaci funkcji C++. Zważywszy jednak na fakt, że będzie to najczęściej wykonywana operacja, warto pokusić się o lepszą reprezen­tację danych, która pozwala­łaby na bardziej bezpo­średni test, czy w danym polu wolno ustawić hetmana.

Interesującą reprezentację danych zaproponował Niklaus Wirth w książce pt. Algorytmy + struktury danych = programy (WNT, Warszawa 1980 i nowsze wydania, obecnie niedo­stępne). Wykorzystując fakt, że wszystkie pola leżące na przeką­tnej o kierunku ⬈ charakte­ryzują się stałą wartością k+w (numer kolumny + numer wiersza), a pola na przeką­tnej ⬊ stałą wartością k–w, użył czterech tablic do określenia pozycji hetmana i stanu pola. Zaprezen­towany w notacji języka Pascal pomysł prowadzi w C++, z uwzglę­dnieniem natu­ralnej w tym języku indeksacji elementów tablic od zera wzwyż, do dekla­racji tablic:

int x(8);
bool a[8], b[15], c[15];

Znaczenie ich elementów jest następujące:

Nietrudno zauważyć, że test sprawdzający, czy pole na skrzyżo­waniu kolumny k i wiersza w nie jest szacho­wane, sprowadza się teraz do obliczenia wartości wyrażenia logicznego

a[w] & b[k + w] & c[k - w + 7]

Operację ustawienia w tym polu hetmana można zapisać za pomocą następu­jących przypisań:

x[k] = w;
a[w] = b[k + w] = c[k - w + 7] = false;

Prosta jest również operacja usunięcia hetmana:

a[w] = b[k + w] = c[k - w + 7] = true;

Przed sformułowaniem ostatecznej wersji funkcji probuj powinniśmy zdecy­dować, gdzie ma ona zapisywać znajdowane rozwią­zania reprezen­towane przez tablice ośmiu numerów wierszy określa­jących ustawienie hetmanów na szacho­wnicy. Ponieważ liczba wszystkich rozwiązań nie jest znana, rozsądnym wydaje się groma­dzenie ich w obiekcie klasy vector. Elemen­tami wektora nie mogą być jednak zwykłe tablice, ale mogą być wektory. Zatem zmienne używane przez funkcję probuj możemy zadekla­rować następu­jąco:

bool a[8], b[15], c[15];
vector<vector<int>> rozw;
vector<int> x(8);

Uwaga. Kompilatory Borland C++ i MinGW C++ wymagają spacji pomiędzy znakami >> w dekla­racji wektora rozw.

Utworzony przez konstruktor wektor x nie jest pusty, ma osiem elementów typu int. Można go więc od razu bez dopisywania nowych elementów używać jak zwykłą tablicę o ośmiu elementach całko­witych. Za każdym razem po wygene­rowaniu w nim ustawienia ośmiu hetmanów jego zawartość możemy dodać do wektora rozw jako nowy element, tworząc w ten sposób kolekcję wszystkich rozwiązań problemu. Uwzglę­dniając nume­rację kolumn i wierszy szachownicy od 0 do 7, ostateczną wersję funkcji probuj możemy sformu­łować następu­jąco:

void probuj(int k)
{
    for (int w = 0; w < 8; w++)
        if (a[w] & b[k + w] & c[k - w + 7])
        {
            x[k] = w;
            a[w] = b[k + w] = c[k - w + 7] = false;
            if (k < 7)
                probuj(k + 1);
            else
                rozw.push_back(x);
            a[w] = b[k + w] = c[k - w + 7] = true;
        }
}

Funkcję probuj należy wywołać po raz pierwszy z argumen­tem 0 określa­jącym rozpoczęcie działania algorytmu poszuki­wania rozwiązań od pustej szacho­wnicy. Naturalnie wszystkie elementy tablic a, bc powinny być zainicja­lizowane wartościami true oznacza­jącymi, że wszystkie pola szacho­wnicy są wolne:

for (int k = 0; k < 8; k++)
    a[k] = true;
for (int k = 0; k < 15; k++)
    b[k] = c[k] = true;
probuj(0);

Program w C++

Pełny program w C++ znajdujący wszystkie rozwią­zania problemu ośmiu hetmanów jest przedsta­wiony na poniższym listingu. Tworząc ten program, przyjęto założenie, że ma on wyświe­tlać na ekranie listę tych rozwiązań i prezen­tować każde z nich w postaci obrazu ukazu­jącego ustawienie hetmanów na szacho­wnicy. Aby uniknąć niezgo­dności biblio­teki grafi­cznej WinBGI z biblio­teką standar­dową conio (różne implemen­tacje funkcji getch), zdecy­dowano się na tworzenie obrazu szacho­wnicy i hetmanów w trybie tekstowym za pomocą znaków semigra­ficznych '\xdb' (zapeł­niony cały prosto­kącik znaku), '\xdc' (zapeł­niona dolna połowa prosto­kącika) i '\xdf' (zapeł­niona górna połowa prosto­kącika).

#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include "bconio.h"
#include "klaw.h"

using namespace std;

const int SX = 8, SY = 5;        // Pozycja szachownicy
const int LX = 47, LY = 6;       // Pozycja listy rozwiązań

bool a[8], b[15], c[15];
vector<vector<int>> rozw;
vector<int> x(8);

void probuj(int k)
{
    for (int w = 0; w < 8; w++)
        if (a[w] & b[k + w] & c[k - w + 7])
        {
            x[k] = w;
            a[w] = b[k + w] = c[k - w + 7] = false;
            if (k < 7)
                probuj(k + 1);
            else
                rozw.push_back(x);
            a[w] = b[k + w] = c[k - w + 7] = true;
        }
}

void plansza()
{
    gotoxy(30, 2);
    cout << "Problem ośmiu hetmanów";
    gotoxy(SX - 1, SY - 1);
    for (int k = 0; k < 8 * 4 + 2; k++)
        cout << "\xdc";
    for (int w = 0; w < 8 * 2; w++)
    {
        gotoxy(SX - 1, SY + w);
        cout << "\xdb";
        gotoxy(SX + 8 * 4, SY + w);
        cout << "\xdb";
    }
    gotoxy(SX - 1, SY + 2 * 8);
    for (int k = 0; k < 8 * 4 + 2; k++)
        cout << "\xdf";
    gotoxy(LX + 1, LY - 2);
    cout << "Lp Poz. hetmana w wierszu";
    gotoxy(LX, LY - 1);
    cout << "-----------------------------";
    gotoxy(30, 23);
    cout << "Menu: Up, Dn, Home, End, ESC";
}

void pole(int w, int k, bool hetman)
{
    const string P[] = { "    ", " \xdc\xdc ", " \xdf\xdf " };
    textbackground((w + k) % 2 == 0 ? WHITE : LIGHTGRAY);
    gotoxy(SX + 4 * k, SY + 2 * w);
    int h = hetman ? 1 : 0;
    cout << P[h];
    gotoxy(SX + 4 * k, SY + 2 * w + 1);
    if (h > 0) h = 2;
    cout << P[h];
    textbackground(WHITE);
}

void drukuj(unsigned int r)
{
    static unsigned int p = 0;
    if (r < p)
        p = r;
    else if (r > p + 15)
        p = r - 15;
    for (unsigned int n = p; (n < p + 16) && (n < rozw.size()); n++)
    {
        x = rozw[n];
        gotoxy(LX, LY + n - p);
        cout << setw(3) << n + 1 << ((n == r) ? '*' : ' ');
        for (int k = 0; k < 8; k++)
            cout << setw(3) << x[k] + 1;
        if (n == r)
            for (int w = 0; w < 8; w++)
                for (int k = 0; k < 8; k++)
                    pole(w, k, x[k] == w);
    }
    gotoxy(58, 23);
}

void pokaz()
{
    unsigned int r = 0;
    drukuj(r);
    while (true)
        switch (czytajZnak())
        {
            case K_UP:
                if (r > 0) drukuj(--r);
                break;
            case K_DN:
                if (r < rozw.size() - 1) drukuj(++r);
                break;
            case K_HOME:
                if (r > 0) drukuj(r = 0);
                break;
            case K_END:
                if (r < rozw.size() - 1) drukuj(r = rozw.size() - 1);
                break;
            case K_ESC:
                return;
        }
}

int main()
{
    textbackground(WHITE);
    textcolor(BLACK);
    clrscr();
    plansza();
    for (int k = 0; k < 8; k++)
        a[k] = true;
    for (int k = 0; k < 15; k++)
        b[k] = c[k] = true;
    probuj(0);
    pokaz();
    return 0;
}

Jak widać, znacznie obszerniejsza część kodu źródłowego programu dotyczy prezen­tacji rozwiązań niż ich znajdowania. Zadaniem funkcji plansza jest wyświe­tlenie tytułu programu, ramki wokół szacho­wnicy, nagłówka listy rozwiązań i menu informu­jącego o klawiszach steru­jących działaniem programu. Funkcja pole wyświetla w zależności od podanych w argu­mentach numerów wiersza i kolumny białe lub jasno­szare pole szacho­wnicy o rozmiarze 4x2=8 znaków. Trzeci argument określa obecność hetmana. Jeśli ma wartość true, wyświe­tlany jest kwadracik symboli­zujący ustawienie hetmana w tym polu. Z kolei funkcja drukuj wypisuje listę 16 rozwiązań zgroma­dzonych w wektorze rozw, poczynając od indeksu określo­nego w zmiennej lokalnej p zadekla­rowanej z modyfi­katorem static (zmienna i jej wartość nie znikają wraz z zakoń­czeniem wykonania funkcji). Ponadto funkcja wyróżnia gwiazdką rozwią­zanie o indeksie wskazanym w argu­mencie r i wyświetla odpowia­dający mu układ hetmanów na szacho­wnicy. Wartość zmiennej p jest w razie potrzeby po wejściu do funkcji korygo­wana tak, by drukowany fragment listy obejmował rozwią­zanie o indeksie r. Dzięki tej korekcie uzyskujemy za sprawą funkcji pokaz efekt przewi­jania listy rozwiązań. Funkcja ta po wydruko­waniu początko­wego fragmentu listy z wyróż­nionym elementem o indeksie 0 pobiera kolejne znaki z klawia­tury, interpre­tuje je i zgodnie z intencją użytko­wnika zleca wydruk fragmentu listy ze wskaza­niem indeksu wyróżnia­nego rozwią­zania lub kończy prezen­tację znale­zionych rozwiązań problemu.

Uwaga. Ze względu na przejęty po systemie DOS specy­ficzny sposób wyświe­tlania kolorów tekstu i tła w aplika­cjach konso­lowych Borland C++ (zob. program koloro­wania kalen­darza) kod źródłowy rozpatry­wanego programu dla tego środo­wiska różni się od przedsta­wionego powyżej kodu dla środowisk MinGW C++ i Visual C++. Po pierwsze, zamiast strumienia cout w programie używana jest funkcja cprintf z biblioteki conio. Po drugie, ciemne pola szacho­wnicy są wyświe­tlane w kolorze brązowym. Gdyby były jasno­szare, nie różniłyby się od pól jasnych określa­nych jako białe, ponieważ biały kolor tła jest w tym systemie trakto­wany jako jasno­szary.

Algorytm działa bardzo szybko, o czym świadczy pojawienie się wyników programu natych­miast po jego urucho­mieniu. Program znajduje wszystkie 92 rozwią­zania problemu ośmiu hetmanów, ale z uwagi na symetrię szacho­wnicy tylko 12 z nich jest istotnie różnych. Oto okno utworzone przez program bezpo­średnio po jego urucho­mieniu:

a) okno programu w MinGW C++,

b) okno programu w Borland C++.


Opracowanie przykładu: styczeń 2020