O piętnastce | Historia, parzystość i 14-15 Sama Loyda

Szał z 1880 roku

Układanka powstała w stanie Nowy Jork w latach 70. XIX wieku; za jej wynalazcę uchodzi zwykle Noyes Chapman, poczmistrz z miejscowości Canastota. Na początku 1880 roku wywołała szał, najpierw w całych Stanach Zjednoczonych, a potem w Europie.

14-15 Sama Loyda

Amerykański twórca łamigłówek Sam Loyd twierdził później, że to on wynalazł tę układankę, i opowiadał o nagrodzie 1000 dolarów dla każdego, kto rozwiąże ją, gdy zamienione są tylko klocki 14 i 15. Nikt nie zdobył nagrody i nikt nie mógł jej zdobyć: tej pozycji nie da się rozwiązać. Jego twierdzenie, że jest wynalazcą, też nie było prawdziwe.

Dlaczego połowa pozycji jest niemożliwa

Potraktuj puste pole jak szesnasty klocek. Każde przesunięcie zamienia puste pole z jednym klockiem. Aby wrócić do swojego rogu, puste pole musi przesunąć się tyle samo razy w lewo co w prawo i tyle samo razy w górę co w dół, więc pozycję z pustym polem w rogu zawsze dzieli od rozwiązanego ułożenia parzysta liczba zamian. Zamiana 14 i 15 to jedna zamiana, czyli nieparzysta, więc żadne przesunięcia nie mogą do niej doprowadzić. W 1879 roku William Johnson i William Story udowodnili, że osiągnąć można dokładnie połowę wszystkich ułożeń.

Test dla każdej pozycji

Policz pary klocków, które stoją w złej kolejności, gdy czytasz ramkę wiersz po wierszu. Na planszy 3×3 lub 5×5 pozycję da się rozwiązać, gdy ta liczba jest parzysta. Na planszy 4×4 dodaj numer wiersza pustego pola liczony od dołu: pozycję da się rozwiązać, gdy suma jest nieparzysta.

Rozwiązywanie komputerem

Komputer może szukać drogi powrotnej algorytmem A*, który zawsze najpierw bada najbardziej obiecującą pozycję. Szacuje on liczbę brakujących ruchów na podstawie tego, jak daleko każdy klocek jest od swojego miejsca, plus dwa ruchy za każdą parę klocków, które blokują się nawzajem we własnym wierszu lub kolumnie. Znalezienie najkrótszego rozwiązania staje się bardzo trudne na dużych planszach. Najtrudniejsze pozycje piętnastki wymagają 80 ruchów, a układanka 8 nigdy nie wymaga więcej niż 31.

Wypróbuj w PictorX

Otwórz Piętnastkę i kliknij klocek, aby go przesunąć. Wymieszaj układa klocki w nową pozycję, którą da się rozwiązać, Rozwiąż odtwarza rozwiązanie ruch po ruchu, a Pokaż klocki na miejscu koloruje numery klocków, które są już na właściwych polach. Wybierz „14-15 Loyda”, aby zobaczyć niemożliwą pozycję, a Rozmiar pozwala przełączać między 3×3, 4×4 i 5×5.

Często zadawane pytania

Kto wymyślił piętnastkę?

Za wynalazcę uchodzi zwykle Noyes Chapman, poczmistrz z miejscowości Canastota w stanie Nowy Jork; układanka powstała w latach 70. XIX wieku. Późniejsze twierdzenie Sama Loyda, że to on ją wynalazł, było fałszywe.

Czy układankę 14-15 da się rozwiązać?

Nie. Od rozwiązanego ułożenia dzieli ją jedna zamiana, a każdą pozycję osiągalną przesunięciami dzieli od niego parzysta liczba zamian.

Ile pozycji ma piętnastka?

16 pól można wypełnić na 20 922 789 888 000 sposobów. Dokładnie połowę z nich, 10 461 394 944 000, można osiągnąć, przesuwając klocki.

Czy PictorX coś wysyła?

Nie. Układanka jest rysowana na płótnie w przeglądarce. Zapisz pobiera PNG, a Edytuj otwiera ten obraz w edytorze PictorX.