Strona 1 z 1

KOŃ i n d i v i d u u m

: 5 wrz 2013, o 22:53
autor: mol_ksiazkowy
Teoria grafów jest od Eulera*.
:arrow:

Historycznie - istnieje już od IX w.*
;matematycznie jest od ok. XVIII w. B. Taylor, a jego rozwiązanie: A. de Moivre oraz R. de Montmort. L. Euler też się tym zajmował: list do C. Goldbacha (1757 r).
:arrow: A także: M. Kraitchik w Mathematical Recreations, H. E. Dudeney Amusements in Mathematics, a także inni:
Allen J. Schwenk. W. Ball i H. S. Coxeter.
* tj. w Kavyalankarze Rudraty (IX w.) gdzie akcenty słów odpowiadają temu jak przemieszcza się konik po planszy \(\displaystyle{ 4 \times 8}\).

Problem konika lub (ścieżki konia): konik ma zmieniać pola całej szachownicy (i na każdym z nich będąc dokładnie raz; a jeśli uda mu się wrócić na pole z którego rozpoczął, to taką ścieżkę nazywa się zamkniętą) - rozważany jest też ten problem na planszach innych niż \(\displaystyle{ 8 \times 8}\) (i także na nieskończonych! a nawet przestrzennych…).
Ścieżkę konia na szachownicy \(\displaystyle{ n \times n}\) nazywa się też konikówką rzędu \(\displaystyle{ n}\).
Istnieje wiele wyników opisujących takie konikówki: kiedy istnieją i jak ich szukać. Jednak mimo tego iż problem jest tak stary, niektóre kwestie z nim związane wciąż nie do końca są wyjaśnione….Jest to jedno z klasycznych zadań tzw. matematyki rekreacyjnej.
Pierwsze algorytmy wyznaczania ścieżki konia pochodzą od H.C. Warnsdorffa (ok. 1823 r.) Spośród różnych metod, oprócz Eulera są np. Moona, (ramowa tj. polegająca na wydzieleniu z całej szachownicy środkowego, mniejszego kwadratu i „ramy”); A. Moivre’a (ramowa) oraz P. Rogeta (podział szachownicy na ćwiartki).
t' Zeepard
: tak nazywała się maszyna skonstruowana przez konstruktora- wynalazcę D'Hooghe'a rozwiązująca zagadnienie obiegu konika (lata 60 -te XX w.).
Ukryta treść:    
Twierdzenie Schwenka
Dla szachownicy \(\displaystyle{ m \times n}\) (gdzie \(\displaystyle{ m \leq n}\)) istnieje zamknięta ścieżka konika, chyba że spełniony jest jeden z warunków:
zarówno \(\displaystyle{ m}\) jak i \(\displaystyle{ n}\) są nieparzyste
\(\displaystyle{ m=1}\) lub \(\displaystyle{ m=2}\) lub \(\displaystyle{ m=4}\), zaś \(\displaystyle{ n>1}\)
\(\displaystyle{ m=3}\) oraz \(\displaystyle{ n=4}\) lub \(\displaystyle{ n=6}\) lub \(\displaystyle{ n=8.}\)

Przykład: Niezamknięta ścieżka konika z h8 do f3 (Abraham de Moivre)
1.jpg
1.jpg (20.19 KiB) Przejrzano 1567 razy
Żadna ścieżka nie może być symetryczna względem przekątnej. Na prostokącie, którego oba boki mają parzystą ilość pól, żadna ścieżka nie jest symetryczna względem osi głównej. Kiedy bok pionowy składa się z nieparzystej ilości pól, ścieżka z symetrią względem osi poziomej nadal jest niemożliwa. Symetryczne ścieżki jednak istnieją na niektórych planszach.
Ukryta treść:    
Przykład (Konikówka Carla Jänischa *)
Konikówka ta rozpoczyna się z pola d4 (któremu przypisuje się: \(\displaystyle{ 1}\)), zaś kończy się na polu c6 (któremu przypisuje się: \(\displaystyle{ 64}\)). Sumy we wszystkich wierszach i kolumnach są równe \(\displaystyle{ 260}\) ale sumy na przekątnych są już inne (tj. \(\displaystyle{ 192}\) i \(\displaystyle{ 328}\)). Symetrię środkową tej konikówki wyraża fakt, iż każde dwa pola symetryczne względem środka szachownicy (np. b3 i g6) będą mieć przypisane takie elementy, których różnica wyniesie \(\displaystyle{ 32}\).
Konikówka ta jest też ukazana wraz z opisem w Kalejdoskopie H. Steinhausa.
* autor Découvertes sur le cavalier z 1837 r. ;

