Problem 8 hetmanów
Z Wikipedii
Spis treści |
[edytuj] Problem (Został sformułowany przez J.C. Gaussa w 1850)
Hetman jest figurą szachową, która bije figury znajdujące się w tej samej kolumnie, wierszu lub skosie co on sam. Jak rozstawić 8 hetmanów na tradycyjnej szachownicy (8x8) tak aby wzajemnie się nie “biły”?
[edytuj] Analiza
Ponieważ dwa hetmany nie mogą stać na jednaj kolumnie, ustawienie hetmanów możemy opisać za pomocą ciągu 8 liczb (a1,...,a8) , gdzie i-ty hetman stoi na i-tej kolumnie w ai -tym wierszu. Dany ciąg będzie stanowić rozwiązanie gdy spełnione będą warunki: ai < > aj dla i < > j (1) i ai − aj < > + − (i − j) (2) Na podstawie samego warunku (1) wiemy że szukany ciąg będzie permutacją zbioru liczby naturalnych od 1 do 8.
[edytuj] Rozwiązanie 1
Będziemy więc generować kolejne permutacje do momentu kiedy któraś z nich spełni warunek (2).
[edytuj] Rozwiązanie 2
Pierwszego hetmana umieszczamy w pierwszym wierszu a1 = 1 . Wyklucza nam to możliwość umieszczenia hetmana drugiego w 1 lub 2 wierszu więc a2 = 3. Następnego hetmana ustawia się w kolejnym wierszu na pozycji, która nie jest bita przez wcześniej ustawione hetmany. W ten sposób rozwiązania szukamy wśród 6! permutacji.
[edytuj] Bibliografia
Zawadzki Marek Wykład ze wstępu do informatyki.
