Файл: Think likea programmer.pdf

22 Глава 1
рацию, просто создав список действий. Вместо этого нам следует попы- таться сделать операции шаблонными, или параметризованными.
1. Операция: Переплыть на лодке с одного берега на другой.
2. Операция: Если лодка пуста, то загрузить в нее один объект с берега.
3. Операция: Если лодка не пуста, то разгрузить с нее один объект на берег.
Обдумав задачу в наиболее общих терминах, второй список дей- ствий позволит нам решить проблему без необходимости догады- ваться, что можно перевезти гуся обратно на ближний берег. Если мы сгенерируем все возможные последовательности действий, при этом прекращая выполнение каждой последовательности, когда она нарушает одно из ограничений или приводит к конфигурации, ко- торую мы видели ранее, то в конце концов мы составим последова- тельность, изображенную на рис. 1.3, и решим задачу. Мы сможем обойти имманентную сложность этой головоломки, переформули- руя ограничения и операции.
Вынесенные уроки
Какой урок можно вынести из примера с лисицей, гусем и кукурузой?
Переустановка задачи более формальным языком — это отличная техника получения выводов, позволяющих решить эту задачу. Многие программисты обращаются к коллегам для обсуждения той или иной задачи не только потому, что коллеги могут иметь решение, но и пото- му, что озвучивание задачи зачастую наводит на новые полезные мыс- ли. Переустановка задачи аналогична обсуждению этой задачи с дру- гим программистом, с той лишь разницей, что вы играете обе роли.
Более широкий урок в том, что обдумывание задачи может быть столь же, а в некоторых случаях более продуктивным, чем обдумыва- ние решения задачи. Во многих случаях правильный подход к реше- нию — это и есть решение.
Головоломки со скользящими плитками
Размеры головоломок со скользящими плитками могут быть разны- ми, что, как вы увидите позднее, влияет на конкретный механизм ре- шения. Нижеследующее описание подходит для версии головолом- ки размером 3
*
3.
: ! "
В сетке 3
x
3 расположено восемь плиток, пронумерованных от 1 до 8, и одна пустая ячейка. Изначально плитки в сетке находятся в случайной последовательности. Плитка может быть передвинута на примыкающую пустую клетку, освободив тем самым клетку под собой. Цель составить плитки по порядку, причем плитка с цифрой 1 должна на- ходиться в верхнем левом углу.

Стратегии решения задач 23
Цель этой задачи проиллюстрирована на рис. 1.4. Если вы ни- когда не разгадывали подобную головоломку, то сейчас самое время это сделать. В Интернете можно найти большое количество симу- ляторов, но для наших целей будет лучше, если вы воспользуетесь игральными картами или же пронумеруете карточки, чтобы сделать собственный игральный набор. На рис. 1.5 показан пример началь- ной конфигурации.
Рис. 1.4. Целевая конфигурация восьмиплиточной версии головоломки со скользящими
плитками. Квадрат без цифры — это пустая ячейка, в которую может быть перенесена при-
мыкающая плитка
Рис. 1.5. Пример начальной конфигурации для головоломки со скользящими плитками
Эта головоломка довольно сильно отличается от головоломки с лисицей, гусем и кукурузой. Сложность прошлой задачи была в оставленной без внимания одной возможной операции. В данном же случае этого не происходит. Для любой заданной конфигурации максимум четыре плитки могут примыкать к пустой ячейке — и лю- бая из этих плиток может быть передвинута в пустую ячейку. Это полностью перечисляет все возможные операции.
Источник сложности этой задачи — необходимость создания длинной цепочки операций. Последовательность операций мо- жет передвинуть часть плиток в правильную окончательную пози- цию, сдвигая при этом другие плитки с их правильных позиций, или же последовательность может передвинуть часть плиток бли- же к верным позициям, сдвинув при этом часть плиток дальше от верных позиций. Из-за этого сложно сказать, будет ли резуль- татом выполнения той или иной операции продвижение к цели.
Не имея возможности оценить прогресс, сложно сформулиро- вать стратегию. Многие из тех, кто пытается решить головолом- ку с плитками, просто в случайном порядке передвигают плитки

