Блок-пазл можно поручить решать и компьютеру. В этой статье мы покажем самый базовый способ.
Идея: начинаем с левой верхней свободной клетки
Компьютер повторяет такие шаги.
- Найти в рамке самую левую верхнюю свободную клетку (смотрим сверху вниз по строкам, в каждой слева направо).
- По очереди брать ещё не использованные фигуры, пробовать все повороты и проверять, можно ли положить их так, чтобы накрыть эту клетку.
- Если положить удалось, перейти к следующей свободной клетке (вернуться к шагу 1).
- Если ни одну фигуру положить нельзя, убрать фигуру, положенную перед этим, и попробовать следующий вариант.
- Когда свободных клеток не осталось, ответ найден.
Самая левая верхняя свободная клетка непременно будет накрыта левой верхней клеткой какой-то фигуры. Поэтому достаточно пробовать только такие положения, где левая верхняя клетка фигуры совпадает с ней, а остальные места пробовать не нужно.
На схеме выше после первой фигуры самая левая верхняя свободная клетка — 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 пентамино — в статье ответы для пентамино.
