Problem ośmiu hetmanów — notacja

Problem ośmiu hetmanów polega na ustawieniu ośmiu figur szachowych znanych jako hetman lub królowa na klasycznej szachownicy o wymiarach 8x8 w taki sposób, aby nie atakowały się wzajemnie. Hetman to figura, która może poruszać się wzdłuż kolumn, wzdłuż wierszy, a także po skosie, zbijając przy tym inne figury, które stoją na jej drodze. Chcąc ustawić ośmiu hetmanów tak, by nie zbijały się nawzajem, nie można dopuścić do sytuacji, w której dwa z nich znajdą się w jednym wierszu lub w jednej kolumnie. Warunkiem koniecznymwarunek koniecznyWarunkiem koniecznym (lecz nie wystarczającymwarunek wystarczającywystarczającym) jest więc to, aby każda z ośmiu figur była ustawiona w innej kolumnie – w przeciwnym wypadku przynajmniej dwie figury atakowałyby się wzajemnie. Notacja stosowana do przedstawienia rozwiązania problemu ośmiu hetmanów składa się z ośmiu liczb, z których każda i-ta liczba oznacza wiersz, w którym znajduje się hetman z i-tej kolumny. Pierwsza liczba stanowi zatem numer wiersza, w którym znajduje się hetman z pierwszej kolumny; druga — numer wiersza, w którym znajduje się hetman z drugiej kolumny, itd.

Implementacja w języku C++

Na początek stwórzmy globalną tablicę typu całkowitego o długości 9. Będzie ona zawierała numery wierszy hetmanów na odpowiednich pozycjach. Komórka o indeksie 0 nie będzie używana.

#include <iostream>
using namespace std;

int h[9];

Teraz zdefiniujmy funkcję o nazwie hetman, przyjmującą parametr będący numerem wiersza, w którym chcemy postawić hetmana. Wewnątrz funkcji stworzymy pętlę, która będzie iterować po wszystkich kolumnach i sprawdzać, czy któraś z nich jest wolna.

#include <iostream>
using namespace std;

int h[9];

void hetman(int wiersz) {
	for (int i = 1; i <= 8; i++) {
		if (h[i] == 0) {
		}
	}
}

Jeżeli istnieje wolna kolumna, musimy sprawdzić, czy pole w tym wierszu i w tej kolumnie nie jest atakowane przez innego hetmana po skosie. Tworzymy pętlę, w której będziemy sprawdzać, czy istnieje hetman w innej kolumnie – a jeśli tak, to czy jego zakres ruchu nie zagraża pozycji naszego nowego hetmana. W tym celu używamy wzoru:

gdzie $\left(a,b\right)$ to współrzędne pierwszego hetmana, zaś $\left(c,d\right)$ to współrzędne drugiego hetmana.

#include <iostream>
using namespace std;

int h[9];

void hetman(int wiersz) {
	for (int i = 1; i <= 8; i++) {
		if (h[i] == 0) {
			int czyAtakowane = 0;
            
			for (int j = 1; j <= 8; j++) {
				if (h[j] && (abs(i - j) == abs(wiersz - h[j]))) {
					czyAtakowane = 1;
				}
			}
		}
	}
}

Jeżeli pole jest atakowane, ustawiamy odpowiednią zmienną na 1. Następnie, jeśli mamy pewność, że pole nie jest zagrożone, umieszczamy hetmana na odpowiedniej pozycji, zapisując numer wiersza w komórce tablicy o indeksie równym numerowi kolumny.

#include <iostream>
using namespace std;

int h[9];

void hetman(int wiersz) {
	for (int i = 1; i <= 8; i++) {
		if (h[i] == 0) {
			int czyAtakowane = 0;
            
			for (int j = 1; j <= 8; j++) {
				if (h[j] && (abs(i - j) == abs(wiersz - h[j]))) {
					czyAtakowane = 1;
				}
			}
                
			if (!czyAtakowane) {
				h[i] = wiersz;
			}
		}
	}
}

