Klotski: write the rules before the animation

Klotski has twenty cells and ten pieces. The hard part is not the layout, it is the check: whether a piece can move one cell in a given direction. Get it wrong and the feel is instantly off — a tap does nothing, or two pieces overlap.

The board is twenty cells, not twenty objects

My first version stored “which piece owns this cell” in a 2D array, and every move cleared the old cells and wrote the new ones. A 2x2 piece touches four cells, so each move wrote four and cleared four, with nothing stopping it from writing over a neighbour.

A simpler representation: a piece is its top-left corner plus width and height, and occupancy is computed on demand.

Figure: two checks for a move, one sorted key for state deduplication.

function occupies(block: Block, x: number, y: number): boolean {
  return x >= block.x && x < block.x + block.w
      && y >= block.y && y < block.y + block.h;
}

A move check needs exactly two facts: is the target rectangle inside the board, and does anything else overlap it.

export function canMove(blocks: Block[], id: string, dx: number, dy: number): boolean {
  const block = blocks.find((item) => item.id === id);
  if (!block) return false;
  const nx = block.x + dx;
  const ny = block.y + dy;
  if (nx < 0 || ny < 0 || nx + block.w > W || ny + block.h > H) return false;
  return !blocks.some((other) =>
    other.id !== id && overlaps(other, nx, ny, block.w, block.h),
  );
}

Overlap is easier than per-cell scanning and does not care about shape. Add a 3x1 piece later and this code does not change.

Deduplicating states

For playing, the check is enough. I also wanted the minimum number of moves, which means searching the state space.

Klotski has roughly a hundred thousand legal states, so BFS is fine. The important part is deduplication: the same position must not count twice just because the pieces array is ordered differently.

function keyOf(blocks: Block[]): string {
  return blocks
    .slice()
    .sort((a, b) => a.id.localeCompare(b.id))
    .map((block) => block.id + ':' + block.x + ',' + block.y)
    .join('|');
}

Sorting by id and joining is cheaper than serialising the object, and far easier to debug — you can read the position straight out of the key.

Why not A*

A* looks smarter, but the heuristic is hard to make reliable here: reaching the exit requires clearing a corridor, and that cost cannot be estimated safely. Overestimate and you lose the optimal path; underestimate and you have written BFS with extra steps.

BFS finishes in tens of milliseconds at this scale and the move count is guaranteed optimal. Trading correctness for an optimisation the player cannot perceive is a bad trade.

Animation comes last

The rules and the search are pure functions with no DOM. Animation does one thing: render the result of moveBlock as a translation. Because of that the logic is testable before any animation exists — my selftest has four assertions for Klotski: the opening is unsolved, Cao Cao cannot move down because Guan Yu blocks it, a pawn can step down, and the coordinate changes afterwards.

Write the data first, then the feel. The other order hurts: you finish the animation, discover the rules are wrong, and now two layers need changing at once.