Konrad Szczęśniak - IT Blog

Witam, tym razem chcę przybliżyć wam jeden z podstawowych problemów szachowych wykorzystywanych w informatyce. Zajmiemy się bowiem problemem skoczka szachowego (skoczek jest jedną z figur szachowych). Jest to typowy przykład zastosowania algorytmu z powrotami, dokładny opis i implementacja rozwiązania znajduje się w dalszej części artykułu.

Opis problemu

Skoczek jest takim typem figury, którego ruch wykonujemy poruszając się dwa pola dalej na poziomej lub pionowej osi, a następnie wykonujemy przesunięcie o jedno pole po tej drugiej osi. Innymi słowy bardziej przystępny będzie typowy obrazek przedstawiający wszystkie możliwe ruchy skoczka.

Wszystkich możliwych ruchów, jak widać na obrazku powyżej, jest 8. Sam opis problemu jest prosty, a mianowicie jak przejść skoczkiem po całej szachownicy pojawiając się na każdym z pól tylko jeden raz?

Rozwiązanie tego problemu jest dosyć proste w zrozumieniu oraz, jeśli znamy ideę działania algorytmów z powrotami(jeśli nie to nie martwcie się, postaram się to wyjaśnić w dalszej części artykułu), w implementacji.

Chodzi w uogólnieniu o sprawdzanie każdej drogi jaką możemy przejść korzystając z dostępnych dla skoczka ruchów. Ideę algorytmów z powrotami możemy porównać do sytuacji gdy jakiś niewdzięcznik wsadził nas do labiryntu, a przy sobie mamy tylko jakąś nitkę i przykładowo młotek z gwoźdźmi. Przez chwilę zastanawiamy się jak efektywnie znaleźć drogę do wyjścia nie biegając w kółko i wchodząc w byle jakie korytarze. Po chwili namysłu przybijamy jeden koniec naszej nitki w miejscu z którego zaczęliśmy i umawiamy się że w przypadku pojawienia się rozdroża (nasz tunel w pewnym miejscu rozbiega się na kilka innych tuneli) wybieramy tunel zgodnie z ruchem wskazówek zegara, a w przypadku natrafienia na ślepy zaułek cofamy się do ostatniego rozdroża i wybieramy kolejną drogę, gdy okaże się że wszystkie rozgałęzienia w danym rozdrożu są ślepymi zaułkami cofamy się jeszcze bardziej i tak cały czas aż uda nam się wyjść i przetrzepać naszego niewdzięcznika. Innymi słowy prosta recepta do celu.

