STILLCODING

STILL CODING / NOTES

슬라이딩 사진퍼즐: 섞기는 거꾸로 걸어서, 풀이는 A*로 — 그리고 4×4부터 멈추는 풀이 버튼

JH Kim

슬라이딩 사진퍼즐은 빈칸 하나를 두고 사진 조각을 밀어 원래 그림을 맞추는 퍼즐입니다. 방장이 사진과 크기(3×3~6×6)를 정하면 참가자가 각자 같은 사진을 풉니다. 막히면 포기하고 정답 풀이를 단계별로 볼 수 있습니다.

사진을 올리고 참가자에게 나눠 주는 부분은 사진퍼즐의 코드를 복사해서 시작했고, 전달 방식은 사진은 서버를 거치지 않는다에서 다뤘기 때문에 이 글에서는 다루지 않습니다. 새로 쓴 것은 세 가지입니다. 풀 수 있는 배치 만들기, 줄 단위로 미는 이동, 그리고 정답 풀이입니다.

아무렇게나 섞으면 절반은 풀 수 없다

슬라이딩 퍼즐은 조각을 무작위로 늘어놓으면 안 됩니다. 빈칸이 있는 이동만 허용되기 때문에, 가능한 모든 배치 가운데 정확히 절반은 아무리 밀어도 원래 그림이 되지 않습니다. 그래서 섞기를 “정답 상태에서 시작해 빈칸을 무작위로 걷게 하는” 방식으로 했습니다.

function shuffleTiles(n, moveCount = null) {
  let tiles = solvedTiles(n);
  const totalMoves = moveCount ?? n * n * 30;
  let prevBlank = -1;
  for (let step = 0; step < totalMoves; step += 1) {
    const blank = blankIndex(tiles);
    const neighbors = neighborIndexes(blank, n);
    const candidates = prevBlank >= 0 ? neighbors.filter((index) => index !== prevBlank) : neighbors;
    const pick = candidates[Math.floor(Math.random() * candidates.length)] ?? neighbors[0];
    tiles = slideTilesSingle(tiles, pick);
    prevBlank = blank;
  }
  return tiles;
}

한 줄을 통째로 민다

빈칸과 같은 행이나 열에 있는 조각을 누르면, 그 조각과 빈칸 사이의 조각이 모두 빈칸 쪽으로 한 칸씩 밀립니다.

if (fromRow === blankRow) {
  const row = fromRow;
  if (fromCol < blankCol) {
    for (let col = blankCol; col > fromCol; col -= 1) {
      next[row * n + col] = next[row * n + col - 1];
    }
  } else {
    for (let col = blankCol; col < fromCol; col += 1) {
      next[row * n + col] = next[row * n + col + 1];
    }
  }
  next[fromIndex] = BLANK;
  return { tiles: next, moveCount: Math.abs(blankCol - fromCol) };
}

조각 하나를 누르고 빈칸까지 여러 칸 떨어져 있어도 한 번에 밀립니다. 이웃한 조각만 한 칸씩 움직이는 전통적인 방식과 다른 점입니다. 이동 횟수는 밀린 조각의 개수만큼 올라갑니다(moveCount). 완료 연출에 N번 이동으로 표시되고, 결과에도 함께 제출됩니다.

이 이동 규칙은 풀이 탐색에도 영향을 줍니다. 아래에서 다룹니다.

포기하면 정답 풀이를 보여 준다

“포기”를 누르고 확인하면 지금 상태에서 정답까지 가는 경로를 계산해서, 이전/다음 버튼으로 한 단계씩 보여 줍니다. 경로를 찾는 방법은 크기에 따라 다릅니다.

export function findSolutionPath(startTiles, n) {
  // ...
  const limit = NODE_LIMITS[n] || 800_000;

  if (n <= 3) {
    const linePath = searchSolution(startKey, goalKey, n, lineSlideMoves, limit);
    if (linePath) return linePath;
  }
  return searchSolutionAStar(startKey, goalKey, n, adjacentSlideMoves, limit);
}

직접 재 보니

풀이 버튼이 실제로 얼마나 걸리고 얼마나 성공하는지 Node 22에서 재 봤습니다. 게임과 같은 방식(n × n × 30번 걷기)으로 섞은 배치를 findSolutionPath에 넣고 시간을 쟀습니다.

크기시도실패걸린 시간풀이 길이
3×3300중앙값 143ms, 최대 315ms11~20번(줄 이동)
4×4126중앙값 약 18.7초, 최대 19.1초44~56번(한 칸 이동)
5×544약 29초없음
6×611약 50초없음

3×3은 문제가 없습니다. 4×4는 열두 번 중 여섯 번이 실패했고, 걸린 시간은 중앙값이 약 19초였습니다. 5×5와 6×6은 시도한 것 모두 실패했습니다. 표본이 작고(6×6은 한 번) 데스크톱 Node에서 잰 값이라 정확한 성공률이나 모바일 시간은 알 수 없지만, 3×3 밖에서는 이 기능을 믿을 수 없다는 것은 분명합니다.

더 나쁜 것은 계산이 메인 스레드에서 동기적으로 돌아간다는 점입니다.

els.solutionMessage.textContent = "정답 경로를 찾는 중입니다. 잠시만 기다려 주세요.";
await new Promise((resolve) => { window.setTimeout(resolve, 0); });
const path = findSolutionPath(tiles, n);
if (!path) {
  ctx.notify("풀이를 계산하지 못했습니다. 잠시 후 다시 시도해 주세요.");
  return;
}

setTimeout(…, 0)을 한 번 기다리는 것은 “찾는 중입니다” 문구를 먼저 그리기 위해서입니다. 그다음 findSolutionPath가 시작되면 끝날 때까지 화면이 멈춥니다. 4×4에서 위 표대로라면 약 19초 동안 아무것도 눌리지 않고, 결국 “풀이를 계산하지 못했습니다”가 뜰 수도 있습니다.

어떻게 고칠 것인가

남은 일

참고