Algorytmy z powrotami

Algorytmy z powrotami przedstawiane są najczęściej na przykładzie problemu n-królowych lub 8. hetmanów, jak kto woli. Z grubsza chodzi o to, żeby tak poustawiać królowe na szachownicy, aby sie wzajemnie nie szachowały. Dla nienzających zasad szachów:
Królowa bije wszystkie figury bedące z nią w jednym wierszy, kolumnie, badź na skos.Tak bije królowaTak trzeba ustawić
Spróbujmy rozwiązać problem dla szachownicy 4x4. Według algorytmu z powrotami robimy to w ten sposób:

1. stawiamy pierwszą królową w pierwszym rzędzie,
2. stawiamy drugą królową w drugim rzędzie tak, żeby się nie szachowały,
3. stawiamy trzecią królową w trzecim rzędzie tak, żeby się nie szachowała z pozostałymi,
4. to samo dla czwartej.

Byłoby to proste gdyby za każdym razem znajdowało się takie miejsce. Załóżmy sytuację w której nie mamy miejsca na postawienie trzeciej królowej (brak nieszachowanego pola w trzecim rzędzie). Wtedy oto algorytm z powrotami mówi nam, ze musimy wrócić, a to znaczy, że cofamy się do drugiego rzędu, przestawiamy drugą królową i próbujemy teraz ustawić trzecią. Jeżeli ciągle nie znajdujemy dla niej miejsca, znowu przestawiamy drugą, jeżeli skończyły się wszystkie miejsca dla drugiej, przestawiamy pierwszą. I to tyle o algorytmach z powrotami, żeby ideę zrozumieć. Teraz trochę teorii.

Algorytmy z powrotami są wykorzystywane do rozwiązywania problemów, w których z określonego zbioru jest wybierana sekwencja obiektów tak, aby spełniała ona określone kryteria.
Dla n królowych na szachownicy o wymiarach n x n sekwencją jest n pozycji, na których są umieszczone królowe. Zbiorem dla każdego wyboru jest n² możliwych pól na szachownicy. Kryterium jest takie, że królowe nie mogą się wzajemnie szachować.

Dla 4 królowych na szachownicy o wymiarach 4 x 4, sekwencją są 4 pozycje (I, II, III i IV kolumna w wierszu), na których są umieszczone królowe. Zbiorem dla każdego wyboru jest 4² = 16 możliwych pól na szachownicy. Kryterium jest takie, że królowe nie mogą się wzajemnie szachować.
Postępując według algorytmu z powrotami robimy sobie takie oto drzewo przestrzeni stanów. Fragment takiego drzewa
Jak to czytamy? Start to początek rozwiązywania naszego problemu, następnie wybieramy (korzystamy z wyszukiwania w głąb grafu, dla porządku jedziemy od lewej) gdzie stawiamy pierwszą królową, na polu (1,1), (1,2), (1,3) lub (1,4). Powiedzmy, że stawiamy na (1,1), przechodzimy więc do tego węzła i dostajemy kolejne możliwości; (2,1), (2,2), (2,3) i (2,4). Pierwsza królowa na polu (1,1), złe ustawienie drugiej królowej
Od razu widać, że pola (2,1) i (2,2) sa szachowane przez nasza królową postawioną na (1,1), zatem nazwijmy te węzły węzłami nieobiecującymi i zignorujmy. Pozostały węzły (2,3) oraz (2,4), to zdecydowanie są dla nas węzły obiecujące. Zgodnie z naszym sposobem wybierania kolejnych węzłów przechodzimy do (2,3). Ale co to? W takiej konfiguracji, każde pole w trzecim rzędzie jest szachowane. Nie pozostaje nam nic jak uznać te węzły za nieobiecujące i spróbowac znowu przestawić królową w polu drugim.
Kontynuując prace tym tokiem skrócimy nasze drzewo do takiej formy:
Elegancko widać jak rozstawić królowe, aby się nie szachowały :) Kolejne kroki algorytmu z powrotami

void sprawdz_wezel(node v) 
{ 
  node u; 
 
  if(obiecujacy(v)) 
    if(istnieje rozwiązanie dla v) 
      drukuj rozwiązanie; 
    else 
      for(każdy węzeł pochodny u węzła v) 
       sprawdz_wezel(u); 
} 

Algorytm z powrotami jest identyczny jak przeszukiwanie w głąb, poza tym, że węzły pochodne są odwiedzane tylko w przypadku, gdy węzeł macierzysty jest obiecujący i nie znaleziono w nim rozwiązania.

Algorytm z powrotami jest algorytmem, w którym po zorientowaniu się, że węzeł prowadzi do ślepego zaułka, wracamy do węzła nadrzędnego i kontynuujemy wyszukiwanie od następnego węzła.
Algorytm z powrotami polega na wykonywaniu przeszukiwania w głąb drzewa przestrzeni stanów, aby sprawdzić czy węzeł jest obiecujący, czy nie. Jeżeli węzeł nie jest obiecujący, wracamy do węzła nadrzędnego.
Algorytm z powrotami sprawdza 27 węzłów w celu odszukania rozwiązania, bez zastosowania tego algorytmu trzeba sprawdzić 155 wezłów w celu odszukania tego samego rozwiązania.
Nieefektywność w ogólnym algorytmie z powrotami (procedura sprawdz_wezel) wynika z faktu, że sprawdzamy czy węzeł jest obiecujący, po przekazaniu go do procedury. Rekordy aktywacji wezłów nieobiecujących są niepotrzebnie odkładane na stos rekordów aktywacji.