Час пик (головоломка) - Rush Hour (puzzle)

В Час пик набор пазлов

Час пик это раздвижной блок головоломки изобретен Ноб Йошигахара в 1970-е гг. Впервые он был продан в Соединенные Штаты в 1996 году. Сейчас его производит ThinkFun (ранее Binary Arts).

ThinkFun теперь продает Час пик побочные продукты Час пик младший, Час пик сафари, Железнодорожный час пик, Час пик Brain Fitness и Смена в час пик, с головоломками Скотт Ким.

Игра

Обычное издание включает 40 головоломок в 1, разделенных на 4 различных уровня сложности, от новичка до эксперта. В Deluxe Edition есть черная игровая доска, картонная коробка вместо лотка для карт и 60 новых головоломок с дополнительной сложностью: Великий Мастер, который сложнее, чем Эксперт.[1]. В Ultimate Collector's Edition также есть черное игровое поле, на котором можно разместить неигровые автомобили, и новый способ отображения текущей активной карты на рекламном щите, таком как дисплей. Ultimate Collectors Edition также включает в себя 155 новых головоломок (некоторые из них из набора карт 3) и белый лимузин. Обычная версия включает дорожную сумку. Также доступны дополнительные наборы карточек-головоломок (в дополнение к 40, 60 или 155 картам, включенным в игру). Также как Deluxe Edition, так и Ultimate Collector's Edition поставляются со всеми новыми блестящими вариантами транспортных средств, причем Ultimate Collector's Edition немного изменен по дизайну. Затем, в 2011 году, доска была изменена на черную, как и в Deluxe Edition, но с лотком для карт, и карты также были изменены, чтобы иметь новые уровни и дизайн, соответствующий новому цвету доски.[2].

Описание

Доска представляет собой сетку 6x6 с канавками в плитках, позволяющих машинам скользить, лоток для карт, в котором держатся карты, текущий активный держатель карты и отверстие для выхода. В игре есть 16 транспортных средств (12 автомобилей, 4 грузовика), каждый разного цвета, и 40 карточек-головоломок. Легковые и грузовые автомобили имеют ширину в один квадрат, но автомобили имеют длину два квадрата, а грузовики - три квадрата. Транспортные средства можно перемещать только по прямой линии на сетке; вращение запрещено. Карточки головоломок, каждая с номером уровня, который указывает на сложность задачи, показывают стартовые позиции автомобилей и грузовиков. Не все автомобили и грузовики используются для решения всех задач.

Задача

Цель игры - вывести только красную машину через выход с доски, убрав другие машины с ее пути. Однако автомобили и грузовики (установленные перед игрой, согласно карточке головоломки) преграждают путь, что делает головоломку еще более сложной.

Расширения

Были выпущены три официальных дополнения, названных «дополнительными пакетами»: набор карт 2, в который входит красный спортивный автомобиль, занимающий 2 квадрата; Набор карт 3, в который входит белый лимузин, занимающий 3 квадрата; и Набор карточек 4, в который входит такси, занимающее 2 квадрата. В каждом наборе также есть 40 новых эксклюзивных испытаний - от среднего уровня до великого мастера, - в которых используются новые машины вместо (или в дополнение к) красной машины. Кроме того, все три пакета расширения будут работать со всеми тремя выпусками игры: Regular Edition, Deluxe Edition и Ultimate Collector's Edition. Кроме того, как и в обычном выпуске игры 2011 года, карты всех трех расширений также были изменены, чтобы иметь новые уровни и дизайн, чтобы соответствовать новому цвету игрового поля обычного издания.

An iOS Версия игры вышла в 2010 году.

Вычислительная сложность на больших платах

Минимальное решение самой сложной начальной конфигурации в час пик.

Когда обобщенный так что в нее можно играть на сколь угодно большой доске, проблема определения того, Час пик проблема имеет решение PSPACE-полный.[3] Это доказывается сокращением графовой игры, называемой недетерминированная логика ограничений, который известен как PSPACE-complete, до обобщенных позиций в час пик. В 2005 году Тромп и Чилибрази [4] показало, что Час пик все еще PSPACE-завершен, когда автомобили только 2-го размера. Они также предположили, что Час пик все еще нетривиально, когда автомобили только 1-го размера.

Самые сложные конфигурации

Было показано, что самая сложная начальная конфигурация состоит из 93 шагов. Кратчайшее решение можно увидеть справа.[5]Если вместо шагов считать нужные ходы, то самая сложная стартовая конфигурация в этом смысле требует 51 ход.[6]

Смотрите также

использованная литература

  1. ^ «Официальная страница Deluxe Edition в час пик». ThinkFun. Получено 2019-09-24.
  2. ^ "Официальный архив страницы в час пик". 2011-07-09. В архиве из оригинала 2011-07-09. Получено 2019-09-24.
  3. ^ Гэри Флейк и Эрик Баум (2002). «Час пик полностью подготовлен для PSPACE, или почему вам следует давать щедрые чаевые парковщикам». Теоретическая информатика. 270 (1–2): 895–911. Дои:10.1016 / S0304-3975 (01) 00173-6.
  4. ^ Джон Тромп; Руди Силибрази (2005). «Пределы сложности логики в час пик». arXiv:cs / 0502068.
  5. ^ Коллетт, Себастьян; Раскин, Жан-Франсуа; Серве, Фредерик (май 2006 г.). «О символическом вычислении сложнейших конфигураций игры RUSH HOUR». Компьютеры и игры: 5-я Международная конференция, CG 2006, Турин, Италия, 29-31 мая 2006 г. Пересмотренные документы. Конспект лекций по информатике. Турин, Италия. 4630: 220–233. CiteSeerX  10.1.1.91.3487. Дои:10.1007/978-3-540-75538-8_20. ISBN  978-3-540-75537-1.
  6. ^ Майкл Фоглеман (июль 2018 г.). «Решение головоломки в час пик». Как я создал базу данных всех интересных конфигураций в час пик.