Uwielbiam przesuwane łamigłówki, ale ostatnio nie miałem na nie czasu. Dlatego potrzebuję programu, który dałby mi rozwiązanie łamigłówek z przesuwanymi kafelkami, w szczególności układanki Klotskiego.
Twoje dane będą miały następujący format:
#######
#001gg#
##.222#
.######
gdzie #
reprezentuje ściany, .
reprezentuje otwarty obszar, g
reprezentuje cel, a sąsiednie liczby reprezentują różne bloki. Możesz założyć, że:
- Nie będzie więcej niż 10 bloków
- Nie będzie dwóch bloków o tym samym numerze
- Wszystkie bloki zostaną otoczone ścianami
- Siatka jest prostokątna
0
Blok jest na tyle duża, aby pokryć wszystkie kwadraty bramkowych.- Istnieje prawidłowe rozwiązanie
Musisz zwrócić sekwencję ruchów, która spowoduje umieszczenie 0
bloku tak, aby obejmował wszystkie pola bramkowe. Bloki nie mogą przechodzić przez ściany ani inne bloki. Dla powyższej układanki byłaby odpowiednia sekwencja
2L,1R,1R,1D,0R,0R,0R
podczas gdy reprezentuje przesunięcie 2
bloku 1 kwadrat w lewo, 1
blok 2 kwadraty w prawo (u góry bramki), a następnie 1 kwadrat w dół, a następnie 0
blok 3 kwadraty w prawo.
W rzeczywistości istnieje kilka sekwencji, które będą działać na powyższy problem, a wyprodukowanie dowolnej z nich jest dopuszczalne. Twoje rozwiązanie powinno być optymalne, co oznacza, że powinno stworzyć sekwencję, która rozwiązuje zagadkę w jak najmniejszej liczbie kroków.
Sekwencja powinna być wydrukowana jak powyżej, ale może być oddzielona przecinkiem, nową linią lub spacją. Nie obchodzi mnie, czy są przecinki lub białe spacje. Powinieneś wytworzyć wynik w rozsądnym czasie (maksymalnie 120 sekund na poniższych łamigłówkach).
Puzzle 1:
..####..
..#00#..
###00###
#......#
#.1122.#
##3124##
.#3344#.
.##55##.
..#gg#..
..####..
Puzzle 2:
######
#1002#
#1002#
#3445#
#3675#
#8gg9#
######
Puzzle 3:
.####.
##1g##
#22g3#
#4255#
#4.56#
#.006#
#7008#
######
Puzzle 4:
.####.
##00##
#.00g#
#.0.1#
#..g2#
######
To jest golf golfowy, więc wygrywa najkrótsze rozwiązanie (w bajtach)!
źródło
Odpowiedzi:
Python, 1761
Niby spłonęło to pytanie, więc nie mogłem zmusić się do gry w golfa. Tak czy inaczej, teraz jest to jedyne rozwiązanie, które rozwiązuje wszystko w terminie (najdłuższy, # 3, zajmuje 27 sekund).
źródło
JavaScript (ES6), 446
388Szerokość Pierwsze wyszukiwanie, więc pierwsze znalezione rozwiązanie jest najkrótsze.
Chociaż nadal uważam, że to dobre rozwiązanie, nie jest wystarczająco dobre. Nawet po sprawdzeniu milionów pozycji (czas działania kilka minut) nie mogłem znaleźć rozwiązania na przykład 2 i 3.
Edytuj zmodyfikowaną wersję ES6 aby przekroczyć limit czasu wykonywania javascript. Puzzle 3 rozwiązane w 7 minut, 145 kroków. Puzzle 2 rozwiązane w 10 minut, 116 kroków
Edytuj 2 Duże przyspieszenie, używając pomysłu @ orlp, by uważać za równe dowolne dwa bloki o tym samym kształcie (wyłączając blok „0”, który jest specjalny). Zmniejsza to przestrzeń odwiedzanych pozycji podczas BSF. Na przykład dla łamigłówki 2 każda pozycja z zamienionym blokiem 1, 2, 3 lub 5 jest naprawdę taka sama.
Czas: najdłuższy jest układanka 3, ~ 20 sekund na moim laptopie.
Użyj Firefoksa, aby przetestować nowy JsFiddle .
Przestarzały
EcmaScript 6 (FireFox) JSFiddleEcmaScript 5 (Chrome) JSFiddlePrzykład
Łamigłówka 1
Puzzle 2
Puzzle 3
Puzzle 4
źródło