Czy potrafisz rozwiązać zagadkę z ośmioma królowymi w czasie kompilacji?
Wybierz dowolny odpowiedni format wyjściowy.
Szczególnie interesuje mnie rozwiązanie do metaprogramowania szablonów C ++, ale możesz używać języków o podobnych konstrukcjach, takich jak na przykład system typów Haskell.
Idealnie twój metaprogram wyprowadziłby wszystkie rozwiązania. Bez kodowania.
puzzle-solver
compile-time
R. Martinho Fernandes
źródło
źródło
Odpowiedzi:
Mój metaprogram zawiera wszystkie 92 rozwiązania. Są drukowane jako komunikaty o błędach:
Oznacza to, że pierwszą królową należy umieścić na y = 1, drugą na y = 5, trzecią na y = 8 i tak dalej.
Po pierwsze, kilka przydatnych meta-funkcji:
Następnie dwie interesujące meta-funkcje (zwróć uwagę na liczbę pojedynczą i mnogą):
Zmienna
queens
przechowuje współrzędne y królowych umieszczonych do tej pory na planszy. Poniższe trzy zmienne przechowują wiersze i przekątne, które są już zajęte przez królowe.x
iy
powinny być zrozumiałe.Pierwszy argument
if_then_else
sprawdzający, czy bieżąca pozycja jest zablokowana. Jeśli tak, rekursja kończy się, zwracając (bez znaczenia) wynik 0. W przeciwnym razie królowa jest umieszczana na planszy, a proces jest kontynuowany z następną kolumną.Gdy x osiągnie 8, znaleźliśmy rozwiązanie:
Ponieważ
print
szablon nie ma elementusolution
, kompilator generuje błąd.I wreszcie, aby rozpocząć proces, sprawdzamy
value
członka pustej planszy:Kompletny program można znaleźć na stronie ideone .
źródło
Wymyśliłem rozwiązanie, które wykorzystuje system typu Haskell. Poszukałem trochę istniejącego rozwiązania problemu na poziomie wartości , nieco go zmieniłem, a następnie podniosłem do poziomu typu. Wymyśliłem wiele na nowo. Musiałem także włączyć kilka rozszerzeń GHC.
Po pierwsze, ponieważ liczby całkowite nie są dozwolone na poziomie typu, musiałem ponownie odkryć liczby naturalne, tym razem jako typy:
Algorytm, który zaadaptowałem, dodaje i odejmuje wartości naturalne, więc musiałem je też wymyślić na nowo. Funkcje na poziomie typu są definiowane za pomocą klas typów. Wymaga to rozszerzenia wielu klas typów parametrów i zależności funkcjonalnych. Klasy typów nie mogą „zwracać wartości”, dlatego używamy do tego dodatkowego parametru, w sposób podobny do PROLOG.
Rekurencja jest implementowana z asercjami klas, więc składnia wygląda nieco wstecz.
Następne były booleany:
I funkcja do porównywania nierówności:
I listy ...
if
brakuje również na poziomie typu ...Dzięki temu wszystkie maszyny pomocnicze, których użyłem, były na miejscu. Czas rozwiązać sam problem!
Rozpoczęcie od funkcji sprawdzania, czy dodanie królowej do istniejącej planszy jest w porządku:
Zwróć uwagę na użycie asercji klasowych w celu uzyskania wyników pośrednich. Ponieważ zwracane wartości są w rzeczywistości dodatkowym parametrem, nie możemy po prostu wywoływać asercji bezpośrednio od siebie. Ponownie, jeśli używałeś PROLOGA, możesz uznać ten styl za nieco znajomy.
Po wprowadzeniu kilku zmian w celu wyeliminowania potrzeby używania lambda (które mogłem wdrożyć, ale postanowiłem wyjechać na kolejny dzień), tak wyglądało oryginalne rozwiązanie:
map
jest funkcją wyższego rzędu. Myślałem, że zaimplementowanie meta-funkcji wyższego rzędu byłoby zbyt dużym problemem (znowu lambdas), więc po prostu wybrałem prostsze rozwiązanie: ponieważ wiem, które funkcje będą mapowane, mogę zaimplementowaćmap
dla nich specjalizowane wersje , aby nie były funkcje wyższego rzędu.A ostatnią meta-funkcję można teraz napisać:
Pozostało po prostu jakiś sterownik, który nakłonił maszynę do sprawdzania typu do wypracowania rozwiązań.
Ten metaprogram ma działać na narzędziu sprawdzania typu, więc można odpalić
ghci
i zapytać o typqueens eight
:To dość szybko przekroczy domyślny limit rekurencji (to marne 20). Aby zwiększyć ten limit, musimy wywołać
ghci
z-fcontext-stack=N
opcją, gdzieN
jest pożądana głębokość stosu (N = 1000 i piętnaście minut to za mało). Nie widziałem jeszcze tego ukończenia, ponieważ zajmuje to bardzo dużo czasu, ale udało mi się do niego dotrzećqueens four
.Jest idealny program na ideone z niektórymi maszynami do ładnego drukowania typów wyników, ale
queens two
może działać tylko bez przekraczania limitów :(źródło
C za pośrednictwem preprocesora
Myślę, że komitet ANSI dokonał świadomego wyboru, aby nie rozszerzać preprocesora C do tego stopnia, że jest całkowicie ukończony przez Turinga. W każdym razie nie jest wystarczająco silny, aby rozwiązać problem ośmiu królowych. Nie w jakikolwiek ogólny sposób.
Ale można to zrobić, jeśli chcesz na stałe zakodować liczniki pętli. Oczywiście nie ma prawdziwego sposobu zapętlenia, ale możesz użyć samowyłączenia (via
#include __FILE__
), aby uzyskać ograniczony rodzaj rekurencji.Pomimo przerażającej ilości powtarzających się treści, zapewniam cię, że naprawdę rozwiązuje ona problem ośmiu królowych algorytmicznie. Niestety jedyną rzeczą, której nie mogłem zrobić z preprocesorem, jest implementacja ogólnej struktury danych stosu push-down. Rezultat jest taki, że musiałem zakodować wartość,
i
gdziekolwiek była używana, aby wybrać inną wartość do ustawienia. (W przeciwieństwie do pobierania wartości, które można wykonać całkowicie ogólnie. Dlatego#if
u góry pliku, który decyduje o tym, czy można dodać królową w bieżącej pozycji, nie trzeba powtarzać osiem razy).W kodzie preprocesora,
i
ij
wskazują aktualną pozycję rozważane, podczasr
,p
in
którego śledzić szeregi i przekątne są aktualnie niedostępne miejsca. Jednaki
również pełni funkcję licznika zaznaczającego bieżącą głębokość rekurencji, więc tak naprawdę wszystkie inne wartości faktycznie używają i jako rodzaju indeksu dolnego, dzięki czemu ich wartości są zachowywane po wznowieniu z rekurencji. (A także z powodu poważnej trudności w modyfikacji wartości symbolu preprocesora bez jego całkowitego zastąpienia.)Skompilowany program drukuje wszystkie 92 rozwiązania. Rozwiązania są osadzone bezpośrednio w pliku wykonywalnym; Wyjście preprocesora wygląda następująco:
Można to zrobić, nawet jeśli wyraźnie nie powinno.
źródło
Oto rozwiązanie C ++ 11 bez żadnych szablonów:
Rozwiązanie jest zakodowane jako cyfry dziesiętne, jak w odpowiedziach FredOverflow. GCC 4.7.1 kompiluje powyższy plik do następującego źródła zestawu z
g++ -S -std=c++11 8q.cpp
:Wartość tego symbolu
places
to 84136275, tj. Pierwsza królowa jest na a8, druga na b4 itd.źródło
Szablon c ++, z zdefiniowaną tylko jedną klasą szablonów:
więc komunikat o błędzie będzie wyglądał następująco:
błąd C2440: „rzutowanie typu”: nie można przekonwertować z „int” na „char [15863724]”
źródło