solver-worker.js

"use strict";

/*
 * Rubik's Cube Solver worker.
 *
 * The vendored cube.js and min2phase.js files are used under their MIT
 * licenses; see the license files in vendor/.
 * Keeping search in a Web Worker prevents its one-time table generation and
 * each solve from blocking the 3D controls or move player.
 */
const workerSignature = new URLSearchParams(self.location.search).get("__sign");
function signedAssetUrl(path) {
  const url = new URL(path, self.location.href);
  if (workerSignature) url.searchParams.set("__sign", workerSignature);
  return url.href;
}
self.postMessage({type: "status", status: "loading", message: "Loading cube parser…"});
importScripts(signedAssetUrl("./vendor/cube.js"));
self.postMessage({type: "status", status: "loading", message: "Loading fast search engine…"});
importScripts(signedAssetUrl("./vendor/min2phase.js"));
const Min2Phase = self.min2phase;
self.postMessage({type: "status", status: "loaded", message: "Initializing solve tables…"});

const FACE_ORDER = ["U", "R", "F", "D", "L", "B"];
const SOLVED = FACE_ORDER.map(face => face.repeat(9)).join("");
let workerInitialized = false;

function fail(code, message) {
  const error = new Error(message);
  error.code = code;
  throw error;
}

function isPermutation(values, size) {
  return Array.isArray(values)
    && values.length === size
    && values.every(Number.isInteger)
    && new Set(values).size === size
    && values.every(value => value >= 0 && value < size);
}

function permutationParity(values) {
  let inversions = 0;
  for (let left = 0; left < values.length; left++) {
    for (let right = left + 1; right < values.length; right++) {
      if (values[left] > values[right]) inversions++;
    }
  }
  return inversions % 2;
}

function normalizeCube(input) {
  if (!input || typeof input !== "object" || Array.isArray(input)) {
    fail("input_type", "Cube input must contain the six U/R/F/D/L/B faces.");
  }

  const values = [];
  for (const face of FACE_ORDER) {
    const facelets = input[face];
    if (!Array.isArray(facelets) || facelets.flat(Infinity).length !== 9) {
      fail("face_shape", `The ${face} face must contain exactly nine stickers.`);
    }
    values.push(...facelets.flat(Infinity));
  }
  if (values.some(value => typeof value !== "string" || !value)) {
    fail("empty_sticker", "Every sticker needs one of the six chosen colors.");
  }

  const centers = FACE_ORDER.map((_, index) => values[index * 9 + 4]);
  if (new Set(centers).size !== 6) {
    fail("duplicate_centers", "Each face center must use a different color.");
  }

  const counts = new Map();
  values.forEach(value => counts.set(value, (counts.get(value) || 0) + 1));
  if (counts.size !== 6 || [...counts.values()].some(count => count !== 9)) {
    fail("color_multiplicity", "Every cube color must appear exactly nine times.");
  }

  const colorToFace = new Map(centers.map((color, index) => [color, FACE_ORDER[index]]));
  const canonical = values.map(value => colorToFace.get(value) || "?").join("");
  if (canonical.includes("?")) {
    fail("unknown_color", "Every sticker must match one of the six center colors.");
  }

  const cube = Cube.fromString(canonical);
  const state = cube.toJSON();

  // fromString is intentionally permissive, so require an exact round trip
  // and then verify all physical invariants ourselves before search.
  if (cube.asString() !== canonical || !isPermutation(state.cp, 8) || !isPermutation(state.ep, 12)) {
    fail("piece_set", "These stickers do not form the eight real corners and twelve real edges. Recheck the colors on each piece.");
  }
  if (!Array.isArray(state.co) || state.co.length !== 8 || state.co.some(value => !Number.isInteger(value) || value < 0 || value > 2)) {
    fail("corner_orientation", "A corner has an impossible orientation. Recheck the three colors around each corner.");
  }
  if (!Array.isArray(state.eo) || state.eo.length !== 12 || state.eo.some(value => value !== 0 && value !== 1)) {
    fail("edge_orientation", "An edge has an impossible orientation. Recheck the two colors on each edge.");
  }
  if (state.co.reduce((sum, value) => sum + value, 0) % 3 !== 0) {
    fail("corner_twist", "This state has one or more impossible twisted corners. Recheck the corner stickers.");
  }
  if (state.eo.reduce((sum, value) => sum + value, 0) % 2 !== 0) {
    fail("edge_flip", "This state has an impossible flipped edge. Recheck the edge stickers.");
  }
  if (permutationParity(state.cp) !== permutationParity(state.ep)) {
    fail("parity", "This state has an impossible piece swap. Recheck the stickers on the last pieces you entered.");
  }

  return {
    canonical,
    faceToColor: Object.fromEntries(FACE_ORDER.map((face, index) => [face, centers[index]])),
    cube,
  };
}

function parseMoves(algorithm) {
  if (!algorithm || !algorithm.trim()) return [];
  const moves = algorithm.trim().split(/\s+/);
  if (moves.some(move => !/^[URFDLB](?:2|')?$/.test(move))) {
    fail("solver_output", "The solver returned unsupported move notation.");
  }
  return moves;
}

function initialize() {
  if (workerInitialized) return;
  self.postMessage({type: "status", status: "preparing"});
  Min2Phase.initFull();
  workerInitialized = true;
  self.postMessage({type: "status", status: "ready"});
}

self.onmessage = event => {
  const message = event.data || {};
  if (message.type === "init") {
    try {
      initialize();
    } catch (error) {
      self.postMessage({
        type: "status",
        status: "error",
        message: `The browser solver could not initialize${error && error.message ? `: ${error.message}` : "."}`,
      });
    }
    return;
  }
  if (message.type !== "solve") return;

  try {
    initialize();
    const normalized = normalizeCube(message.cube);
    const started = performance.now();
    const algorithm = normalized.canonical === SOLVED ? "" : Min2Phase.solve(normalized.canonical);
    const searchSeconds = (performance.now() - started) / 1000;
    if (algorithm === null || /^Error\s/i.test(algorithm)) {
      fail("search_depth", "No solution was found within 22 moves. Please recheck the entered stickers.");
    }
    self.postMessage({
      type: "result",
      id: message.id,
      ok: true,
      canonical: normalized.canonical,
      faceToColor: normalized.faceToColor,
      moves: parseMoves(algorithm),
      searchSeconds,
    });
  } catch (error) {
    self.postMessage({
      type: "result",
      id: message.id,
      ok: false,
      error: {
        code: error && error.code ? error.code : "solver_failure",
        message: error && error.message ? error.message : "The cube could not be solved.",
      },
    });
  }
};