Ścieżki z ograniczeniami
Nieco innym typem ścieżek są te, w których łamana jej odpowiadająca nie zawiera samoprzecięć (ang. uncrossed knight's path ). Jest to tzw. łamana zwyczajna. W takiej ścieżce konik nie przejdzie przez wszystkie pola (a więc nie jest to konikówka), ale musi ich zaliczyć możliwie jak najwięcej. Znane są takie drogi jedynie dla małych wartości \(\displaystyle{ n}\)
Ukryta treść:    
Ścieżki ustrukturalizowane
Jeśli ścieżka "otacza wszystkie rogi", tj. gdy zawiera osiem „narożnych odcinków”, to jest ustrukturalizowana: np. konikówka de’ Moivre’a nie jest ustrukturalizowaną, gdyż nie zawiera odcinka z g8 do h6. Konikówka Eulera też nie jest ustrukturalizowana, lecz konikówka Jänischa już tak.

Przykład (ścieżka ustrukturalizowana)

Najmniejsza wartością \(\displaystyle{ n}\), dla której istnieje konikówka na planszy \(\displaystyle{ 3 \times n}\) jest \(\displaystyle{ n=10}\), przy czym ilość konikówek ostro rośnie wraz ze zwiększeniem rozmiarów szachownicy (gdy \(\displaystyle{ n=10}\) jest ich \(\displaystyle{ 16}\), gdy \(\displaystyle{ n= 11}\) to jest ich już \(\displaystyle{ n= 176}\) itd).
Zaś dla planszy \(\displaystyle{ 5 \times 6}\) jest \(\displaystyle{ 8}\) rozwiązań ale dla planszy \(\displaystyle{ 5 \times 8}\) jest już ich \(\displaystyle{ 44 \ 202}\) itd.

Argument parzystości (ang. parity proof) Nie istnieje zamknięta ścieżka konika na planszy \(\displaystyle{ n \times m}\), jeśli \(\displaystyle{ n}\) i \(\displaystyle{ m}\) są nieparzyste.
Na szachownicy \(\displaystyle{ 4 \times 4}\) problem konika także nie ma rozwiązania (na planszy \(\displaystyle{ 3 \times 3}\) też nie ma, bo środek jest nieosiągalny…).
Problem dualny: Jeśli dla danej planszy \(\displaystyle{ n \times m}\) nie istnieje konikówka, to jaka jest największa ilość pól które może koń obejść...?

Konikówki można zilustrować graficznie na dwa typowe sposoby, tj. rysując całą ścieżkę, co jest wizualnie atrakcyjne, ale przy dużych rozmiarach szachownicy mniej przejrzyste… bądź też użyć zapisu macierzowego, jak tu:
\(\displaystyle{ M_1 =\left[\begin{array}{ccccc}25&6&17&12&23\\16&11&24&7&2\\5&18&1&22&13\\10&15&20&3&8\\19&4&9&14&21\end{array}\right]}\) \(\displaystyle{ M_2 =\left[\begin{array}{cccccc}1&26&13&24&3&28\\12&23&2&27&14&17\\33&36&25&16&29&4\\22&11&34&7&18&15\\35&32&9&20&5&30\\10&21&6&31&8&19\end{array}\right]}\)

\(\displaystyle{ M_1}\) i \(\displaystyle{ M_2}\) (tj. konikówki rzędu \(\displaystyle{ 5}\) i \(\displaystyle{ 6}\)).
Jest też trzecia możliwość tj. przez podanie listy kolejnych pól ścieżki np. dla szachownicy \(\displaystyle{ 5 \times 6}\):
a1, b3, a5, c4, b2, d1, f2, e4, c5, a4, c3, b5, a3, b1, d2, f1, e3, f5, d4, e2, c1, a2, b4, d5, f4, d3, e5, f3, e1, c2.

Przykład (Euler, 1759 r.)

:arrow: Na stronie wiki można też znaleźć więcej użytecznych informacji o komputerowych technikach konstrukcji różnego typu konikówek (m. in o metodzie Warnsdorffa) oraz Eulerze, są ukazane m.in. konikówki rzędu \(\displaystyle{ 5}\) oraz \(\displaystyle{ 8}\) (Mechaniczny Turek) z animacją jak i nawet rzędu \(\displaystyle{ 24}\) znalezioną przy użyciu sieci neuronowych, etc.
I. Stewart (Krowy w labiryncie) podaje znacznie szersze omówienie tego tematu, w tym ideę dowodu twierdzenia Golomba oraz rezultaty i hipotezy R. Ulmera, który badał konikówki głównie pod kątem ich symetrii. Eugene Gik w Szachmaty skupia się na różnych właściwościach konika szachowego - łącząc umiejętnie matematykę z szachami. W An efficient algorithm Iana Parberry zawarte są niektóre własności (także i motywy symetrii itp.) i przykłady ścieżek ustrukturalizowanych. Dan Thomasson daje przykłady w formie animacji ścieżek konika na różnych szachownicach.


Twierdzenie
Dla każdego \(\displaystyle{ n \geq 6}\) parzystego istnieje ustrukturalizowana ścieżka konika na szachownicy \(\displaystyle{ n \times n}\) oraz \(\displaystyle{ n \times (n+2)}\).

Twierdzenie
Dla każdej szachownicy kwadratowej o boku \(\displaystyle{ 4n+1}\) istnieje konikówka o początku w środku szachownicy i końcu w prawym górnym rogu.

Twierdzenie
Z kwadratu \(\displaystyle{ n \times n}\), gdzie \(\displaystyle{ n > 4}\), wycięto środkowy kwadrat \(\displaystyle{ (n - 2) \times (n - 2)}\). Pozostałą figurę można obejść konikiem szachowym (bedąc na każdym polu dokładnie jeden raz) wtedy i tylko wtedy, gdy \(\displaystyle{ n \equiv 1 \pmod{4}.}\)

Twierdzenie
Dla szachownicy \(\displaystyle{ n \times nm}\) gdzie \(\displaystyle{ n \geq 5}\) i \(\displaystyle{ m \geq 5}\) istnieje otwarta ścieżka konika.

Twierdzenie Golomba- Polyi
Nie istnieje ścieżka konika (ani otwarta ani zamknięta) na szachownicy \(\displaystyle{ 4 \times n}\).

Źródła:
Ukryta treść:    
* link do cytatu początkowego:
Ukryta treść:    
Przykład: Niezamknięta ścieżka z a8 do c1 (Dan Thomasson)

Przykład: animacja /źródło: wiki/
220px-Knight's_tour_anim_2.gif
220px-Knight's_tour_anim_2.gif (83.17 KiB) Przejrzano 1567 razy
:arrow: błedy + dalsze info --> pw.

Re: KOŃ i n d i v i d u u m

: 26 maja 2017, o 18:39
autor: mol_ksiazkowy
kody źródłowe - autor mariuszm

Algorytm z powrotami , dla planszy \(\displaystyle{ 8 \times 8}\) z punktu startowego \(\displaystyle{ (3,7)}\) daje ścieżkę zamkniętą
Pascal (Free Pascal):    
C (gcc):    
Java 1.7:    
Python 2.5: