Problem ośmiu hetmanów
Kod był wyświetlany 4257 razy.
    Problem 8 hetmanów - hetman jest figurą szachową, która bije figury znajdujące się w tej samej kolumnie, wierszu lub diagonali co on sam. W jaki sposób rozstawić osiem hetmanów na tradycyjnej szachownicy 8x8 tak, aby wzajemnie się nie atakowały? Ile jest możliwych rozstawień? Przez rozstawienie podstawowe bądź rozwiązanie podstawowe należy rozumieć rozwiązanie z dokładnością do izomorfizmu, tzn. z uwzględnieniem wszystkich pokrewnych pozycji wynikających z przekształceń o charakterze symetrii i obrotów.
Historia problemu
Problem ośmiu hetmanów został po raz pierwszy sformułowany w 1848 roku przez mistrza szachowego nazwiskiem Max Bezzel (1824-1871). Prawidłowa odpowiedź została określona dwa lata później przez Franza Naucka. Również matematyk Carl Friedrich Gauss interesował się tym problemem, jednak nie on jako pierwszy. W roku 1992 wykazano ekwiwalencję pomiędzy problemem ośmiu hetmanów a kwadratami magicznymi.
Sformułowanie analityczne problemu [edytuj]
Niech (i,j) (m,n) będą współrzędnymi dwóch hetmanów
* dwa hetmany stoją na jednej linii wtedy i tylko wtedy gdy i=m lub j=n
* dwa hetmany stoją na jednej diagonali wtedy i tylko wtedy gdy i=m+x i j=n+x
gdzie wartość +x może być ujemna lub dodatnia niezależnie w obu równaniach. Jak można stwierdzić całkowita ilość rozwiązań nie może przekroczyć 8!.
#include <iostream>
#include <cmath>

using namespace std;

const int n=8;

int poz_y[n];
int licznik=1;

bool czy_wolne(int x, int y)
{
int i;
for (i=0;i<x;i++)
{
        if (y==poz_y[i] || abs(x-i)==abs(y-poz_y[i]))
         return false;
}        
return true;
}

void wypisz()
{
int i;
cout << "\t\t\t" << licznik << ")\t";
for (i=0;i<n;i++)
        cout << static_cast<char>('A'+i) << poz_y[i]+1 << " ";
cout << endl;
}        

void hetman(int kol=0)
{
int i;
for (i=0; i<n; i++)
{
        if (czy_wolne(kol,i))
        {
         poz_y[kol]=i;
         if (kol==n-1)
         {
         wypisz();
         licznik++;
         return ;
         }
         hetman(kol+1);        
        }
}}

int main ()
{
cout << "\n\n\t\t\t\tPROBLEM OSMIU HETMANOW" ;
cout<<"\n\n\t\tszachowa konwencja zapisu ustawienia hetmanow\n\n\n";
hetman();
cout << "\nIstnieje " << licznik-1 << " mozliwosci ustawienia 8 hetmanow na szachownict tak, aby sie \nwzajemnie nie atakowaly."
         << " Wszystie te kombinacje zostaly przedstawione powyzej.\n\n";

cin.ignore();
getchar();
return 0;
}     
Pobierz plik tekstowy
Administrator WJL
PHP&SQL coded by NOVA-IT