Godziny szczytu (układanka)

Zestaw puzzli Godziny szczytu

Godziny szczytu to puzzle z przesuwanymi klockami, wymyślone przez Noba Yoshigaharę w latach 70. XX wieku. Po raz pierwszy został sprzedany w Stanach Zjednoczonych w 1996 roku. Obecnie jest produkowany przez ThinkFun (dawniej Binary Arts).

ThinkFun sprzedaje teraz spin-offy Rush Hour Rush Hour Jr. , Safari Rush Hour , Railroad Rush Hour , Rush Hour Brain Fitness i Rush Hour Shift , z zagadkami autorstwa Scotta Kima .

Gra

Plansza to siatka 6 × 6 z rowkami w płytkach umożliwiającymi przesuwanie się samochodów, tacką na karty do przechowywania kart, aktualnym aktywnym posiadaczem karty i otworem wyjściowym. Gra zawiera 16 pojazdów (12 samochodów, 4 ciężarówki), każdy w innym kolorze, oraz 40 kart puzzli. Samochody i ciężarówki mają szerokość jednego kwadratu, ale samochody mają dwa kwadraty długości, a ciężarówki trzy kwadraty. Pojazdy można przesuwać tylko po linii prostej na siatce; obrót jest zabroniony. Karty puzzli, z których każda ma numer poziomu wskazujący stopień trudności wyzwania, przedstawiają pozycje startowe samochodów osobowych i ciężarowych. Nie wszystkie samochody i ciężarówki są używane we wszystkich wyzwaniach.

Cel

Celem gry jest wydostanie się tylko czerwonego samochodu przez wyjście z planszy, usuwając inne pojazdy z drogi. Jednak samochody i ciężarówki (ustawione przed grą, zgodnie z kartą układanki) blokują ścieżkę, co jeszcze bardziej utrudnia układankę.

Wydania

Regular Edition zawiera czterdzieści łamigłówek podzielonych na cztery różne poziomy trudności, od początkującego do eksperta. Edycja Deluxe zawiera czarną planszę do gry, pudełko na karty zamiast tacki z edycji regularnej oraz sześćdziesiąt nowych łamigłówek z dodatkowym poziomem trudności: Wielki Mistrz. Ultimate Collector's Edition ma planszę do gry, na której mogą znajdować się pojazdy, które nie są w grze, i może wyświetlać aktywną kartę na wyświetlaczu przypominającym billboard. Ultimate Collectors Edition zawiera również 155 nowych łamigłówek (niektóre z nich pochodzą z trzeciego zestawu kart) oraz białą limuzynę. W 2011 roku plansza została zmieniona na czarną, podobnie jak w wersji Deluxe Edition.

Wersja gry na iOS została wydana w 2010 roku.

Rozszerzenia

Wydano trzy oficjalne rozszerzenia, zwane „pakietami dodatków”: Zestaw kart 2, który zawiera czerwony samochód sportowy zajmujący 2 pola; Zestaw kart 3, który zawiera białą limuzynę zajmującą 3 pola; oraz Zestaw kart 4, który jest dostarczany z taksówką zajmującą 2 pola. Każdy zestaw zawiera również 40 nowych, ekskluzywnych wyzwań — od poziomu średniozaawansowanego po arcymistrzowskiego — które wykorzystują nowe pojazdy zamiast (lub oprócz) czerwonego samochodu. Wszystkie trzy dodatki będą działać ze wszystkimi edycjami gry. Ponadto, podobnie jak edycja zwykła gry z 2011 roku, karty wszystkich trzech rozszerzeń zostały zmienione, aby miały nowe poziomy i projekt, aby pasowały do nowego koloru planszy z edycji regularnej.

Złożoność obliczeniowa na większych tablicach

Minimalne rozwiązanie najtrudniejszej początkowej konfiguracji Godzin szczytu.

Po uogólnieniu, tak aby można go było rozgrywać na dowolnie dużej planszy, problem z podjęciem decyzji, czy problem w godzinach szczytu ma rozwiązanie, jest PSPACE-complete . Dowodzi tego redukując grę grafową zwaną niedeterministyczną logiką z ograniczeniami , o której wiadomo, że jest kompletna w PSPACE, do uogólnionych pozycji w godzinach szczytu. W 2005 roku Tromp i Cilibrasi wykazali, że Godziny szczytu są nadal kompletne w PSPACE, gdy samochody mają tylko rozmiar 2. Przypuszczali również, że godziny szczytu nadal nie są trywialne, gdy samochody mają tylko rozmiar 1.

