15 Puzzle to słynna łamigłówka polegająca na przesuwaniu 15 płytek po siatce 4x4. Zaczynając od losowej konfiguracji, celem jest ułożenie płytek we właściwej kolejności. Oto przykład rozwiązanej 15 zagadek:
01 02 03 04
05 06 07 08
09 10 11 12
13 14 15
Każdy ruch na układance ma postać Góra / Dół / Lewo / Prawo. Ruch „W dół” polega na przesuwaniu płytki w dół nad pustym miejscem w dół. Ruch „w prawo” polega na przesunięciu płytki w prawo, w puste miejsce. Oto jak plansza wygląda po ruchach w dół i w prawo.
01 02 03 04
05 06 07 08
09 10 11
13 14 15 12
Celem tego wyzwania jest napisanie programu, który wygeneruje serię ruchów potrzebnych do rozwiązania 15 puzzli. Zwycięzcą jest program, który rozwiązuje pięć przypadków testowych (poniżej) w jak najmniejszej liczbie ruchów. Wygenerowane rozwiązanie nie musi być rozwiązaniem idealnym, musi być po prostu lepsze niż konkurencja. Dla każdego indywidualnego przypadku testowego program nie powinien zająć więcej niż dziesięć sekund na rozsądnej maszynie.
Twój program musi być w stanie rozwiązać każdą zagadkę, którą można rozwiązać, wykorzystuję tylko te pięć przypadków testowych jako punktację.
Twój program otrzyma nierozwiązane 15 puzzli jako dane wejściowe w formacie tablicy 2D. Tablicę 2D można sformatować zgodnie z używanym językiem lub zmienić, jeśli język nie ma tablic 2D. Pierwszym elementem pierwszej podgrupy będzie liczba w lewym górnym rogu, a ostatnim elementem pierwszej pod-tablicy będzie liczba w prawym górnym rogu. ZA0
będzie pustą przestrzenią.
Jako wynik program powinien wydrukować listę ruchów w kolejności, w jakiej należy je wykonać. Każdy krok powinien być ponumerowany, aby zwiększyć użyteczność wyników.
EDYCJA: W oparciu o komentarze pozwolę, aby dane wyjściowe były w formie Dół / Góra / etc lub w postaci współrzędnych fragmentu do przesunięcia. Ponieważ nie jest to golf golfowy, najważniejszą częścią jest rozwiązanie zagadki.
Niektóre inne ogólne zasady nie wymagają korzystania ze źródła zewnętrznego itp.
Przypadek testowy 1
([5,1,7,3],[9,2,11,4],[13,6,15,8],[0,10,14,12])
Przykładowe dane wyjściowe:
1: Down
2: Down
3: Down
4: Left
....
Przypadek testowy 2
([2,5,13,12],[1,0,3,15],[9,7,14,6],[10,11,8,4])
Przypadek testowy 3
([5,2,4,8],[10,0,3,14],[13,6,11,12],[1,15,9,7])
Przypadek testowy 4
([11,4,12,2],[5,10,3,15],[14,1,6,7],[0,9,8,13])
Przypadek testowy 5
([5,8,7,11],[1,6,12,2],[9,0,13,10],[14,3,4,15])
źródło
Odpowiedzi:
PyPy, 195 ruchów, ~ 12 sekund obliczeń
Oblicza optymalne rozwiązania za pomocą IDA * z heurystyką „odległości spaceru” powiększoną o konflikty liniowe. Oto optymalne rozwiązania:
I kod:
źródło
JavaScript (ES6) ogółem kroki 329 dla wszystkich 5 przypadków testowych w ~ 1min
Edytuj Ta sama strategia, różne cele, lepsze rozwiązanie. Wolniej ...
Mniej więcej tak rozwiązuję to ręcznie: używanie pośrednich celów Po każdym celu względne płytki nie są ponownie przenoszone Każdy pośredni cel jest osiągany za pomocą parametrycznej funkcji BSF. 2 parametry to warunek pętli L (powtórz, gdy jest prawdziwy) i warunek wyboru S (wybierz, który kafelek można przenieść). Kroki:
Notatka dodatkowa Nie sprawdzam położenia płytek 14 i 15. Nie rozwiązane łamigłówki, takie jak
[11,4,12,2,,15,10,3,5,,14,1,6,7,,0,9,8,13]
14 i 15, zostaną zamienione.Otwórz fragment kodu, aby przetestować lub odtworzyć (tylko Firefox)
Pokaż fragment kodu
Zestaw testowy W konsoli Firefox / FireBug
Wydajność
źródło
Zacząłem pracować nad tym problemem i do tej pory chciałem współpracować z moim kodem. Jak stwierdził Gareth, problem jest porównywalny z 8-kafelkową łamigłówką, więc kod oparty jest na wspaniałym rozwiązaniu Keitha Randalla, a więc w Pythonie. To rozwiązanie może rozwiązać wszystkie 5 przypadków testowych o łącznej sumie mniejszej niż 400 ruchów, a także inne zagadki. Zawiera zoptymalizowane i brutalne rozwiązanie. Kod jest już trochę rozdęty. Dane wyjściowe są skrócone jak „llururd ..”. Mam nadzieję, że jest to pomocne. http://www.penschuck.org/joomla/tmp/15Tile.txt (wyjaśnienie) http://www.penschuck.org/joomla/tmp/tile15.txt (kod python)
źródło