Блок-пазл можно поручить решать и компьютеру. В этой статье мы покажем самый базовый способ.

Идея: начинаем с левой верхней свободной клетки

Компьютер повторяет такие шаги.

  1. Найти в рамке самую левую верхнюю свободную клетку (смотрим сверху вниз по строкам, в каждой слева направо).
  2. По очереди брать ещё не использованные фигуры, пробовать все повороты и проверять, можно ли положить их так, чтобы накрыть эту клетку.
  3. Если положить удалось, перейти к следующей свободной клетке (вернуться к шагу 1).
  4. Если ни одну фигуру положить нельзя, убрать фигуру, положенную перед этим, и попробовать следующий вариант.
  5. Когда свободных клеток не осталось, ответ найден.

Самая левая верхняя свободная клетка непременно будет накрыта левой верхней клеткой какой-то фигуры. Поэтому достаточно пробовать только такие положения, где левая верхняя клетка фигуры совпадает с ней, а остальные места пробовать не нужно.

На схеме выше после первой фигуры самая левая верхняя свободная клетка — 2-я строка, 1-й столбец (золотое кольцо). Дальше пробуем только способы накрыть именно эту клетку.

Такой способ поиска, когда идут вперёд, пока можно, а если нельзя, возвращаются и пробуют другой путь, называется поиском в глубину (бэктрекингом).

Код на JavaScript

Рамка — это таблица из true (свободно) и false (занято), а фигура — набор клеток [строка, столбец]. Клетки фигуры расположены сверху вниз, а в каждой строке слева направо.

// Рамка: true — свободная клетка. Фигура: набор клеток [строка, столбец]
function rotate(shape) {
  const turned = shape.map(([r, c]) => [c, -r]);
  const minR = Math.min(...turned.map(([r]) => r));
  const minC = Math.min(...turned.map(([, c]) => c));
  return turned
    .map(([r, c]) => [r - minR, c - minC])
    .sort((a, b) => a[0] - b[0] || a[1] - b[1]);
}

function solve(frame, pieces) {
  const rows = frame.length;
  const cols = frame[0].length;
  const used = pieces.map(() => false);
  let count = 0;

  function search() {
    // Ищем самую левую верхнюю свободную клетку
    let at = -1;
    for (let i = 0; i < rows * cols && at < 0; i++) {
      if (frame[Math.floor(i / cols)][i % cols]) at = i;
    }
    if (at < 0) {
      count++; // Всё заполнено
      return;
    }
    const r0 = Math.floor(at / cols);
    const c0 = at % cols;
    pieces.forEach((piece, p) => {
      if (used[p]) return;
      let shape = piece;
      const seen = new Set();
      for (let turn = 0; turn < 4; turn++, shape = rotate(shape)) {
        const key = JSON.stringify(shape);
        if (seen.has(key)) continue;
        seen.add(key);
        // Совмещаем левую верхнюю клетку фигуры со свободной клеткой
        const [dr, dc] = shape[0];
        const cells = shape.map(([r, c]) => [r - dr + r0, c - dc + c0]);
        const fits = cells.every(
          ([r, c]) => r >= 0 && r < rows && c >= 0 && c < cols && frame[r][c]
        );
        if (!fits) continue;
        cells.forEach(([r, c]) => (frame[r][c] = false));
        used[p] = true;
        search();
        used[p] = false;
        cells.forEach(([r, c]) => (frame[r][c] = true));
      }
    });
  }

  search();
  return count;
}

Если передать в solve рамку 4×5 и 5 фигур — P, T, L, S и L из 3 клеток, — вернётся 8. Это значит, что у примера из статьи о решении с учётом поворотов 8 ответов.

Приём: возвращаться пораньше

Код выше идёт вперёд, пока фигуры можно класть. Но уже в тот момент, когда образуется маленькая запертая пустота, понятно, что дальше ответа не будет.

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

Когда мы считали все ответы для укладки 12 пентамино в прямоугольник 3×20, до добавления этого приёма расчёт не заканчивался и за 10 минут. С приёмом он закончился примерно за 6 секунд (это расчёт, сделанный при написании статей этого сайта; время зависит от компьютера).

Как устроена «Подсказка» в приложении

«Подсказка» в приложении «Блок-пазл» тоже использует такой же поиск в глубину.

  • Пробуются только способы накрыть свободную клетку с наименьшим номером.
  • Из фигур одной формы, совпадающих при повороте, пробуется только одна.
  • Если образуется запертая пустота меньше фигуры, происходит возврат.
  • Число просматриваемых позиций ограничено, чтобы не тратить слишком много времени.

Если рамку можно заполнить до конца при нынешней расстановке, подсвечиваются фигура и способ её положить, закрывающие самую труднозаполнимую свободную клетку. Если до конца заполнить нельзя, подсвечиваются фигуры, не совпадающие с изначально созданным ответом, и появляется сообщение «Уберите светящуюся фигуру, чтобы вернуться на верный путь».

О том, как создаются задачи, рассказано в статье как создаются всегда решаемые задачи, а о числе ответов для 12 пентамино — в статье ответы для пентамино.