«Час Пик»

Мы, надо признаться, головоломки недолюбливаем. В детстве у нас была игра «15», которая быстро оказалась тривиальной, а потому скучной, и похожая на нее головоломка «Осел», которая была нам не по зубам, и от этого не менее скучной. Кубик Рубика мы собирали посредством разбирания его на составные части и составления их затем в правильном порядке. От остальных головоломок, которые нам время от времени дарили разные дяди и тети, не осталось даже воспоминания.

А между тем, отдельные представители головоломного жанра очень даже неплохи. Вот, например, довольно мало известная «Час Пик» (Rush Hour), которую в далеком 1996 году изобрел японец Ноб Йошигахара (Nob Yoshigahara) — известный спец по головоломкам, автор десятков книг и изобретений. «Час Пик» — поистине гениальная штука, потому что она, во-первых, до смешного проста, а во-вторых, чрезвычайно сложна. Не волнуйтесь, сейчас поясним.

Головоломка представляет собой квадратное поле 6 на 6 клеточек, в котором стоят машинки, образуя солидную пробку. Машинки бывают двух видов: двухклеточные и трехклеточные, но все могут двигаться только вперед или назад. Задача состоит в том, чтобы, передвигая автомобили, вывести красную машинку за пределы поля через единственные «ворота» в правой грани. Как видите, правила достаточно просты. Прелесть головоломки заключается в том, что если машинки расставлены с умом, то ее решение может быть весьма нетривиальным. Если есть время, можете попробовать свои силы в Java-версии. Уровень «эксперт» занял у разных сотрудников редакции от двух до пятидесяти трех минут, причем минимальное число ходов у нас в итоге получилось 46.

•	Довольно сложная задачка.

Неожиданные трудности, возникающие при решении некоторых вариантов «Часа Пик», наводят на вопрос: а какова компьютерная сложность этой задачи? Иначе говоря, предположим, что мы хотим написать программу, которая по исходной позиции определяла бы, возожно ли в принципе решение; спрашивается, какова трудоемкость такого алгоритма? Этот вопрос недавно тщательно изучили двое парней из Принстона — Гари Флейк и Эрик Баум (Gary Flake, Eric Baum). Их статья под названием «Головоломка «Час Пик» PSPACE-полна, или почему нужно щедро давать на чай работникам авто-стоянки» выложена на всеобщее обозрение, но доступна для понимания разве что студентам computer science. Последним, кстати, рекомендуем вникнуть.

Вкратце суть в следующем. С помощью довольно хитрых построений из машинок «Часа Пик» удается построить некоторое подобие логических элементов И и ИЛИ. Каждый из них требует пары дюжин машинок, но принципиально это возможно. Следовательно, можно свести известную задачу о выполнимости булевых формул (SAT) к задаче о разрешимости этой головоломки, то есть последняя оказывается NP-трудна. Попросту говоря, это означает, что она очень трудна и требует для достаточно больших полей зверских вычислений. Что в корне отличает «Час Пик» от других игр со столь же простыми правилами.

Более того, с помощью подобных рассуждений можно показать, что из часпиковских машинок можно сконструировать полноценный компьютер. И действительно, от элементов AND и OR до процессора не так уж и далеко.

•	Логический элемент OR из машинок.

А теперь смотрите, что получается. Rush Hour невероятно актуальна — каждый, кто имеет опыт парковки в Москве или Нью-Йорке, понимает, о чем идет речь. Если наблюдать сверху, то ситуация на асфальтовом пятачке вполне может напоминать позицию из «Часа Пик». Таким образом, весь Нью-Йорк в часы пик есть не что иное, как одна огромная головоломка Rush Hour, которая, как оказалось, есть не что иное, как компьютер.

Нам страшно интересно: какие вычисления постоянно идут таким образом в Нью-Йорке? Мы не удивимся, если окажется, что крупнейшие мегаполисы мира — это сеть распределенных вычислений какого-нибудь высшего разума.