Jeśli nie ustawiliśmy jeszcze wszystkich hetmanów, przechodzimy do kolejnego wiersza, wywołując rekurencyjnierekurencjarekurencyjnie funkcję hetman(wiersz + 1). W momencie zaś, gdy wszystkie osiem wierszy zostanie wypełnione, wypisujemy całe rozwiązanie na standardowe wyjście.

#include <iostream>
using namespace std;

int h[9];

void hetman(int wiersz) {
	for (int i = 1; i <= 8; i++) {
		if (h[i] == 0) {
			int czyAtakowane = 0;
            
			for (int j = 1; j <= 8; j++) {
				if (h[j] && (abs(i - j) == abs(wiersz - h[j]))) {
					czyAtakowane = 1;
				}
			}
                
			if (!czyAtakowane) {
				h[i] = wiersz;
                
				if (wiersz < 8) {
					hetman(wiersz + 1);
				} else {
					for (int i = 1; i <= 8; i++) {
						cout << h[i];
					}
                    
					cout << endl;
				}
			}
		}
	}
}

Jeżeli jednak w danym wierszu nie znajdziemy pola, którego nie atakuje inny hetman, musimy powrócić do poprzedniego wiersza i dla kolumny, w której się znajdował, ustawić wartość 0. Dzięki wcześniejszemu zastosowaniu pętli zostanie wyszukane dla niego inne wolne pole. Jeżeli tu także nie znajdziemy innego wolnego pola, nastąpi ponowne cofnięcie itd. Algorytm taki nazywamy algorytmem z nawrotamialgorytm z nawrotamialgorytmem z nawrotami.

#include <iostream>
using namespace std;

int h[9];

void hetman(int wiersz) {
	for (int i = 1; i <= 8; i++) {
		if (h[i] == 0) {
			int czyAtakowane = 0;
            
			for (int j = 1; j <= 8; j++) {
				if (h[j] && (abs(i - j) == abs(wiersz - h[j]))) {
					czyAtakowane = 1;
				}
			}
                
			if (!czyAtakowane) {
				h[i] = wiersz;
                
				if (wiersz < 8) {
					hetman(wiersz + 1);
				} else {
					for (int i = 1; i <= 8; i++) {
						cout << h[i];
					}
                    
					cout << endl;
				}
                
				h[i] = 0;
			}
		}
	}
}

Teraz wystarczy w głównej funkcji wypełnić komórki tablicy wartością 0 i wywołać funkcję hetman dla pierwszego wiersza. Oto gotowy kod naszego programu, odnajdujący wszystkie możliwe rozwiązania problemu ośmiu hetmanów w języku C++:

#include <iostream>
using namespace std;

int h[9];

void hetman(int wiersz) {
	for (int i = 1; i <= 8; i++) {
		if (h[i] == 0) {
			int czyAtakowane = 0;
            
			for (int j = 1; j <= 8; j++) {
				if (h[j] && (abs(i - j) == abs(wiersz - h[j]))) {
					czyAtakowane = 1;
				}
			}
                
			if (!czyAtakowane) {
				h[i] = wiersz;
                
				if (wiersz < 8) {
					hetman(wiersz + 1);
				} else {
					for (int i = 1; i <= 8; i++) {
						cout << h[i];
					}
                    
					cout << endl;
				}
                
				h[i] = 0;
			}
		}
	}
}

int main() {
	for (int i = 1; i <= 8; i++) {
		h[i] = 0;
    }
    
	hetman(1);
	return 0;
}

Problem n hetmanów

Problem n hetmanów to termin, którym określamy zastosowanie problemu ośmiu hetmanów dla szachownicy mniejszej lub większej niż standardowa (8x8 pól). W problemie n hetmanów chcemy ustawić n figur na szachownicy o wymiarach nxn w taki sposób, aby nie atakowały się wzajemnie.

Poniższa tabela prezentuje liczbę rozwiązań problemu n hetmanów dla danych wartości n:

Słownik