Podobnie postąpimy z problemem skoczka rozdrożem będzie każde pole szachownicy, ale zamiast przechodzić z niego na następne, chodzić będziemy po 8 możliwych dla każdego pola (jak można wywnioskować z tabeli dostępnych ruchów. Cofać będziemy się gdy miejsce na które chcemy przejść będzie poza obszarem szachownicy lub będzie oznaczone jako takie na którym już wcześniej stał nasz skoczek. W końcowym rezultacie znajdziemy się na ostatnim wolnym polu na szachownicy dzięki czemu rozwiążemy zadanie.

Do rozwiązania problemu posłużymy się jedną funkcją, którą będziemy wywoływać rekurencyjnie z różnymi parametrami. Każdy ruch będziemy numerować, po pierwsze aby było można odtworzyć trasę skoczka korzystając z tablicy dwuwymiarowej, w której to wartością danego pola będzie numer ruchu w którym skoczek je odwiedził, a zero jeśli pole nie zostało jeszcze odwiedzone. Po drugie w końcowym momencie algorytmu zdarzy się sytuacja gdy skoczek będzie w ostatnim miejscu i nie będzie już możliwości ruchu bo ukończyliśmy zadanie, w tym wypadku dzięki informacji o numerze ruchu możemy zwrócić informację o poprawnym zakończeniu algorytmu. Sama funkcja będzie zwracać 0 jeśli wszystko przebiegło pomyślnie lub 1 jeśli musimy powrócić z jakiegoś miejsca i szukać dalej. Teraz uwaga, w związku z konfliktem nazw numer ruchu jako numer aktualnego posunięcia skoczka to nrRuchu, a numer ruchu jako numer jednej z 8 możliwości ruchu skoczka to nrPrzesunięcia. Wartości przesunięć będziemy przechowywać w tablicy dwuwymiarowej 8×2 gdzie pierwszy indeks to nr przesunięcia, a drugi do index osi po której się poruszamy (dla lepszej organizacji kodu lepiej zrobić własną strukturę, ale akurat tutaj postanowiłem nie wprowadzać tego). W praktyce wygląda to tak:

ruchy[0][0]=-2; ruchy[0][1]=1;
ruchy[1][0]=-1; ruchy[1][1]=2;
ruchy[2][0]=1; ruchy[2][1]=2;
ruchy[3][0]=2; ruchy[3][1]=1;
ruchy[4][0]=2; ruchy[4][1]=-1;
ruchy[5][0]=1; ruchy[5][1]=-2;
ruchy[6][0]=-1; ruchy[6][1]=-2;
ruchy[7][0]=-2; ruchy[7][1]=-1;

Jak widać do określenia jednego przesunięcia potrzebne są nam dwie wartości, teraz kod naszej głównej funkcji w języku ANSI C:

int Ruch(int nrRuchu, int wspX, int wspY) {
int NastWspX,NastWspY,nrPrzesuniecia=-1;
do {
nrPrzesuniecia++;
NastWspX=wspX+ruchy[nrPrzesuniecia][0];
NastWspY=wspY+ruchy[nrPrzesuniecia][1];
if(NastWspX>=0&&NastWspX=0&&NastWspY
if(tablica[NastWspX][NastWspY]==0) {
tablica[NastWspX][NastWspY]=nrRuchu;
if(nrRuchu
if(Ruch(nrRuchu+1,NastWspX,NastWspY)==0) return 0;
else tablica[NastWspX][NastWspY]=0;
} else return 0;
}
}
} while(nrPrzesuniecia!=8);
return 1;
}

Jak widać argumentami naszej funkcji są aktualna pozycja skoczka oraz numer aktualnego ruchu(uwaga: szerokosc i wysokosc sa zmiennymi globalnymi), obliczamy w prosty sposób wartość kolejnej współrzędnej oraz sprawdzamy czy pole o takich współrzędnych znajduje się w obrębie tablicy oraz czy nie było odwiedzone wcześniej, w przypadku gdy któreś z tych warunków jest niespełniony następuje wyjście z pętli if i wykonanie pętli while kolejny raz, w przypadku gdy każdy z 8 dostępnych dla nas ruchów był niewypałem funkcja zwraca wartość 1 co oznacza że z tego pola nie da się iść dalej w takiej konfiguracji poprzednich ruchów. Jednak w przypadku gdy jakieś pole jest wolne to stawiamy na nie naszego skoczka i sprawdzamy czy to przypadkiem już nie koniec, jeśli to nasz ostatni ruch (a wiemy że liczba ruchów potrzebnych do przejścia szachownicy wynosi szerkosc szachownicy razy jej wysokosc) to zwrazamy wartość 0. Został nam jeszcze do omówienia najgłębszy element, w pętli if wywołujemy funkcję Ruch z nowymi parametrami i czekamy na jej wynik, jeśli zwróci 1 to jak już wiemy oznacza ślepy zaułek, po czym odznaczamy miejsce które oznaczyliśmy wcześniej i wywołujemy kolejny przebieg pętli while, która sprawdzi kolejną możliwość, jeśli jednak dostaniemy 0 to szczęśliwi informacją o powodzeniu naszej misji zwracamy 0 poprzednim wywołaniom funkcji. Tym oto sposobem rozwiązaliśmy problem, a dzięki tablicy z wartościami pól łatwo odtworzymy wybraną trasę.

Na koniec spora uwaga, a właściwie to dwie. Po pierwsze w przykładzie użyliśmy szachownicy o dowolnym rozmiarze, ale nie dla każdej tablicy istnieje rozwiązanie, przykładowo zróbcie na kartce tescik dla tablicy 3×3. Wniosek? Po prostu się nie da. Po drugie uważajcie na rozmiar tablicy oraz punkt startowy, który tutaj też jest dowolny, jako że algorytm jest typowo brutalny (brute-force) w pewnych przypadkach, albo przy dużej szachownicy albo przy niefortunnym wybraniu punktu startowego, może liczyć się baaardzo długo albo nawet i „wiecznie” mimo waszych nowiusieńkich CoreQuad.

Mam nadzieję że na tym przykładzie zrozumieliście ideę algorytmów z powrotami, w razie jakichś pytań proszę słać je na mail lub lepiej zostawić tutaj w komentarzu. To by było na tyle…