Księżna
W komentarzu do poprzedniego wpisu Witman, pisząc program, jako pierwszy na świecie (?) rozprawił się z problemem:
Ile jest różnych bezpiecznych ustawień a(n) największej liczby (n) wieżoskoczków na szachownicy n × n?
Wartości a(n) dla n od 1 do 15 tworzą ciąg:
1, 1, 1, 3, 6, 21, 75, 415, 2621, 21066, 195485, 2083543, 24744474, 323438322, 4596672672… – gotowy do umieszczenia w OEIS (jeśli autor zdecyduje się go tam zarekomendować).
Przypomnę, że analogiczny problem dla wieżogońców, czyli hetmanów, należy do klasycznych – doczekał się mnóstwa publikacji, także ściśle matematycznych i trafił do podręczników programowania. Powstało też wiele wariacji na jego temat.
Wieżoskoczek jest blisko spokrewniony z hetmanem, ponieważ także stanowi „krzyżówkę” figur ortodoksyjnych, choć w zwykłych szachach nie występuje. Pojawia się natomiast pod różnymi nazwami w tzw. szachach bajkowych, czyli w wariantach królewskiej gry oraz w problemistyce jako cesarzowa (empress).
W sumie „krzyżówki” figur szachowych są cztery. Wszystkie obejmuje poniższy trójkąt (bajkowe na różowym tle):
Podany na wstępie problem można uogólnić:
Ile jest różnych (obroty i odbicia lustrzane nie tworzą nowych ustawień) bezpiecznych (figury nie atakują się nawzajem) ustawień największej liczby danych figur na szachownicy n x n?
Odpowiedzi dla wież, skoczków, gońców i hetmanów znane są od dawna (dla skoczków to zagadnienie trywialne, bo ustawienie jest zawsze tylko jedno dla danego n). Dla wieżoskoczków dzięki Witmanowi – od kilku dni. Liczby ustawień gońcoskoczków (księżne w problemistyce) oraz hetmanoskoczków (amazonki lub superhetmany) – pozostają zagadką. W przypadku amazonek wiadomo przynajmniej, ile najwięcej można ich ustawić na szachownicach n x n; o księżnych nic nie wiadomo.
Pozostańmy przy księżnej, czyli gońcoskoczku (GS).
Zadanie jest matem pomocniczym w dwóch ruchach, czyli gra toczy się do jednej bramki – obie strony dążą do zamatowania czarnego króla, który też chce być zamatowany. Zaczynają czarne, a matują białe w drugim posunięciu. Inaczej mówiąc, rozwiązanie polega na wykonaniu czterech „bezstronnych” posunięć (czarne-białe-czarne-białe (bum) – jak w dowcipie o zakonnicy 🙂 ) , po których zaatakowany czarny król nie będzie miał gdzie odejść (ani nie będzie mógł zostać zasłonięty).
Komentarze z prawidłowymi rozwiązaniami uwalniane są wieczorem w przeddzień kolejnego wpisu. Wpisy pojawiają się co kilka dni.
Komentarze
Zadanie nie jest zbyt trudne:
1. Wg4 GSg6
2. Hg5 GSd3
Pozdrawiam 🙂
Grzegorzu, powinienem uwolnić rozwiązanie, bo jest błędne, ale nie zrobię tego, bo byłoby zbyt dużą podpowiedzią.
mp
PS szach „działa” także w macie pomocniczym
Zgadza się, gapa ze mnie 🙂 właśnie dlatego, jak kiedyś wspominałem, jestem pełnym pasji, ale kiepskim graczem 😉
1. Wg4 GSf7
2. Hg5 GSd6.
3. He5…
Zaatakowany król rzeczywiście nie ma gdzie odejść, ale to nie jest mat (powinienem dodać we wpisie, że król nie tylko nie ma gdzie odejść, ale też, że nie może być zasłonięty – mea culpa).
mp
Przez OEIS trafiłem na stronę (http://www.durangobill.com/N_Queens.html), na której znaleźć można liczbę różnych rozwiązań problemu „n amazonek na szachownicy n x n” . Dla n=2..9 nie ma rozwiązań, bo różni się od pytania postawionego przez Gospodarza (ustawienia największej możliwej liczby figur). Pozostaje wypełnić tę lukę, bo od n=10 problemy są równoważne.
PS
Zgłosiłem już chęć posiadania konta na OEIS 🙂
PPS
Ostatnia (na razie?) liczba w „moim” ciągu to 4596672672. W powyższym wpisie brak ostatniej cyferki.
Fajnie!
Z tej strony można też ściągnąć książkę Vaclava Kotesovca „Non-atacking chess pieces”, w której do cna przerobiony jest temat bezpiecznego ustawiania k różnych figur na szachownicy. Tylko że k chyba nigdy z założenia nie jest maksymalne możliwe.
mp
1. ……. Wg4
2. (GS)b2 Hg5
3. (GS)d3X
Wydaje mi się, że istnieje tylko jedno ustawienie największej możliwej liczby gońcoskoczków na każdej szachownicy. Figury powinny stać w dwóch rzędach na przeciwległych bokach z tym, że (w przypadku 8×8) na jednym z boków powinno ich być 8 a na przeciwległym tylko 6 na środkowych polach boku. W notacji szachowej te czternaście gońcoskoczków powinno stać na polach a1,a2,…a8,h2,h3,…,h7. Istnieją cztery takie ustawienia ale są one obrotami tego samego układu. Stąd mamy tylko jedno rozwiązanie. Intuicyjny dowód polega na spostrzeżeniu, że goniec atakuje najmniejszą ilość pól wtedy gdy jest bliżej krawędzi szachownicy wobec tego najmniej gdy jest na krawędzi i tak się dobrze składa że wtedy właśnie gońce się wzajemnie nie atakują a gdy zamienimy je na skoczki również się nie atakują. No i trzeba by to teraz formalnie udowodnić ale rzecz wydaje się przejrzysta.
Oj, chyba nie tak.
A005418 – to jest ciąg dla liczby różnych bezpiecznych ustawień maksymalnej liczby gońców (2n – 2) na szachownicy nxn. W opisie na OEIS nie ma wprawdzie wzmianki o bishops, ale z Bishops problem na Wolframie wynika, że tak właśnie jest.
I teraz: czy np. z 36 różnych bezpiecznych ustawień 14 gońców na szachownicy 8×8 35 odrzucimy po zastąpieniu gońców skoczkami, bo zawsze jakieś skoczki będą się atakować?
mp
Potwierdzam wynik witmana dla wieżoskoczków. Mój program dał te same liczby.
Wg4
GSd4
Hf5
GSf3
Wiąz, w Twoim rozwiązaniu czarny król nie jest szachowany.
Powinno być tak:
Wg4
GSf7
Hg5
GSd6
🙂
🙂 no tak:):) obstawiony ze wszech stron ale nie szachowany:):)
Wg4
GSf7
Hg5
GSd6
@Spytko z Melsztyna: tak sobie zerknąłem na planszę i od razu widać na przykład układ gońców podobny do a1,a2,…,a8,h2,h3,…,h7, z tym, że na przykład przesuńmy a8 na h1, robi to już drugi układ. W sumie widać na gołe oko jeszcze kilka układów, choćby z układu a1-a7,h1-h7, przesunąć 2 gońce: z a2 na b1 i h7 na g8 i tak dalej… Liczba gońców się nie zmienia a układy różne. Jak się nie myle można tak wygenerować jeszcze 4 układy.
@Wiąz: Dokładnie tak, mam już pomysł jak to zrobić programem. Gońce powinny siedzieć pod ścianami jak panny na zabawie w remizie strażackiej. Trzeba znależć wszystkie możliwe takie „usadzenia”, potem zredukować je do 36 eliminując odbicia i obroty i w końcu wyrzucić te które po zamianie gońców na skoczki daja konflikty.
Marny że mnie szachista, nie potrafię przewidzieć następnego ruchu czarnych 🙂
Wg4
GSb2
Hg5
GSd3
Teraz już ok:)
Racja, po raz kolejny 🙂 znowu się zagapiłem, upieram się, że to jednak mea culpa – wszak reguły szachowe są bezwzględne, nawet w różnych wariantach królewskiej gry. Wygląda na to, że znowu nie zastanowiłem się dokładnie.
Teraz podaję już poprawne rozwiązanie 😉
1. Wg4 GSb2
2. Hg5 GSd3.
Teraz już musi być dobrze, ponieważ wykorzystałem zaletę skoczka: nie da się przed nim zasłonić. Od razu pomyślałem, że takim ruchem trzeba zaatakować króla, ale później w ferworze walki, gdzieś mi to umknęło.
Oczywiście, teraz jest tip-top
mp
W końcu przecież czarne pragną zamatowania czarnego króla, a nie złamania zasad gry w szachy – mea culpa…
Maksymalna liczba księżnych jakie można ustawić na szachownicy n x n, różni się od sytuacji dotyczącej gońców (2n-2) tylko dla n=3. Wtedy można ustawić tylko 3 księżne.
Przerobiłem program z wieżoskoczków na problem gońców i księżnych (na razie bez optymalizacji za pomocą lematu Burnside’a).
Myślę, że jest ok, bo wyniki są następujące:
1. Liczba bezpiecznych ustawień n gońców na szachownicy n x n http://ideone.com/xa1Tlb
Potwierdza się ciąg http://oeis.org/A002465 i mamy nowy ciąg różnych ustawień: 1,1,5,37,447,6770,… którego w OEIS nie ma :).
2. Liczba bezpiecznych ustawień największej liczby gońców na szachownicy n x n http://ideone.com/DV8w8o
Dla wszystkich ustawień mamy „sympatyczny” ciąg:
1,4,8,16,32,64,128,256,512,…
Dla różnych:
1,1,2,3,6,10,20,36,72,… co potwierdza http://oeis.org/A005418
3.Liczba bezpiecznych ustawień n księżnych na szachownicy n x n http://ideone.com/8fwULv
Dla wszystkich ustawień:
1,4,6,86,854,9556,…
Dla różnych:
1,1,2,14,115,1221,…
(obu ciągów nie ma w OEIS)
4. Liczba bezpiecznych ustawień największej liczby księżnych na szachownicy n x n http://ideone.com/L93zp3 (Tu http://ideone.com/2ukf1L można zobaczyć różne ustawienia na szachownicy 6×6).
Okazuje się, że dostajemy ciągi podobne do tych z przypadku dla gońców, tylko przesunięte.
Dla wszystkich ustawień:
1,4,6,8,8,16,32,64,128,256,512,…
Dla różnych:
1,1,2,2,2,3,6,10,20,36,72,…
Pozdrawiam 🙂
PS
Zgłosiłem do OEIS ciąg dotyczący wieżoskoczków, ale na razie nikt z uprawnionych do aprobowania, tego nie zrobił :(.
Może ktoś jest zorientowany czy trzeba zrobić coś więcej?
ad. 3: ciąg „dla wszystkich” jest w książce Kotesovca, choć do OEIS nie trafił.
ad. PS: moim zdaniem trzeba poczekać (choćby na jakąś reakcję).
mp
https://oeis.org/A218244 🙂
Congratulations
mp
Ciąg wieżoskoczków jest już w OEIS http://oeis.org/search?q=1%2C1%2C1%2C3%2C6%2C21%2C75&sort=&language=english