A small program to solve the Klotski puzzle, also know as "Trabado"

klotski.js

"use strict";

const initialState = [
  "21v",
  "4",
  "4",
  "22v",
  "21v",
  "4",
  "4",
  "22v",
  "23v",
  "25h",
  "25h",
  "24v",
  "23v",
  "12",
  "13",
  "24v",
  "11",
  "0",
  "0",
  "14",
];

const pieces = initialState
  .filter((piece) => piece !== "0")
  .reduce((all, piece) => (all.includes(piece) ? all : all.concat(piece)), [])
  .sort();

const getState = (s, x, y) => s[y * 4 + x];
const setToState = (s) =>
  function (x, y, p) {
    s[y * 4 + x] = p;
  };

const isWinNode = ({ state }) =>
  getState(state, 1, 3) === "4" &&
  getState(state, 2, 3) === "4" &&
  getState(state, 1, 4) === "4" &&
  getState(state, 2, 4) === "4";

function calcNextMoves(state) {
  const isFree = (x, y) => getState(state, x, y) === "0";

  return pieces
    .map(function (piece) {
      const nextStates = [];

      const x = state.indexOf(piece) % 4;
      const y = Math.floor(state.indexOf(piece) / 4);

      const is1 = piece.startsWith("1");
      const is2H = piece.includes("h");
      const is2V = piece.includes("v");
      const is4 = piece.startsWith("4");

      const canMoveRight =
        (is1 && x < 3 && isFree(x + 1, y)) ||
        (is2V && x < 3 && isFree(x + 1, y) && isFree(x + 1, y + 1)) ||
        (is2H && x < 2 && isFree(x + 2, y)) ||
        (is4 && x < 2 && isFree(x + 2, y) && isFree(x + 2, y + 1));

      if (canMoveRight) {
        const newState = [].concat(state);
        const setState = setToState(newState);

        if (is1) {
          setState(x, y, "0");
          setState(x + 1, y, piece);
        }
        if (is2H) {
          setState(x, y, "0");
          setState(x + 2, y, piece);
        }
        if (is2V) {
          setState(x, y, "0");
          setState(x, y + 1, "0");
          setState(x + 1, y, piece);
          setState(x + 1, y + 1, piece);
        }
        if (is4) {
          setState(x, y, "0");
          setState(x, y + 1, "0");
          setState(x + 2, y, piece);
          setState(x + 2, y + 1, piece);
        }

        nextStates.push({
          move: `${piece} right`,
          state: newState,
        });
      }

      const canMoveLeft =
        (is1 && x > 0 && isFree(x - 1, y)) ||
        (is2V && x > 0 && isFree(x - 1, y) && isFree(x - 1, y + 1)) ||
        (is2H && x > 0 && isFree(x - 1, y)) ||
        (is4 && x > 0 && isFree(x - 1, y) && isFree(x - 1, y + 1));

      if (canMoveLeft) {
        const newState = [].concat(state);
        const setState = setToState(newState);

        if (is1) {
          setState(x, y, "0");
          setState(x - 1, y, piece);
        }
        if (is2H) {
          setState(x + 1, y, "0");
          setState(x - 1, y, piece);
        }
        if (is2V) {
          setState(x, y, "0");
          setState(x, y + 1, "0");
          setState(x - 1, y, piece);
          setState(x - 1, y + 1, piece);
        }
        if (is4) {
          setState(x + 1, y, "0");
          setState(x + 1, y + 1, "0");
          setState(x - 1, y, piece);
          setState(x - 1, y + 1, piece);
        }

        nextStates.push({
          move: `${piece} left`,
          state: newState,
        });
      }

      const canMoveUp =
        (is1 && y > 0 && isFree(x, y - 1)) ||
        (is2V && y > 0 && isFree(x, y - 1)) ||
        (is2H && y > 0 && isFree(x, y - 1) && isFree(x + 1, y - 1)) ||
        (is4 && y > 0 && isFree(x, y - 1) && isFree(x + 1, y - 1));

      if (canMoveUp) {
        const newState = [].concat(state);
        const setState = setToState(newState);

        if (is1) {
          setState(x, y, "0");
          setState(x, y - 1, piece);
        }
        if (is2H) {
          setState(x, y, "0");
          setState(x + 1, y, "0");
          setState(x, y - 1, piece);
          setState(x + 1, y - 1, piece);
        }
        if (is2V) {
          setState(x, y + 1, "0");
          setState(x, y - 1, piece);
        }
        if (is4) {
          setState(x, y + 1, "0");
          setState(x + 1, y + 1, "0");
          setState(x, y - 1, piece);
          setState(x + 1, y - 1, piece);
        }

        nextStates.push({
          move: `${piece} up`,
          state: newState,
        });
      }

      const canMoveDown =
        (is1 && y < 4 && isFree(x, y + 1)) ||
        (is2V && y < 3 && isFree(x, y + 2)) ||
        (is2H && y < 4 && isFree(x, y + 1) && isFree(x + 1, y + 1)) ||
        (is4 && y < 3 && isFree(x, y + 2) && isFree(x + 1, y + 2));

      if (canMoveDown) {
        const newState = [].concat(state);
        const setState = setToState(newState);

        if (is1) {
          setState(x, y, "0");
          setState(x, y + 1, piece);
        }
        if (is2H) {
          setState(x, y, "0");
          setState(x + 1, y, "0");
          setState(x, y + 1, piece);
          setState(x + 1, y + 1, piece);
        }
        if (is2V) {
          setState(x, y, "0");
          setState(x, y + 2, piece);
        }
        if (is4) {
          setState(x, y, "0");
          setState(x + 1, y, "0");
          setState(x, y + 2, piece);
          setState(x + 1, y + 2, piece);
        }

        nextStates.push({
          move: `${piece} down`,
          state: newState,
        });
      }

      return nextStates;
    })
    .flat();
}

const knownStates = [];

const serializeState = (s) => s.map((p) => p[0]).join("");

const addParent = (parent) => (node) => ({ ...node, parent });

const getMovesTo = (node) =>
  node.parent ? getMovesTo(node.parent).concat(node.move) : [];

function solveNode(node) {
  const { state } = node;

  const serialized = serializeState(state);
  if (knownStates.includes(serialized)) {
    return [];
  }
  knownStates.push(serialized);

  const nextNodes = calcNextMoves(state);

  const winNode = nextNodes.find(isWinNode);
  if (!winNode) {
    return nextNodes.map(addParent(node));
  }

  console.log("WIN!");
  console.log(winNode.state);

  const moves = getMovesTo(node).concat(winNode.move);
  console.log("Moves", moves.length);
  console.log(moves.join("\n"));

  process.exit(0);
}

console.log("Solving Klotski...");

const root = { state: initialState };
let leaves = [root];
while (leaves.length) {
  console.log(`Checking ${leaves.length} states`);
  leaves = leaves.map(solveNode).flat();
}

console.log("Solution not found");