블록 맞추기는 컴퓨터에게 풀게 할 수도 있어요. 이 기사에서는 가장 기본적인 푸는 법을 소개해요.
생각법: 왼쪽 위의 빈 칸부터
컴퓨터는 다음 순서를 되풀이해요.
- 틀 안에서 가장 왼쪽 위의 빈 칸을 찾는다(위쪽 행부터, 왼쪽부터 차례로 본다).
- 아직 쓰지 않은 조각을 하나씩, 돌린 방향도 전부 시험해서 그 칸을 덮도록 놓을 수 있는지 조사한다.
- 놓을 수 있으면 다음 빈 칸으로 간다(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 틀과 P·T·L·S·3칸짜리 L의 5개 조각을 넘기면 8이 반환돼요. 푸는 법 기사의 예제에는 돌린 방향을 포함해 8가지 정답이 있다는 뜻이에요.
일찍 되돌아가는 방법
위 코드는 조각을 놓을 수 없게 될 때까지 나아가요. 하지만 갇힌 작은 빈틈이 생긴 시점에서 그 앞에 정답이 없다는 것은 알 수 있어요.
조각을 놓을 때마다 빈 칸 덩어리의 크기를 조사해서 남은 조각으로는 만들 수 없는 크기의 덩어리가 생기면 바로 되돌아가요. 이것만으로 탐색하는 수가 크게 줄어요.
12종류의 펜토미노를 3×20 직사각형에 채우는 정답을 전부 셀 때, 이 방법을 넣기 전에는 10분이 지나도 끝나지 않았어요. 방법을 넣으니 6초쯤에 끝났어요(이 사이트의 기사를 쓸 때의 계산이고, 시간은 컴퓨터에 따라 달라져요).
앱 「힌트」의 구조
앱 「블록 맞추기」의 「힌트」도 같은 깊이 우선 탐색을 쓰고 있어요.
- 번호가 가장 작은 빈 칸을 덮는 방법만 시험한다.
- 돌려서 겹치는 같은 모양의 조각은 하나만 시험한다.
- 조각보다 작게 갇힌 빈틈이 생기면 되돌아간다.
- 조사하는 상태의 수에 상한을 두어 시간이 너무 오래 걸리지 않게 한다.
지금 놓은 그대로 다 채울 수 있다면 가장 채우기 어려운 빈 칸을 덮는 조각과 놓는 방법을 빛내요. 다 채울 수 없다면 처음에 만든 정답과 비교해서 맞지 않는 조각을 빛내고 「빛나는 조각을 빼면 잘 풀려요」라고 알려 줘요.
문제 만드는 법은 반드시 풀리는 문제 만드는 법, 12종류의 펜토미노의 정답 수는 펜토미노의 정답에서 소개하고 있어요.
