Wojskowa Akademia Techniczna

Treść zadania - zaprojektować i zaimplementować algorytm heurystyczny (najpierw najlepszy) ustawiający na szachownicy n polowej n hetmanów tak, aby nie atakowały się wzajemnie. W rozwiązaniu należy zaproponować modyfikację heurystycznej funkcji oceny wierzchołków zaproponowanej na wykładzie.

Szachownica (wg. WikiSłownik) - plansza do gry w szachy lub warcaby, składająca się z kwadratowych, dwukolorowych pól umieszczonych w taki sposób, że każdy kwadrat styka się z kwadratem o innym kolorze.

Hetman (wg. WikiPedia.pl) - najsilniejsza figura w szachach. Hetman nazywany jest również damą, królową lub królówką. (...) Hetman może poruszać się w dowolnym kierunku (poziomo, pionowo oraz na ukos) o dowolną liczbę wolnych pól (...)

Heuristic (z. WikiPedia) - "...For shortest path problems, the term has a different meaning. Here, a heuristic is a function, h(n) defined on the nodes of a search tree, which serves as an estimate of the cost of the cheapest path from that node to the goal node. Heuristics are used by informed search algorithms such as Greedy best-first search and A* to choose the best node to explore. Greedy best-first search will choose the node that has the lowest value for the heuristic function. A* search will expand nodes that have the lowest value for g(n) + h(n), where g(n) is the (exact) cost of the path from the initial state to the current node. If h(n) is admissible-that is, if h(n) never overestimates the costs of reaching the goal-, then A* will always find an optimal solution..."

Program liczy dla każdego położenia hetmanów na szachownicy wartość funkcji oceny i do położenia z najwyższą wartością dostawia kolejną kolumnę hetmanów, wylicza dla nich wartość funkcji, wybiera położenie z najwyższą wartością, dostawia kolejną kolumnę, itp. W teorii funkcja powinna prowadzić do celu najlepszą drogą, w praktyce dla dużych wielkości szachownicy przyjęte funkcje wpadają w "ślepe uliczki" i należy włączyć cofanie się (wybrać funkcję oceny z cofaniem).

Jedna z przyjętych funkcji oceny = 3000*długość_napisu_z_położeniami_hetmanów + suma_dla_wszystkich_możliwych_lokalizacji_nowych_hetmanów (współrzędna_x*wielkość + moduł(wielkość_szachownicy/2 - współrzędna_y)) + suma_dla_wszystkich_położeń_hetmanów (współrzędna_x*200 + moduł(wielkość_szachownicy/3 - współrzędna_y))