Czy kiedykolwiek grałeś w szachy? Jeśli tak, to wiesz już, że królowa jest najważniejszą figurą i że może poruszać się o dowolną liczbę pól w pionie, poziomie lub po przekątnej. Jeśli nie, to nie martw się: dziś dowiemy się tylko, jak ustawić 8 królowych na szachownicy tak, aby żadna z nich nie mogła przejść na kwadrat zajmowany przez inną królową. W żargonie szachowym mówimy, że królowe nie będą mogły się nawzajem atakować. Jak to zrobić? Używamy backtrackingu.
Algorytm backtrackingowy znajduje rozwiązanie problemów, w których muszą być spełnione pewne ograniczenia. Testuje on wszystkie możliwe rozwiązania, aż znajdzie to właściwe. Wypróbujmy przykład z czterema królowymi i małą planszą. Zaczniemy od umieszczenia pierwszej królowej:
The second step is to place the second queen in a safe position, and then the third one:
At this point, there is no safe square on which we can place the last queen. So, we will change the position of the previous one. This is backtracking!
As you can see, there is no other square to safely place the third queen, different than the one we tried. Hence, this will require multiple backtracks. We will have to go back again and change the position of the second queen we placed.
We will have to perform multiple backtracks again to place all queens correctly and finally obtain a solution:
If you want to learn more how multiple backtracking steps inevitably lead you to a solution, check out Computer Science Distilled. Pokaże ci również wiele innych strategii obliczeniowych, które pomogą ci rozwiązać interesujące problemy!
Teraz, gdy już wiesz, jak działa backtracking, możemy rozwiązać pełnowymiarowy problem 8 królowych. Poniżej znajduje się szachownica, z którą możesz zagrać, aby poćwiczyć swoje umiejętności i znaleźć rozwiązanie. Zacznij od umieszczenia pierwszej królowej, klikając na lewy górny kwadrat szachownicy. Zobaczysz, że umieszczona przez Ciebie królowa znajdzie się na liście „Aktualne królowe”.
Obecne królowe
Możesz teraz umieścić kolejną królową w pozycji, która uniemożliwi im atakowanie się nawzajem. Nasza pierwsza królowa jest na a8, druga może być umieszczona na przykład na c7. Tak długo należy umieszczać królowe, aż na szachownicy nie pozostanie żaden bezpieczny kwadrat. W tym momencie należy cofnąć się, klikając „undo”. Usunie to ostatnią umieszczoną królową i pozwoli Ci wybrać inne pole, na którym ją umieścisz. Możesz również usunąć królową z planszy, klikając bezpośrednio na nią.
Grając w interaktywną grę, możesz zacząć wyczuwać, jak się cofać. Jako ludzie, może nam być trudno śledzić wszystkie poprzednie położenia królowych. Tutaj z pomocą przychodzi programowanie! Poniżej znajduje się animacja wygenerowana przez program demonstrujący swoje bezbłędne umiejętności backtrackingu:
Pseudokod:
- Zacznij od umieszczenia pierwszej królowej na lewym górnym kwadracie szachownicy.
- Jeśli umieściliśmy już 8 królowych, to skończyliśmy. W przeciwnym razie, czy możliwe jest umieszczenie kolejnej królowej w bezpiecznej pozycji?
- Jeśli tak, to oznacz to jako część rozwiązania i wróć do punktu 2.
- Jeśli nie, to zmień pozycję poprzedniej królowej (backtracking) i wróć do punktu 2.
.