Najtrudniejsze konfiguracje

Wykazano, że najtrudniejsza możliwa konfiguracja początkowa obejmuje 93 kroki. Najkrótsze rozwiązanie widać po prawej stronie. Jeśli policzysz niezbędne ruchy zamiast kroków, najtrudniejsza konfiguracja początkowa w tym sensie wymaga 51 ruchów.

Zobacz też

Łamigłówki kombinowane
Łamigłówki mechaniczne
Klotski (lub chiński: Huarong Dao), podobna układanka z przesuwanymi klockami
Zablokowana (gra wideo) : mobilna gra wideo z 2009 r. oparta na godzinach szczytu.

^ „Oficjalna strona edycji Deluxe w godzinach szczytu” . Pomyśl Zabawa . Źródło 2019-09-24 .
^ „Oficjalne archiwum strony w godzinach szczytu” . 2011-07-09. Zarchiwizowane od oryginału w dniu 2011-07-09 . Źródło 2019-09-24 .
^ Gary Płatek i Eric Baum (2002). „Godziny szczytu są PSPACE-kompletne, czyli dlaczego powinieneś hojnie dawać napiwki pracownikom parkingu” . Informatyka teoretyczna . 270 (1–2): 895–911. doi : 10.1016/S0304-3975(01)00173-6 .
Bibliografia _ Rudy Cilibrasi (2005). „Granice złożoności logiki godzin szczytu”. arXiv : cs/0502068 .
^ Collette, Sebastien; Raskin, Jean-françois; Servais, Frédéric (maj 2006). „O symbolicznym obliczeniu najtrudniejszych konfiguracji gry GODZINY SZCZYTU”. Komputery i gry: 5. Międzynarodowa Konferencja, CG 2006, Turyn, Włochy, 29–31 maja 2006 r. Artykuły poprawione . Notatki z wykładów z informatyki. Turyn, Włochy. 4630 : 220–233. CiteSeerX 10.1.1.91.3487 . doi : 10.1007/978-3-540-75538-8_20 . ISBN 978-3-540-75537-1 .
^ Michael Fogleman (lipiec 2018). „Rozwiązywanie godzin szczytu, układanki” . Jak stworzyłem bazę danych wszystkich ciekawych konfiguracji Godzin Szczytu.

[1] „Oficjalna strona edycji Deluxe w godzinach szczytu” . Pomyśl Zabawa . Źródło 2019-09-24 .

[2] „Oficjalne archiwum strony w godzinach szczytu” . 2011-07-09. Zarchiwizowane od oryginału w dniu 2011-07-09 . Źródło 2019-09-24 .

[3] Gary Płatek i Eric Baum (2002). „Godziny szczytu są PSPACE-kompletne, czyli dlaczego powinieneś hojnie dawać napiwki pracownikom parkingu” . Informatyka teoretyczna . 270 (1–2): 895–911. doi : 10.1016/S0304-3975(01)00173-6 .

[4] Bibliografia _ Rudy Cilibrasi (2005). „Granice złożoności logiki godzin szczytu”. arXiv : cs/0502068 .

[5] Collette, Sebastien; Raskin, Jean-françois; Servais, Frédéric (maj 2006). „O symbolicznym obliczeniu najtrudniejszych konfiguracji gry GODZINY SZCZYTU”. Komputery i gry: 5. Międzynarodowa Konferencja, CG 2006, Turyn, Włochy, 29–31 maja 2006 r. Artykuły poprawione . Notatki z wykładów z informatyki. Turyn, Włochy. 4630 : 220–233. CiteSeerX 10.1.1.91.3487 . doi : 10.1007/978-3-540-75538-8_20 . ISBN 978-3-540-75537-1 .

[6] Michael Fogleman (lipiec 2018). „Rozwiązywanie godzin szczytu, układanki” . Jak stworzyłem bazę danych wszystkich ciekawych konfiguracji Godzin Szczytu.