: index | programowanie | webmastering | algorytmika | download | projekty | słownik | grafika | flash | linki :

a l g o r y t m y > inne >

P R O B L E M   O Ś M I U   H E T M A N Ó W

 

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 29 30

 
       

Problem 8 hetmanów związany jest, a jakże, z szachami. Królowa, zwana hetmanem, ustawiona na szachownicy atakuje wszystkie pola w poziomie, w pionie i po skosie - ustawiona w polu [1, 1] atakuje łącznie 21 pól szachownicy.

Jeśli w jednej kolumnie ustawimy dwa hetmany, to siłą rzeczy muszą się wzajemnie atakować. Wniosek stąd płynący jest taki, że na standardowej szachownicy o wymiarach 8 x 8 nie można ustawić więcej niż 8 hetmanów. Odpowiedź na pytanie czy można ustawić 8 jest pozytywna i znana od dawna, zwłaszcza że jest to zadanie wykonalne metodą prób i błędów, można popróbować, powinno zająć kilka (lub kilkanaście) minut.
Ale wcale nie jest to odpowiedź oczywista, bo na przykład na szachownicy o wymiarach 3 x 3 nie ustawimy w żaden sposób nie atakujących się 3 hetmanów, na szachownicy 4 x 4 można ustawić 4 nieatakujące się hetmany na dwa sposoby.

Hetmany ustawione na polach [x, y] i [x', y'] atakują się gdy:

  • stoją w tym samym wierszu, tzn. gdy x = x',

  • stoją w tej samej kolumnie, tzn. gdy y = y',

  • stoją w tej samej linii po skosie, tzn. gdy |x-x'| = |y-y'|

W przełożeniu na Pascal funkcję o wartościach logicznych zwracająca prawdę, gdy dwa hetmany atakują się może być zdefiniowana tak:

Function AtakujaSie(x1, y1, x2, y2 : ShortInt) : Boolean;
Begin
  If (x1=x2) Or (y1=y2) Or (Abs(x1-x2)=Abs(y1-y2)) Then AtakujaSie:=True
  Else AtakujaSie:=False;
End;

Do zapamiętania ustawienia 8 hetmanów wystaczy zwykła tablica 8 bajtów - tutaj ShortInt, tylko dla zgodności z powyższą funkcją:

Type
  Rozmiar     = 8;
  Szachownica = Array[1..Rozmiar] Of ShortInt;

Poszczególne komórki tej tablicy są odpowiednikami wierszy szachownicy - odpowiednikiem kolumny będzie liczba zapisana w odpowiedniej komórce - jeśli na szachownicy ustawimy hetmana na polu [x, y], to do tablicy tej w komórkę S[x] wpiszemy wartość kolumny, czyli y:

(x, y) = (x, S[x])

Algorytm ustawiający hetmany na szachownicy jest przykładem rekurencji z powrotami. Ustawiamy kolejno hetmana w wierszu pierwszym, drugim, itd. aż do ósmego, zawsze wybierając pierwszą wolną komórkę w wierszu - wolną, to znaczy taką, aby ustawiony na niej hetman nie atakował się z żadnym z ustawionych już hetmanów w wierszach o niższych numerach.
Funkcja sprawdzająca czy komórka [x, y] jest wolna:

Function Wolna(x, y : ShortInt) : Boolean;
Var
  wiersz : ShortInt;
Begin
  Wolna:=False;
  For wiersz:=1 To x-1 Do
    If AtakujaSie(wiersz, S[wiersz], x, y) Then Exit;
  Wolna:=True;
End;

Do przykładowego programu, który wypisze wszystkie możliwe ustawienia i poda ich ilość potrzebna jest jeszcze procedura wypisująca poprawne ustawienie:

Var
  S     : Szachownica;
  Ilosc : LongInt;

Procedure Wypisz;
Var
  wiersz, kolumna : ShortInt;
Begin
  For wiersz:=1 To Rozmiar Do
    Begin
      For kolumna:=1 To Rozmiar Do
        If kolumna=S[wiersz] Then Write('x':2)
        Else Write('*':2);
      WriteLn;
    End;
  WriteLn;
  Ilosc:=Ilosc+1;
  WriteLn('Ustawienie numer = ', Ilosc);
End;

Argumentem rekurencyjnej procedury ustawiającej hetmany na szachownicy jest numer wiersza, w którym należy ustawić kolejnego hetmana - jeżeli nie jest to wiersz ostatni, to ustawieniu należy ustawić kolejnego w wierszu wiersz+1, jeśli ustawiony został poprawnie hetman w ostatnim wierszu, to wypisujemy znalezione ustawienie.
Na szachownicy o wymiarach 10 x 10 można ustawić 10 hetmanów na 724 sposoby.

Procedure Ustaw(wiersz : ShortInt);
Var
  kolumna : ShortInt;
Begin
  For kolumna:=1 To Rozmiar Do
    If Wolna(wiersz, kolumna) Then
      Begin
        S[wiersz]:=kolumna;
        If wiersz<Rozmiar Then Ustaw(wiersz+1)
        Else Wypisz;
      End;
End;

Begin
  Ilosc:=0;
  Ustaw(1);
  ReadLn;
End.

 * * * * * * * * * x
 * * * * * * * x * *
 * * * * x * * * * *
 * x * * * * * * * *
 * * * x * * * * * *
 x * * * * * * * * *
 * * * * * * x * * *
 * * * * * * * * x *
 * * * * * x * * * *
 * * x * * * * * * *
Ustawienie numer = 723

 * * * * * * * * * x
 * * * * * * * x * *
 * * * * x * * * * *
 * * x * * * * * * *
 x * * * * * * * * *
 * * * * * x * * * *
 * x * * * * * * * *
 * * * * * * * * x *
 * * * * * * x * * *
 * * * x * * * * * *
Ustawienie numer = 724