24 Глава 1
в надежде выйти на конфигурацию, из которой будет виден путь к цели.
Тем не менее существуют стратегии решения головоломок с плит- ками. Для иллюстрации одного из подходов давайте рассмотрим го- ловоломку с меньшей и при этом прямоугольной, а не квадрат ной сеткой.
: !
В сетке 2
x
3 расположено пять плиток, пронумерованных от 4 до 8, и одна пустая клет- ка. Изначально плитки в сетке находятся в случайной последовательности. Плитка мо- жет быть передвинута в примыкающую пустую ячейку, освободив тем самым клетку под собой. Цель составить плитки по порядку, причем плитка с цифрой 4 должна на- ходиться в верхнем левом углу.
Вы могли обратить внимание, что наши пять плиток пронуме- рованы от 4 до 8, а не от 1 до 5. Причины этого будут понятны чуть позже.
Несмотря на то, что это такая же базовая задача, как и сколь- зящая восьмерка, из-за того, что плиток всего пять, ее проще ре- шить. Попробуйте конфигурацию, изображенную на рис. 1.6.
Рис. 1.6. Пример начальной конфигурации для уменьшенной головоломки со скользящими
плитками 2x3
Если вы поиграете с плитками на протяжении нескольких ми- нут, то вы, возможно, найдете решение. Я довольно быстро научил- ся, играя с малым количеством плиток. Именно этот навык, вместе с наблюдением, которое мы вскоре обсудим, я использую для решения всех головоломок с плитками.
Я называю мою технику кортеж. Она основана на наблюдении, что схема позиций плиток с пустой ячейкой составляет кортеж — ве- реницу плиток, — которая может перемещаться по схеме, сохраняя при этом относительную упорядоченность плиток. На рис. 1.7 пока- зан наименьший возможный кортеж с четырьмя позициями. Из на- чальной конфигурации плитка 1 может передвинуться в пустую ячей- ку, плитка 2 может передвинуться на место, освобожденное плиткой
1, и, наконец, плитка 3 может передвинуться на место, освобожден- ное плиткой 2. Такая последовательность оставляет пустую ячейку примыкать к плитке 1, что позволяет кортежу продолжать движе- ние, и таким образом плитки могут быть двигаться по пути переме- щения кортежа.

Стратегии решения задач 25
Рис. 1.7. «Кортеж» — путь плиток, который начинается от плитки, примыкающей к пустому
квадрату, и скользящий по полю головоломки как кортеж из автомобилей.
Используя кортеж, мы можем перемещать наборы плиток, со- храняя при этом их взаимное расположение. Теперь давайте вер- немся к предыдущей конфигурации с сеткой 2
x
3. Несмотря на то, что ни одна из плиток не находится в правильной финальной по- зиции, некоторые из плиток примыкают к плиткам, рядом с кото- рыми они должны находиться в финальной конфигурации. Напри- мер, в финальной конфигурации плитка 4 будет над плиткой 7, и в данный момент эти плитки смежные. Как показано на рис. 1.8, мы можем использовать шестипозиционный кортеж для того, чтобы пе- редвинуть плитки 4 и 7 на правильные позиции. Когда мы сделаем это, оставшиеся плитки займут почти что правильные позиции, нам останется лишь придвинуть плитку 8.
Рис. 1.8. Из конфигурации 1 две ротации вдоль выделенного «пути» приведут нас к конфигу-
рации 2. Оттуда движение одной плитки приведет нас к цели, конфигурации 3.
Итак, каким же образом эта единственная техника позволяет нам решить любую головоломку с плитками? Рассмотрим нашу ис- ходную конфигурацию 3
x
3. Мы можем использовать шестипозици- онный кортеж для переноса смежных плиток 1 и 2 так, что плитки
2 и 3 станут смежными, как показано на рис. 1.9.
Рис. 1.9. Из конфигурации 1 плитки перемещаются вдоль выделенного «пути» и приходят
к конфигурации 2.
Это действие сделало плитки 1, 2 и 3 смежными. Имея восьми- позиционный кортеж, мы можем переместить плитки 1, 2 и 3 так,

26 Глава 1
чтобы они оказались в правильных финальных позициях, как пока- зано на рис. 1.10.
Рис. 1.10. Из конфигурации 1 плитки перемещаются вдоль выделенного «пути» и приходят к
конфигурации 2, в которой оказываются в правильных финальных позициях
Обратите внимание на положение плиток 4–8. Эти плитки нахо- дятся в конфигурации, которую мы ранее задали для сетки 2
*
3, — и это ключевой момент. Поместив плитки 1–3 в правильные позиции, мы теперь можем решить оставшуюся сетку, как отдельную, мень- шую и менее сложную задачу. Обратите внимание, чтобы данный метод сработал, нам нужно решить полностью либо столбец, либо строку; если бы мы передвинули плитки 1 и 2 в правильные позиции, а плитка 3 все еще находилась не на своем месте, то мы бы не смогли ничего передвинуть в правый верхний угол, не смещая одну или обе плитки верхнего ряда.
Эта же техника может использоваться для решения головоломок со скользящими плитками большего размера. Самая популярная голо- воломка насчитывает 15 плиток в сетке 4
*
4. Она может быть решена поэтапно. Для начала нужно перенести плитки 1–4 в правильные по- зиции, оставив сетку 3
*
4. Далее мы составим плитки самой левой ко- лонки — и получим сетку 3
*
3. К этому моменту задача уменьшится и сведется к загадке с 8 плитками.
Вынесенные уроки
Какие уроки мы можем вынести из головоломок со скользящими плитками?
Количество движений плиток достаточно велико, поэтому сложно или вовсе невозможно заранее спланировать полноцен- ное решение головоломки из начальной конфигурации. Однако не- возможность спланировать полноценное решение не мешает нам составлять стратегии или использовать различные техники для систематичного решения головоломки. При решении задач про- граммирования мы иногда сталкиваемся с такими ситуациями, ког- да невозможно увидеть четкий путь написания программного кода, необходимого для решения. Однако мы не должны использовать это как оправдание отказа от планирования и системного подхода.
Лучше разработать стратегию, чем атаковать задачу методом проб и ошибок.

Стратегии решения задач 27
Я разработал свою технику с «кортежем», играя с маленькой го- ловоломкой. Зачастую я использую эту же технику и в программи- ровании. Столкнувшись со сложной задачей, я экспериментирую с уменьшенной версией этой задачи. Эти эксперименты часто приво- дят к ценным ноу-хау.
Еще один урок в том, что иногда задачи можно разделить неви- димыми изначально способами. Так как перемещение плитки влия- ет не только на эту плитку, но также на возможные следующие ходы, кому-то может показаться, что такая головоломка должна решаться за один шаг, а не постепенно. Поиск способа решить задачу, как пра- вило, занимает значительное количество времени. Даже если вы не можете найти четкого разделения, вы можете узнать нечто такое, что поможет вам решить эту задачу. При решении задачи всегда луч- ше работать с определенной целью в уме, нежели предпринимать случайные попытки, вне зависимости от того, удается вам достичь этих конкретных целей или нет.

28 Глава 1
Головоломки «Судоку» могут иметь разный уровень сложности, который определяется количеством пустых клеток. По этой клас- сификации, приведенный вариант — очень легкая головоломка. Так как 36 клеток уже пронумеровано, нам осталось заполнить лишь 45.
Вопрос, какие клетки нам следует заполнить первыми?
Помните об ограничениях этой головоломки. Каждая из девяти цифр должна появиться один раз в каждой строке, в каждой колонке и в каждой области 3
*
3, обозначенной жирной границей. Эти прави- ла указывают нам, где мы должны начинать наши попытки. Область в центре головоломки уже содержит восемь из девяти цифр, таким об- разом, существует только одно возможное значение пустой клетки в центре, значение, не представленное в других клетках области 3
*
3.
Именно здесь мы должны начать решение этой головоломки. Пропу- щенное число в этой области — 7, а, значит, мы можем вписать его в центральную клетку.
Вписав это значение, обратите внимание, что в центральной ко- лонке теперь есть семь из девяти значений клеток, таким образом, нам осталось лишь заполнить две клетки, при этом в этих клетках должны быть значения, еще не представленные в этой колонке. Два недостающих числа — это 3 и 9. Ограничение для этой колонки позво- лит нам вписать любое число в любую клетку, однако обратите вни- мание, что в третьей строке уже есть число 3, а в седьмой строке есть число 9. Таким образом, ограничения строк говорят нам, что число 9 нужно вписать в среднюю колонку третьей строки, а число 3 — в сред- нюю колонку седьмой строки. Эти шаги резюмированы на рис. 1.12.
Рис. 1.12. Первые шаги решения примера головоломки «Судоку»
Я не буду решать всю головоломку, но эти первые шаги уже по- казывают важный момент: мы ищем клетки с наименьшим количе- ством вариантов возможных значений, в идеале — только с одним.
Вынесенные уроки
Основной урок из головоломки «Судоку» заключается в том, что следу- ет искать наиболее ограниченную часть задачи. Несмотря на то, что ограничения — это то, что делает задачу сложной (вспомните про ли- сицу, гуся и кукурузу), они также могут упростить процесс обдумыва- ния решения благодаря уменьшению количество вариантов.

Стратегии решения задач 29
Хотя в этой книге мы не будем обсуждать искусственный интел- лект, в нем существует правило решения подобных задач, называется оно «наиболее ограниченная переменная». Это значит, что при реше- нии задачи, где вы пытаетесь присвоить различные значения раз- личным переменным, для соответствия ограничениям, вам следует начать с переменной, на которую наложено наибольшее количество ограничений или иными словами — переменной с наименьшим вари- антом возможных значений.
Вот пример такого образа мышления. Предположим, что не- сколько коллег хотят вместе сходить на обед и попросили вас найти ресторан, который придется по вкусу каждому. Проблема в том, что каждый из коллег накладывает определенные ограничения на груп- повое решение: Пэм вегетарианка, Тодд не любит китайскую кухню и так далее. Если ваша цель — минимизировать время, которое по- требуется для поиска ресторана, то вам нужно начать с коллеги с наиболее жесткими ограничениями. Если у Боба аллергия на боль- шое количество продуктов, то логичнее всего было бы начать с выяс- нения списка ресторанов, в которых он знает, что сможет поесть, а не с Тодда, нелюбовь к китайской еде которого может запросто быть подавлена.
Такая же техника может использоваться и при решении задач по программированию. Если на некую часть задачи возложено большое количество ограничений, значит, это отличный отправной пункт, потому что вы можете продвигаться вперед без опасения, что тра- тите время на работу, которая впоследствии будет отменена. Свя- занный с этим вывод — вы должны начинать с наиболее очевидной части. Если вы можете решить часть задачи — смело приступайте и делайте, что сможете. Изучив собственный код, вы можете увидеть нечто такое, что подстегнет ваше воображение, и вы сможете ре- шить оставшуюся часть задачи.
Замóк Кварраси
Возможно, вы уже встречали предыдущие головоломки ранее, но вы не должны знать о последней головоломке этой главы, если не читали данную книгу, так как я придумал эту задачу сам. Будьте внимательны, так как описание задачи может показаться несколько сложным.
: # # $ " ó
Враждебная инопланетная раса Кварраси совершила высадку на Земле, и вы были захва- чены. Вы смогли победить своих охранников, несмотря на то, что они огромные и с боль- шим количеством конечностей, однако, чтобы сбежать из (все еще находящегося на Земле) космического корабля, вы должны открыть массивную дверь. Как ни странно, инструкции по открытию двери написаны на английском, но это лишь незначительно упрощает задачу.
Чтобы открыть дверь вы должны передвинуть три бруска Кратцца вдоль полозьев от право- го рецептора к левому, находящемуся на краю двери, примерно в 3 метрах от вас.