Strategia zrównoleglania
Głównym kłopotem w rozwiązaniu problemu n-królowych jest złożoność struktury danych, z jaką musi się zmierzyć
algorytm z powrotami. Drzewo przestrzeni stanów rozrasta się bardzo szybko, a równoczesne przetwarzanie wielu
jego gałęzi (szczególnie przy dużych szachownicach) jest zadaniem niezmiernie czasochłonnym. Analizując tę
sytuację dotarto do wniosku, że istnieje dosyć interesujący sposób rozłożenia pracy związanej z przetwarzaniem
drzewa przestrzeni stanów. Pomysł polega na podzieleniu drzewa na niezależne obszary, których przetwarzaniem
zajmowałaby się grupa wątków. Liczba obszarów jest równa liczbie kolumn w analizowanej szachownicy. Jeżeli
obszarów jest więcej niż dostępnych wątków, wtedy jeden wątek przetwarza kolejno kilka obszarów. Dane
przetwarzane w ramach każdego z nich są danymi prywatnymi, jedynie ilość rozwiązań odnotowywana jest w
zmiennej współdzielonej przez wszystkie wątki. Poniższy rysunek przedstawia sposób, w jaki dokonano zrównoleglania
procesu poszukiwania rozwiązań dla szachownicy 4x4 za pomocą 4 wątków.
Zatem wszystkie możliwe kombinacje ustawień królowych rozpoczynające się od królowej w wierszu 1 i kolumnie 1, będą przeliczane przez wątek 1. Z kolei wszystkie rozwiązania wyznaczone przez wątek 2 będą tyczyły się kombinacji ustawień królowych, rozpoczynających się od królowej w wierszu 1 i kolumnie 2 (królowa zielona) itd. Na rys. 2 pokazano, jak może wyglądać przykładowe rozdzielenie pracy między dwoma pierwszymi wątkami w czasie przetwarzania szachownicy 4x4.