Однажды утром Грейди заходит в офис и оставляет пару деревянных пазлов на общем столе в зоне группы управления данными. Многих из нас в тот день зарезали. Это история о том, как одна-единственная головоломка расстроила разработчиков, архитекторов программного обеспечения и даже технического директора.

Головоломка Калиброн 12 названа по количеству деталей (двенадцать). Инструкция гласит:

Поместите все части в большое отверстие. Очень сложная головоломка, придуманная в 1933 году Теодором Эдисоном, сыном изобретателя Томаса Эдисона.

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

Ботаника убивают каждые 42 минуты. Пожалуйста, подумайте о ботаниках

В течение дня люди приходили, чтобы попробовать его, и неизбежно сдавались. Это очень сложная головоломка, и в ней есть несколько гнусных элементов. Например, некоторые части отличаются по своим размерам всего на 1 единицу (создатели были достаточно любезны, чтобы пометить размеры каждой части). Есть как 28*7 шт, так и 28*6 шт. Есть и 32*10 и 32*11 шт. Есть и дубликаты: две 21*18 и две 21*14 штуки!

К концу первого дня кто-то в офисе измерил размер доски 56*56 кв. Заметив, что 56 кратно 7, Пэт подумал о том, чтобы сгруппировать части по длине их сторон по модулю 7. Шери независимо друг от друга попробовала сгруппировать длины сторон по четным и нечетным значениям. Ни одна из стратегий, похоже, не помогла. Позже я понял почему — есть 668 способов получить 56, выбрав не более одной стороны из каждой части!

Я пытался проникнуть в сознание создателя. «Если бы я был Теодором Эдисоном, как бы я разбил квадрат на более мелкие прямоугольники?» Несколько набросков на доске показали, что легче иметь прямоугольники меньшего размера внутри, чем снаружи. У нас также было предчувствие, что большинство частей будут располагаться в шахматном порядке, т. е. части никогда не будут образовывать неполный прямоугольник в окончательном решении. Одна из этих догадок была бы верной.

В какой-то момент вокруг головоломки столпилось нас трое. Пока Майк пытался разместить фигуры на доске, я записал размеры всех фигур на каталожную карточку. Я надеялся решить ее «офлайн» — без физических частей. Они здесь:

  • 21 * 18 (2)
  • 21 * 14 (2)
  • 28 * 14
  • 17 * 14
  • 4 * 14
  • 7 * 10
  • 32 * 10
  • 32 * 11
  • 28 * 6
  • 28 * 7

Цель: Из этих частей сделать квадрат 56*56.

Если ничего не помогает, грубая сила

В какой-то момент каждый программист неизбежно думает: «А как насчет того, чтобы просто написать программу для ее решения?» Первое, что приходит на ум, — поиск методом грубой силы. Мы называем это грубой силой, когда программа просто пробует каждую возможность без какой-либо стратегии. Грубая сила глупа и медленна, но она может работать, если количество возможностей достаточно мало. И это работает только потому, что компьютеры довольно быстро справляются с ошеломляюще повторяющимися задачами.

Программы грубой силы действительно легко писать! Если у вас есть 3 вещи (i, j, k), каждая из которых имеет набор возможных значений на выбор, проверка всех возможных комбинаций — это просто тройной вложенный цикл for, например:

for i in i_values:
   for j in j_values:
      for k in k_values:
         test(i, j, k) // does (i, j, k) work?

Но надо быть осторожным — количество комбинаций комбинаторное (очевидное предложение очевидно). Приведенный выше код выполняется за n³ времени. Почему? Если бы у каждой из наших трех переменных было 10 значений на выбор, было бы 10³ комбинаций. Если бы у каждого из них было по 100 значений, было бы 100³. Если бы у нас было 12 переменных (скажем, для определенной головоломки из 12 частей…) с n возможными значениями каждая, было бы n¹² комбинаций! Это становится большим быстро.

Вернемся к нашей головоломке. Рассмотрим эту формулировку проблемы:

  • Есть 12 частей, которые должны быть размещены.
  • Каждая часть должна быть в одной из двух ориентаций (горизонтальной или вертикальной).
  • Каждая фигура должна иметь позицию внутри квадратного отверстия (доски).
  • Определите положение фигуры (x, y) как координаты ее левого верхнего угла. Мы можем принять целочисленные координаты, потому что все части имеют целочисленные размеры. Итак, давайте ограничим x и y целыми числами от 0 до 55.

В этой формулировке каждая часть имеет 2 * 56² = 6272 пары позиция-ориентация на выбор. В одиночку, это кусок пирога для компьютера. Но с 12 частями, требующими положения и ориентации, это общее пространство для поиска

6272¹²
= 3.7 * 10⁴⁵

комбинации, чтобы попробовать! Поиск грубой силы по всем этим возможным решениям никогда не закончится. Как правило, на частоте 1 ГГц компьютеры могут выполнять 10⁹ операций в секунду, игнорируя параллелизм. Скажем, ваш компьютер работает в 10 раз быстрее, и для проверки одной комбинации требуется всего 1 цикл. Эта программа по-прежнему будет выполняться 10³⁵ секунд или 10²⁷ лет! (Для сравнения, возраст Вселенной оценивается в 13 миллиардов = 10¹⁰ лет.)

Лучшее решение — что сделал бы человек?

Приведенная выше формулировка грубой силы глупа. Конечно, вы не стали бы пробовать все позиции 56 * 56 для одного произведения. Многие из этих позиций оставляли бы промежутки неправильного размера или перекрывали бы другие уже размещенные фигуры и т. д. Грубая сила — это глупо, но мы это знали.

Если бы вы решали эту головоломку вручную, вы бы взяли кусочек и попытались поместить его рядом с краем или, что более вероятно, в один из углов. Затем вы выберете еще одну часть и поместите ее рядом с первой, и так далее.

Мы можем смоделировать это как несколько вариантов выбора на каждом этапе:

  1. Выберите кусок.
  2. Выберите ориентацию (горизонтальную или вертикальную).
  3. Поместите его в самый верхний, самый левый угол, который еще не занят.

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

Но закончатся ли эти поиски? На пустой доске у нас есть 24 варианта на выбор — 12 штук, умноженных на 2 ориентации. (Это уже намного меньше, чем 6272 выше.) На каждом последующем шаге, если осталось n штук, у нас есть 2n значений на выбор. Полное решение состоит из 12 шагов. Общее пространство для поиска:

24 * 22 * … * 2
= 2¹² * 12!
= 1,961,990,553,600

Это примерно 1,9 * 10¹² возможных комбинаций, что по-прежнему огромно, но более разумно, чем раньше. Снова есть термин n¹², но на этот раз n намного меньше. Если предположить, что в секунду тестируется 10⁹ комбинаций, это «всего» 2000 секунд или около 33 минут. Теоретически это может сработать!

Взорванная геометрия

Но ждать! Все приведенные выше расчеты предполагают, что проверка одной комбинации — это постоянное время. Мы рассмотрели, как это сделать, а также как найти «самый верхний, самый левый» угол. Если мы не будем осторожны, мы можем в конечном итоге ввести еще один фактор n², сделав что-то наивное, например перебирая массив битов 56 * 56, чтобы выяснить, полностью ли мы заполнили доску. Представьте, если бы нам приходилось выполнять 3136 операций в каждом тесте — эти 33 минуты превратились бы в 100 000 минут…

Теперь самое сложное при написании этой программы — выяснить, как эффективно выполнять геометрию. Как найти самый верхний и самый левый угол (частично заполненной) доски? И как мы определяем, войдет или не войдет кусок в этот угол? Ждите ответы на эти вопросы во второй части!

(ПРОДОЛЖЕНИЕ СЛЕДУЕТ…)

Первоначально опубликовано на https://engineering.vena.io 25 сентября 2019 г.