블록 맞추기는 컴퓨터에게 풀게 할 수도 있어요. 이 기사에서는 가장 기본적인 푸는 법을 소개해요.

생각법: 왼쪽 위의 빈 칸부터

컴퓨터는 다음 순서를 되풀이해요.

  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 틀과 P·T·L·S·3칸짜리 L의 5개 조각을 넘기면 8이 반환돼요. 푸는 법 기사의 예제에는 돌린 방향을 포함해 8가지 정답이 있다는 뜻이에요.

일찍 되돌아가는 방법

위 코드는 조각을 놓을 수 없게 될 때까지 나아가요. 하지만 갇힌 작은 빈틈이 생긴 시점에서 그 앞에 정답이 없다는 것은 알 수 있어요.

조각을 놓을 때마다 빈 칸 덩어리의 크기를 조사해서 남은 조각으로는 만들 수 없는 크기의 덩어리가 생기면 바로 되돌아가요. 이것만으로 탐색하는 수가 크게 줄어요.

12종류의 펜토미노를 3×20 직사각형에 채우는 정답을 전부 셀 때, 이 방법을 넣기 전에는 10분이 지나도 끝나지 않았어요. 방법을 넣으니 6초쯤에 끝났어요(이 사이트의 기사를 쓸 때의 계산이고, 시간은 컴퓨터에 따라 달라져요).

앱 「힌트」의 구조

앱 「블록 맞추기」의 「힌트」도 같은 깊이 우선 탐색을 쓰고 있어요.

  • 번호가 가장 작은 빈 칸을 덮는 방법만 시험한다.
  • 돌려서 겹치는 같은 모양의 조각은 하나만 시험한다.
  • 조각보다 작게 갇힌 빈틈이 생기면 되돌아간다.
  • 조사하는 상태의 수에 상한을 두어 시간이 너무 오래 걸리지 않게 한다.

지금 놓은 그대로 다 채울 수 있다면 가장 채우기 어려운 빈 칸을 덮는 조각과 놓는 방법을 빛내요. 다 채울 수 없다면 처음에 만든 정답과 비교해서 맞지 않는 조각을 빛내고 「빛나는 조각을 빼면 잘 풀려요」라고 알려 줘요.

문제 만드는 법은 반드시 풀리는 문제 만드는 법, 12종류의 펜토미노의 정답 수는 펜토미노의 정답에서 소개하고 있어요.