Biorąc pod uwagę liczbę całkowitą 2n, znajdź liczbę możliwych sposobów ułożenia 2n ^ 2 czarnych pionków i 2n ^ 2 białych pionków na szachownicy 2n przez 2n, tak aby żaden pionek nie atakował innego.
- Czarny pionek może atakować tylko białego pionka i odwrotnie.
- Stosowane są zwykłe zasady szachowe ataku, tj. Białe pionki atakują kwadraty bezpośrednio po przekątnej z przodu, a czarne pionki atakują kwadraty natychmiast po przekątnej do tyłu (jak widzi biały obserwator).
- Cały obrót, odbicia liczą się jako odrębne.
Wygrywa program, który może wypisać wszystkie możliwe konfiguracje dla najwyższej wartości 2n w 120 sekund. (Wszystkie programy są mile widziane)
Na przykład program Alicji może poradzić sobie z upto n = 16 w ciągu 120 sekund, podczas gdy program Boba może poradzić sobie z upto n = 20 w tym samym czasie. Bob wygrywa.
Platforma: Linux 2.7GHz @ 4 procesory
fastest-code
combinatorics
chess
Agnishom Chattopadhyay
źródło
źródło
2n^2
pionki, jest to, że(2n)^2
albo2(n^2)
?Odpowiedzi:
Java, n = 87 na moim komputerze
Wynik dla n = 87 wynosi
Obecnie korzysta z dynamicznego schematu programowania, który przyjmuje operacje O (n ^ 4), aby obliczyć sposoby umieszczania
p
pionków na kwadratach jednego koloru0 <= p <= n^2
. Myślę, że powinno być to możliwe znacznie wydajniej.Sprawdź wyniki tutaj.
Wyjaśnienie
W prawidłowym rozwiązaniu najniższe białe pionki w każdej kolumnie muszą tworzyć zygzakowatą linię:
Oznacza to, że wysokość linii w kolumnie c musi wynosić +/- 1 od jej pozycji w kolumnie c - 1 . Linia może również przechodzić do dwóch wyimaginowanych rzędów powyżej górnej części planszy.
Możemy użyć programowania dynamicznego, aby znaleźć liczbę sposobów narysowania linii na pierwszych c kolumnach, które zawierają p pionki na tych kolumnach, jest na wysokości h na c- tej kolumnie, wykorzystując wyniki dla kolumny c - 1 , wysokości h + / - 1 , a liczba pionków p - h .
źródło
Jawa
Obecnie mój kod jest bardzo długi i żmudny, pracuję nad tym, aby był szybszy. Używam metody rekurencyjnej, aby znaleźć wartości. Oblicza pierwsze 5 w ciągu 2 lub 3 sekund, ale potem robi się znacznie wolniej. Ponadto nie jestem jeszcze pewien, czy liczby są prawidłowe, ale wydaje się, że pierwszych kilka zgadza się z komentarzami. Wszelkie sugestie są mile widziane.
Wynik
Wyjaśnienie
Podstawową ideą jest rekurencja. Zasadniczo zaczynasz od pustej planszy, planszy ze wszystkimi zerami. Metoda rekurencyjna sprawdza tylko, czy może umieścić czarnego lub białego pionka w następnej pozycji, jeśli może umieścić tylko jeden kolor, umieszcza go tam i wywołuje. Jeśli umieści oba kolory, nazywa się dwa razy, po jednym z każdym kolorem. Za każdym razem, gdy się wywołuje, zmniejsza kwadraty w lewo i pozostawia odpowiedni kolor. Po wypełnieniu całej planszy zwraca bieżącą liczbę + 1. Jeśli stwierdzi, że nie ma sposobu, aby umieścić czarnego lub białego pionka w następnej pozycji, zwraca 0, co oznacza, że jest to martwa ścieżka.
Kod
Wypróbuj tutaj (nie działa wystarczająco szybko dla Ideone, więc ostatnia wartość nie jest drukowana, wygląda na to, że moje rozwiązanie nie jest zbyt dobre!)
źródło
C ++ z pthreads, n =
147156Najnowszy wynik to uruchomienie tego samego kodu, co poprzednio, na maszynie o większej mocy. To było teraz uruchomione na pulpicie z czterordzeniowym i7 (Core i7-4770), który osiągnął n = 156 w 120 sekund. Wynik to:
Wykorzystuje to algorytm programowania dynamicznego. Początkowo zastanawiałem się nad podejściami, w których wynik byłby budowany rząd po rzędzie, ale nigdy nie mogłem znaleźć sposobu na rozszerzenie rozwiązania bez śledzenia tony stanu.
Kluczowymi spostrzeżeniami, które umożliwiły racjonalnie skuteczne rozwiązanie, były:
Jeśli spojrzysz na jedną przekątną prawidłowej konfiguracji, zawsze składa się ona z sekwencji czarnych pionków, a następnie sekwencji białych pionków (gdzie każda z sekwencji może być również pusta). Innymi słowy, każdą przekątną można w pełni scharakteryzować liczbą czarnych pionków.
Dlatego stan śledzony dla każdej przekątnej to liczba prawidłowych konfiguracji pionków dla każdej kombinacji:
Przechodząc od jednej przekątnej do następnej, istnieje inne ograniczenie do budowania prawidłowych rozwiązań: Pozycja oddzielająca czarne pionki od białych pionków nie może wzrosnąć. Tak więc liczba prawidłowych konfiguracji jest obliczana jako suma prawidłowych konfiguracji poprzedniej przekątnej dla pozycji, które są równe lub większe.
Podstawowy krok DP jest wtedy bardzo prosty. Każda wartość na przekątnej jest tylko sumą wartości z poprzedniej przekątnej. Jedyną nieco bolesną częścią jest prawidłowe obliczanie wskaźników i zakresów pętli. Ponieważ pracujemy nad przekątnymi, długość zwiększa się w pierwszej połowie obliczeń, a zmniejsza w drugiej połowie, co sprawia, że obliczanie zakresów pętli jest bardziej skomplikowane. Należy również wziąć pod uwagę wartości na granicy tablicy, ponieważ mają one tylko sąsiadujących po przekątnej sąsiadów po jednej stronie podczas przechodzenia od przekątnej do przekątnej.
Ilość używanej pamięci to O (n ^ 3). Trzymam dwie kopie danych stanu i między nimi ping ponga. Wierzę, że byłoby możliwe działanie z jedną instancją danych stanu. Ale trzeba bardzo uważać, aby żadne wartości nie były aktualizowane, zanim stare wartości zostaną w pełni wykorzystane. Ponadto nie działałoby to dobrze w przypadku równoległego przetwarzania, które wprowadziłem.
Złożoność środowiska wykonawczego jest ... wielomianowa. Algorytm zawiera 4 zagnieżdżone pętle, więc na pierwszy rzut oka wyglądałoby to jak O (n ^ 4). Ale oczywiście potrzebujesz bigintów w tych rozmiarach, a same liczby stają się dłuższe w większych rozmiarach. Liczba cyfr w wyniku wydaje się rosnąć mniej więcej proporcjonalnie do n, co dałoby całość O (n ^ 5). Z drugiej strony znalazłem pewne ulepszenia wydajności, które pozwalają uniknąć przejścia przez pełny zakres wszystkich pętli.
Chociaż jest to wciąż dość drogi algorytm, staje się on znacznie szerszy niż algorytmy wyliczające rozwiązania, które są wykładnicze.
Kilka uwag na temat wdrożenia:
Główny kod algorytmu.
THREADS
kontroluje liczbę używanych wątków, przy czym liczba rdzeni procesora powinna być rozsądnym punktem wyjścia:To także potrzebuje klasy bigint, którą napisałem w tym celu. Zauważ, że nie jest to klasa bigint ogólnego przeznaczenia. To wystarczy, aby obsłużyć operacje używane przez ten konkretny algorytm:
źródło
Fantom
Oto pierwszy post, który konfiguruje framework. Myślę, że procedura jest stosunkowo dobra, ale wdrożenie jest w tej chwili trochę do bani. Prawdopodobnie muszę spróbować zminimalizować liczbę wykonywanych obliczeń, a zamiast tego przekazać więcej stałych.
Strategia
Zasadniczo każdy biały pionek musi atakować inne białe pionki. Zacznę więc od umieszczenia białego pionka, umieszczenia pionków w każdym zaatakowanym miejscu i zasadniczo wypełnienia planszy wszystkimi miejscami, którymi MUSI iść biały pionek. Przestaję, jeśli dodałem już zbyt wiele białych pionków. Jeśli na końcu mam dokładnie 2n ^ 2 pionki, jest to rozwiązanie. Jeśli mniej, dodaj kolejny biały pionek, wypełnij wszystkie wymagane miejsca i policz ponownie. Rekurencyjnie dzielę się za każdym razem, gdy zostanie znalezione wypełnienie mniejsze niż 2n ^ 2, i obliczam liczbę rozwiązań z dodanym pionkiem i bez niego.
Kod
Wynik
W tej chwili jest tylko 5, ale myślę, że większość problemu dotyczy implementacji.
Test
źródło