Błędne wyświetlenie wyniku programu - problem szachowy

Question

Naskrobałem program mający rozwiązywać problem "N-Hetmanów" na szachownicy NxN. Chcę sprawdzać ilość możliwych unikalnych rozwiązań oraz wyświetlać pierwsze znalezione - w tym celu w funkcji sprawdzającej czy pole jest atakowane próbuję przechwycić pierwsze N pozycji hetmanów zapisując wiersze i kolumny do wektorów i wyświetlić je na końcu programu. Program nie wyświetla prawidłowo wszystkich hetmanów - 5 dobrze, 6 zle i kolejnych już wcale. W czym tkwi problem? Próbowałem modyfikować warunek sprawdzający pole, sprawdzałem poprawność funkcji wyświetlania i nie mam pomysłu.

Answer 1

Czy na pewno zrobiłeś to przez BFS? Na wszelki wypadek sprawdź na przykład tutaj pisałem dużo o zagadkach przeszukujących graf i masz tam pseudoprogram. Do BFS potrzebujesz struktury danych typu "kolejka" i algorytm jest iteracyjny.

http://informatyka-delphi.blogspot.com/2018/05/problem-naczyn-odmierzajacych.html

a tu jest aplikacja internetowa która to zadanie liczy (zagadka odmierzanie objętości)

http://zagadki-informatyczne.pl/

Ogólnie algorytmy przeszukujące graf są szybsze bo są rzędu wielomianowego podczas gdy brute force są rzędu wykładniczego.

Zauważ jednak że rozwiązanie tego zadania przez BFS zamiast brute force, przez proste dostosowanie kodu, niczego nie przyspieszy bo brute force w tym przypadku działa na zasadzie przeszukiwania drzewa a nie zwykłego grafu (każda kolejna badana pozycja jest inna). Nie mamy tego korzystnego przypadku jaki jest w grafach, że napotykamy tą samą pozycję w związku z tym już jej ponownie nie przeszukujemy bo wcześniej ją zaznaczyliśmy.

Prawdopodobnie dałoby się problem przedstawić jako graf (eliminacja powtarzania pozycji) jeśliby sprawdzać dla każdej pozycji czy nie istnieje już wcześniej badana pozycja symetryczna, czyli plansza obrócona o 90 stopni. Wtedy pozornie mielibyśmy trochę przyspieszenie, w tym przypadku niewielkie. Faktycznie jednak algorytm brute force też może mieć to zaimplementowane w taki sam sposób bo z warunków zadania wynika że brute force jest w stanie określić czy pozycja symetryczna już była wcześniej przeszukiwana.

Typowe zadania na algorytmy grafowe opierają się na tym, że nie da się ich zamienić na brute force bo nie wiemy czy dojście do pozycji symetrycznej na pewno musiało być badane wcześniej. Wybrany został zły problem do tego zadania bo to nie jest typowy problem grafowy, gdyż można go z taką samą efektywnością rozwiązać przez brute force.