Введение
Rush Hour – это головоломка с передвижением блоков, изобретенная Ноб Йосигахара в 1970-х годах. Впервые она поступила в продажу в США в 1996 году. В настоящее время её производит компания ThinkFun (ранее Binary Arts). ThinkFun также продает спин-оффы Rush Hour: Rush Hour Jr., Safari Rush Hour, Railroad Rush Hour, Rush Hour Brain Fitness и Rush Hour Shift, с головоломками, разработанными Скоттом Кимом. Было продано более миллиона экземпляров игры.
Игра
Доска представляет собой игровое поле 6x6 с пазами в ячейках, позволяющими автомобилям скользить, лоток для карт, держатель текущей активной карты и выходное отверстие. В комплекте идут 16 транспортных средств (12 машин и 4 грузовика), каждое разного цвета, а также 40 карточек с головоломками. Машины и грузовики занимают один квадрат в ширину, но машины занимают два квадрата в длину, а грузовики – три квадрата. Транспортные средства могут двигаться только по прямой линии на поле; поворачивать их запрещено. На карточках с головоломками, каждая из которых имеет номер уровня, указывающий на сложность задачи, показаны начальные позиции машин и грузовиков. Не все машины и грузовики используются в каждой головоломке.
Цель
Цель игры — выкатить только красную машину через выход с игрового поля, отодвигая другие транспортные средства с её пути. Однако автомобили и грузовики (расставленные перед началом игры согласно карте головоломки) преграждают дорогу, что делает задачу еще более сложной.
Издания
Регулярное издание включает в себя сорок головоломок, разделенных на четыре уровня сложности – от начинающего до эксперта. В Deluxe Edition представлена черная игровая доска, карточная коробка вместо карточного лотка Регулярного издания и шестьдесят новых головоломок с дополнительным уровнем сложности – «Грандмастер». Ultimate Collector's Edition имеет игровую доску, на которой можно размещать неиспользуемые транспортные средства и демонстрировать активную карту, как на билборде. Ultimate Collector's Edition также включает 155 новых головоломок (в том числе некоторые из третьего набора карт) и белый лимузин. В 2011 году игровая доска была изменена на черную, как в Deluxe Edition. Версия игры для iOS вышла в 2010 году.
Расширения
Были выпущены три официальных дополнения, называемых "наборами дополнений": Card Set 2, в который входит красная спортивная машина, занимающая 2 клетки; Card Set 3, в который входит белый лимузин, занимающий 3 клетки; и Card Set 4, в который входит такси, занимающее 2 клетки. Каждый набор также содержит 40 новых эксклюзивных заданий – от среднего до уровня Гранд-мастера – которые используют новые транспортные средства вместо (или в дополнение к) красной машине. Все три набора дополнений будут совместимы со всеми изданиями игры. Кроме того, как и в Регулярном издании игры 2011 года, карты всех трех дополнений были изменены: им были присвоены новые уровни и дизайн, соответствующие новому цвету игрового поля Регулярного издания.
Комплексность вычислений на больших платах
Когда обобщается для игры на доске произвольного размера, задача определения, имеет ли головоломка Rush Hour решение, является PSPACE-полной. Это доказывается сведением графовой игры, называемой недетерминированной логикой ограничений, которая известна как PSPACE-полная, к обобщенным позициям Rush Hour. В 2005 году Тромп и Cilibrasi показали, что Rush Hour остаётся PSPACE-полной даже при размере автомобилей, равном 2. Они также предположили, что Rush Hour остаётся нетривиальной задачей даже при размере автомобилей, равном 1.
Наиболее сложные конфигурации
Было показано, что наиболее сложная начальная конфигурация требует 93 хода. Кратчайшее решение можно увидеть справа. Если считать необходимые перемещения, а не ходы, то наиболее сложная начальная конфигурация в этом случае требует 51 перемещения.