15-Puzzle: Sliding Tiles

// 15-Puzzle: Sliding Tiles
// 4x4 grid, tiles numbered 1..15 and a blank (0). Tap an adjacent tile to
// slide it into the gap. Win when tiles are in row-major order with the
// blank in the bottom-right.
//
// Shuffle is performed by random legal moves only, so the puzzle is always
// solvable. "Solve" runs A* with Manhattan + linear-conflict heuristic and
// animates the solution at ~3 moves/sec.

const N = 4;
const GOAL = new Uint8Array(N * N);
for (let i = 0; i < N * N - 1; i++) GOAL[i] = i + 1;
GOAL[N * N - 1] = 0;

let board;            // Uint8Array(16), values 0..15, 0 is blank
let blank;            // index of blank
let moveCount = 0;
let startTime = 0;
let elapsedMs = 0;
let won = false;
let winFlash = 0;     // 0..1, fades out after win

// Sliding animation: only one tile animates at a time. We snapshot the
// post-move board, but draw the moved tile interpolating from its old cell.
let anim = null;      // { from, to, t, dur, value }
let queue = [];       // queue of pending tile indices to slide (for solver)
let solving = false;
let solveDelayMs = 0; // accumulator between solver-driven moves

// UI
let W = 0, H = 0;
let buttons = [];     // [{ x, y, w, h, label, action }]
let lastMouseDown = false;
let pressStart = null;

function shuffleByRandomMoves(steps) {
  // Random legal moves from the goal state. Avoid immediate reversal.
  let last = -1;
  for (let s = 0; s < steps; s++) {
    const nbs = neighbors(blank);
    const choices = last < 0 ? nbs : nbs.filter((n) => n !== last);
    const pick = choices[(Math.random() * choices.length) | 0];
    swap(blank, pick);
    last = blank; // the cell we just emptied (where the moved tile came from)
    blank = pick;
  }
}

function neighbors(i) {
  const x = i % N, y = (i / N) | 0;
  const out = [];
  if (x > 0)     out.push(i - 1);
  if (x < N - 1) out.push(i + 1);
  if (y > 0)     out.push(i - N);
  if (y < N - 1) out.push(i + N);
  return out;
}

function swap(a, b) {
  const t = board[a]; board[a] = board[b]; board[b] = t;
}

function reset() {
  board = new Uint8Array(GOAL);
  blank = N * N - 1;
  // 80 random legal moves is enough to look thoroughly scrambled (the
  // true optimal-solve distance averages ~20-30 moves at this depth),
  // while keeping the A* solver fast.
  shuffleByRandomMoves(80);
  moveCount = 0;
  startTime = performance.now();
  elapsedMs = 0;
  won = false;
  winFlash = 0;
  anim = null;
  queue = [];
  solving = false;
  solveDelayMs = 0;
}

function init({ width, height }) {
  W = width; H = height;
  reset();
}

function isGoal() {
  for (let i = 0; i < N * N; i++) if (board[i] !== GOAL[i]) return false;
  return true;
}

function tryMoveTileAt(idx) {
  if (anim || solving) return false;
  if (won) return false;
  if (board[idx] === 0) return false;
  // Must be orthogonally adjacent to the blank.
  if (!neighbors(idx).includes(blank)) return false;
  startSlide(idx, blank);
  moveCount++;
  return true;
}

function startSlide(fromIdx, toIdx) {
  // The tile at fromIdx slides into toIdx (the blank). After animation we
  // update the board logically.
  anim = {
    from: fromIdx,
    to: toIdx,
    t: 0,
    dur: solving ? 0.18 : 0.11,
    value: board[fromIdx],
  };
}

function finishAnim() {
  if (!anim) return;
  swap(anim.from, anim.to);
  blank = anim.from;
  anim = null;
  if (!won && isGoal()) {
    won = true;
    winFlash = 1;
  }
}

// ----- A* solver -----
// 16-cell boards encoded as a 64-bit hex string (4 bits per cell).
function encode(b) {
  let s = "";
  for (let i = 0; i < N * N; i++) s += b[i].toString(16);
  return s;
}
function decode(s) {
  const b = new Uint8Array(N * N);
  for (let i = 0; i < N * N; i++) b[i] = parseInt(s[i], 16);
  return b;
}
function blankOf(b) {
  for (let i = 0; i < N * N; i++) if (b[i] === 0) return i;
  return -1;
}

const GOAL_POS = new Uint8Array(N * N);
for (let v = 0; v < N * N; v++) {
  // value v -> its goal index
  if (v === 0) GOAL_POS[v] = N * N - 1;
  else GOAL_POS[v] = v - 1;
}

function heuristic(b) {
  // Manhattan distance + linear conflicts (each conflict adds 2).
  let h = 0;
  for (let i = 0; i < N * N; i++) {
    const v = b[i];
    if (v === 0) continue;
    const gi = GOAL_POS[v];
    const x = i % N, y = (i / N) | 0;
    const gx = gi % N, gy = (gi / N) | 0;
    h += Math.abs(x - gx) + Math.abs(y - gy);
  }
  // Linear conflicts along rows
  for (let y = 0; y < N; y++) {
    for (let i = 0; i < N; i++) {
      const a = b[y * N + i];
      if (a === 0) continue;
      const ay = (GOAL_POS[a] / N) | 0;
      if (ay !== y) continue;
      for (let j = i + 1; j < N; j++) {
        const c = b[y * N + j];
        if (c === 0) continue;
        const cy = (GOAL_POS[c] / N) | 0;
        if (cy !== y) continue;
        if (GOAL_POS[a] > GOAL_POS[c]) h += 2;
      }
    }
  }
  // Linear conflicts along columns
  for (let x = 0; x < N; x++) {
    for (let i = 0; i < N; i++) {
      const a = b[i * N + x];
      if (a === 0) continue;
      const ax = GOAL_POS[a] % N;
      if (ax !== x) continue;
      for (let j = i + 1; j < N; j++) {
        const c = b[j * N + x];
        if (c === 0) continue;
        const cx = GOAL_POS[c] % N;
        if (cx !== x) continue;
        if (GOAL_POS[a] > GOAL_POS[c]) h += 2;
      }
    }
  }
  return h;
}

// Simple binary-heap priority queue keyed on f.
class PQ {
  constructor() { this.a = []; }
  push(item, f) {
    this.a.push({ item, f });
    let i = this.a.length - 1;
    while (i > 0) {
      const p = (i - 1) >> 1;
      if (this.a[p].f <= this.a[i].f) break;
      [this.a[p], this.a[i]] = [this.a[i], this.a[p]];
      i = p;
    }
  }
  pop() {
    if (!this.a.length) return null;
    const top = this.a[0];
    const last = this.a.pop();
    if (this.a.length) {
      this.a[0] = last;
      let i = 0, n = this.a.length;
      for (;;) {
        const l = 2 * i + 1, r = 2 * i + 2;
        let m = i;
        if (l < n && this.a[l].f < this.a[m].f) m = l;
        if (r < n && this.a[r].f < this.a[m].f) m = r;
        if (m === i) break;
        [this.a[m], this.a[i]] = [this.a[i], this.a[m]];
        i = m;
      }
    }
    return top.item;
  }
  get size() { return this.a.length; }
}

function solveAStar(startBoard) {
  // Returns array of board indices (the tile to slide each step), or null.
  const startKey = encode(startBoard);
  const goalKey = encode(GOAL);
  if (startKey === goalKey) return [];

  const open = new PQ();
  const gScore = new Map();
  const parent = new Map(); // key -> { prev, movedTile }

  gScore.set(startKey, 0);
  open.push(startKey, heuristic(startBoard));

  // Cap to keep the worker responsive; 15-puzzle solutions average ~50
  // moves and the search can blow up — but our shuffles are 200 random
  // legal moves so this is bounded in practice.
  const NODE_CAP = 250000;
  let expanded = 0;

  while (open.size) {
    const key = open.pop();
    if (key === goalKey) break;
    expanded++;
    if (expanded > NODE_CAP) return null;

    const b = decode(key);
    const bl = blankOf(b);
    const g = gScore.get(key);
    const nbs = neighbors(bl);
    for (const nb of nbs) {
      const movedTile = b[nb];
      // Swap blank and nb
      const nb2 = new Uint8Array(b);
      nb2[bl] = movedTile; nb2[nb] = 0;
      const k2 = encode(nb2);
      const tentative = g + 1;
      const prev = gScore.get(k2);
      if (prev === undefined || tentative < prev) {
        gScore.set(k2, tentative);
        parent.set(k2, { prev: key, moved: nb }); // nb was the tile's cell
        open.push(k2, tentative + heuristic(nb2));
      }
    }
  }

  if (!parent.has(goalKey) && startKey !== goalKey) return null;
  // Reconstruct: each parent entry records the cell of the tile that moved
  // (its location BEFORE the move, i.e. relative to the previous board).
  const path = [];
  let cur = goalKey;
  while (cur !== startKey) {
    const p = parent.get(cur);
    if (!p) return null;
    path.push(p.moved);
    cur = p.prev;
  }
  path.reverse();
  return path;
}

function startSolve() {
  if (won || solving || anim) return;
  const path = solveAStar(board);
  if (!path) return;
  if (path.length === 0) return;
  // Translate path of "cell containing the tile to move on the snapshot at
  // step k" into a sequence we can drive frame-by-frame. We'll re-derive
  // the moving tile relative to the current board state as we go, so we
  // also need to walk a virtual board to map each step's cell to the live
  // cell at the moment of execution. Since A* already produced moves on
  // the actual board sequence, we can replay them directly.
  queue = path.slice();
  solving = true;
  solveDelayMs = 0;
}

// ----- Layout / rendering -----
function layout() {
  const headerH = 56;
  const buttonH = 44;
  const padding = 16;
  const availH = H - headerH - buttonH - padding * 3;
  const availW = W - padding * 2;
  const side = Math.max(120, Math.min(availW, availH));
  const ox = (W - side) / 2;
  const oy = headerH + padding;
  const gap = Math.max(3, side * 0.012);
  const cell = (side - gap * (N + 1)) / N;

  // buttons row beneath the board
  const by = oy + side + padding;
  const bw = Math.min(160, (W - padding * 3) / 2);
  const bgap = padding;
  const totalBW = bw * 2 + bgap;
  const bx0 = (W - totalBW) / 2;
  buttons = [
    { x: bx0,             y: by, w: bw, h: buttonH, label: "Solve",   action: "solve" },
    { x: bx0 + bw + bgap, y: by, w: bw, h: buttonH, label: "Shuffle", action: "shuffle" },
  ];

  return { side, ox, oy, gap, cell };
}

function cellRect(i, L) {
  const x = i % N, y = (i / N) | 0;
  return {
    x: L.ox + L.gap + x * (L.cell + L.gap),
    y: L.oy + L.gap + y * (L.cell + L.gap),
    s: L.cell,
  };
}

function cellAt(px, py, L) {
  // Returns cell index or -1
  for (let i = 0; i < N * N; i++) {
    const r = cellRect(i, L);
    if (px >= r.x && px < r.x + r.s && py >= r.y && py < r.y + r.s) return i;
  }
  return -1;
}

function pointInRect(px, py, r) {
  return px >= r.x && px < r.x + r.w && py >= r.y && py < r.y + r.h;
}

function easeOutCubic(t) {
  const u = 1 - t;
  return 1 - u * u * u;
}

function formatTime(ms) {
  const t = Math.floor(ms / 1000);
  const m = (t / 60) | 0;
  const s = t % 60;
  return `${m}:${String(s).padStart(2, "0")}`;
}

function drawTile(ctx, x, y, s, value) {
  const r = Math.max(4, s * 0.08);
  // Soft gradient fill per tile
  const grad = ctx.createLinearGradient(x, y, x, y + s);
  // Subtle hue shift across rows so it's pretty but stays readable
  const row = ((value - 1) / N) | 0;
  const stops = [
    ["#2a4365", "#1e3a5f"], // row 0 — blue
    ["#2c5282", "#234e7a"], // row 1
    ["#2b6cb0", "#1f5894"], // row 2
    ["#3182ce", "#2563a8"], // row 3
  ];
  const [c1, c2] = stops[Math.min(3, Math.max(0, row))];
  grad.addColorStop(0, c1);
  grad.addColorStop(1, c2);
  ctx.fillStyle = grad;
  ctx.beginPath();
  ctx.moveTo(x + r, y);
  ctx.lineTo(x + s - r, y);
  ctx.quadraticCurveTo(x + s, y, x + s, y + r);
  ctx.lineTo(x + s, y + s - r);
  ctx.quadraticCurveTo(x + s, y + s, x + s - r, y + s);
  ctx.lineTo(x + r, y + s);
  ctx.quadraticCurveTo(x, y + s, x, y + s - r);
  ctx.lineTo(x, y + r);
  ctx.quadraticCurveTo(x, y, x + r, y);
  ctx.closePath();
  ctx.fill();

  // Highlight stripe
  ctx.fillStyle = "rgba(255,255,255,0.08)";
  ctx.fillRect(x + r, y + Math.max(2, s * 0.05), s - 2 * r, Math.max(1, s * 0.04));

  // Value
  const correct = (value - 1) === GOAL_POS[value] && false; // not used; could highlight
  ctx.fillStyle = "#f0f6ff";
  const fs = Math.floor(s * (value >= 10 ? 0.38 : 0.46));
  ctx.font = `bold ${fs}px sans-serif`;
  ctx.textAlign = "center";
  ctx.textBaseline = "middle";
  ctx.fillText(String(value), x + s / 2, y + s / 2 + s * 0.02);
  void correct;
}

function drawSlot(ctx, x, y, s) {
  const r = Math.max(4, s * 0.08);
  ctx.fillStyle = "#1a1f2a";
  ctx.beginPath();
  ctx.moveTo(x + r, y);
  ctx.lineTo(x + s - r, y);
  ctx.quadraticCurveTo(x + s, y, x + s, y + r);
  ctx.lineTo(x + s, y + s - r);
  ctx.quadraticCurveTo(x + s, y + s, x + s - r, y + s);
  ctx.lineTo(x + r, y + s);
  ctx.quadraticCurveTo(x, y + s, x, y + s - r);
  ctx.lineTo(x, y + r);
  ctx.quadraticCurveTo(x, y, x + r, y);
  ctx.closePath();
  ctx.fill();
}

function drawButton(ctx, b, hot) {
  const r = 10;
  ctx.fillStyle = hot ? "#2c5282" : "#1f2937";
  ctx.beginPath();
  ctx.moveTo(b.x + r, b.y);
  ctx.lineTo(b.x + b.w - r, b.y);
  ctx.quadraticCurveTo(b.x + b.w, b.y, b.x + b.w, b.y + r);
  ctx.lineTo(b.x + b.w, b.y + b.h - r);
  ctx.quadraticCurveTo(b.x + b.w, b.y + b.h, b.x + b.w - r, b.y + b.h);
  ctx.lineTo(b.x + r, b.y + b.h);
  ctx.quadraticCurveTo(b.x, b.y + b.h, b.x, b.y + b.h - r);
  ctx.lineTo(b.x, b.y + r);
  ctx.quadraticCurveTo(b.x, b.y, b.x + r, b.y);
  ctx.closePath();
  ctx.fill();
  ctx.strokeStyle = "rgba(255,255,255,0.12)";
  ctx.lineWidth = 1;
  ctx.stroke();
  ctx.fillStyle = "#e6edf3";
  ctx.font = "bold 16px sans-serif";
  ctx.textAlign = "center";
  ctx.textBaseline = "middle";
  ctx.fillText(b.label, b.x + b.w / 2, b.y + b.h / 2);
}

function handleInput(input) {
  // Keyboard
  if (input.justPressed("r") || input.justPressed("R")) {
    reset();
    return;
  }

  // Track press-then-release as a tap (avoid drag-misfires).
  const md = input.mouseDown;
  if (md && !lastMouseDown) {
    pressStart = { x: input.mouseX, y: input.mouseY };
  } else if (!md && lastMouseDown && pressStart) {
    const dx = input.mouseX - pressStart.x;
    const dy = input.mouseY - pressStart.y;
    if (Math.abs(dx) < 14 && Math.abs(dy) < 14) {
      onTap(input.mouseX, input.mouseY);
    }
    pressStart = null;
  }
  lastMouseDown = md;

  // Drain any click events (some platforms only emit click, not down/up).
  const clicks = input.consumeClicks ? input.consumeClicks() : [];
  for (const c of clicks) onTap(c.x, c.y);
}

function onTap(px, py) {
  // Buttons take priority.
  for (const b of buttons) {
    if (pointInRect(px, py, b)) {
      if (b.action === "shuffle") {
        reset();
      } else if (b.action === "solve") {
        if (solving) {
          // cancel solver
          solving = false;
          queue = [];
        } else {
          startSolve();
        }
      }
      return;
    }
  }
  // Board taps
  const L = layout();
  const idx = cellAt(px, py, L);
  if (idx >= 0) tryMoveTileAt(idx);
}

function tick({ ctx, dt, width, height, input }) {
  W = width; H = height;
  const L = layout();

  if (!won && !solving) elapsedMs = performance.now() - startTime;

  handleInput(input);

  // Advance animation
  if (anim) {
    anim.t += dt / anim.dur;
    if (anim.t >= 1) {
      anim.t = 1;
      finishAnim();
    }
  } else if (solving && queue.length) {
    solveDelayMs += dt * 1000;
    if (solveDelayMs >= 150) {
      solveDelayMs = 0;
      const next = queue.shift();
      // The solver path enumerates the cell of the tile to slide on the
      // board snapshot at that step. Because A* produced these moves
      // against the actual sequence starting from our current board, this
      // is consistent: `next` is the live cell of an adjacent tile.
      if (board[next] !== 0 && neighbors(next).includes(blank)) {
        startSlide(next, blank);
        moveCount++;
      } else {
        // Sanity fallback: stop solver if state diverged.
        solving = false;
        queue = [];
      }
      if (queue.length === 0) {
        // last move starting; let it animate, then drop solving flag.
      }
    }
  } else if (solving && !queue.length) {
    solving = false;
  }

  // Background
  const bg = ctx.createLinearGradient(0, 0, 0, H);
  bg.addColorStop(0, "#0b0e14");
  bg.addColorStop(1, "#11151c");
  ctx.fillStyle = bg;
  ctx.fillRect(0, 0, W, H);

  // Header
  ctx.fillStyle = "#e6edf3";
  ctx.font = "bold 18px sans-serif";
  ctx.textBaseline = "top";
  ctx.textAlign = "left";
  ctx.fillText(`Moves ${moveCount}`, 14, 14);
  ctx.textAlign = "right";
  ctx.fillText(`Time ${formatTime(elapsedMs)}`, W - 14, 14);
  ctx.textAlign = "center";
  ctx.font = "12px sans-serif";
  ctx.fillStyle = "rgba(230,237,243,0.55)";
  ctx.fillText(solving ? "solving with A* — tap Solve to cancel" : "tap an adjacent tile  ·  R to shuffle", W / 2, 18);

  // Board frame
  const frameR = Math.max(6, L.side * 0.018);
  ctx.fillStyle = "#0d1320";
  ctx.beginPath();
  ctx.moveTo(L.ox + frameR, L.oy);
  ctx.lineTo(L.ox + L.side - frameR, L.oy);
  ctx.quadraticCurveTo(L.ox + L.side, L.oy, L.ox + L.side, L.oy + frameR);
  ctx.lineTo(L.ox + L.side, L.oy + L.side - frameR);
  ctx.quadraticCurveTo(L.ox + L.side, L.oy + L.side, L.ox + L.side - frameR, L.oy + L.side);
  ctx.lineTo(L.ox + frameR, L.oy + L.side);
  ctx.quadraticCurveTo(L.ox, L.oy + L.side, L.ox, L.oy + L.side - frameR);
  ctx.lineTo(L.ox, L.oy + frameR);
  ctx.quadraticCurveTo(L.ox, L.oy, L.ox + frameR, L.oy);
  ctx.closePath();
  ctx.fill();
  ctx.strokeStyle = "rgba(255,255,255,0.04)";
  ctx.lineWidth = 1;
  ctx.stroke();

  // Empty slot wells
  for (let i = 0; i < N * N; i++) {
    const r = cellRect(i, L);
    drawSlot(ctx, r.x, r.y, r.s);
  }

  // Tiles (skip the one currently animating; we draw it last)
  for (let i = 0; i < N * N; i++) {
    if (anim && i === anim.from) continue; // value here is 0 in board but tile is in flight
    const v = board[i];
    if (v === 0) continue;
    const r = cellRect(i, L);
    drawTile(ctx, r.x, r.y, r.s, v);
  }

  // Animating tile
  if (anim) {
    const eased = easeOutCubic(anim.t);
    const a = cellRect(anim.from, L);
    const b = cellRect(anim.to, L);
    const x = a.x + (b.x - a.x) * eased;
    const y = a.y + (b.y - a.y) * eased;
    drawTile(ctx, x, y, a.s, anim.value);
  }

  // Buttons. When solving, swap the Solve button's label to "Stop" in place
  // and restore it afterwards — avoids allocating a clone object every frame.
  for (const b of buttons) {
    const hot = (input.mouseDown && pointInRect(input.mouseX, input.mouseY, b))
              || (b.action === "solve" && solving);
    if (b.action === "solve" && solving) {
      const orig = b.label;
      b.label = "Stop";
      drawButton(ctx, b, true);
      b.label = orig;
    } else {
      drawButton(ctx, b, hot);
    }
  }

  // Win flourish
  if (won) {
    winFlash = Math.max(0, winFlash - dt * 0.6);
    // Pulsing gold overlay on the board
    const a = 0.18 + 0.18 * Math.sin(performance.now() * 0.006);
    ctx.fillStyle = `rgba(237,194,46,${0.35 + a * 0.3})`;
    // Draw thin rings expanding from center
    const cx = L.ox + L.side / 2, cy = L.oy + L.side / 2;
    for (let k = 0; k < 3; k++) {
      const phase = ((performance.now() * 0.001) + k * 0.33) % 1;
      const rad = phase * (L.side * 0.55);
      ctx.beginPath();
      ctx.arc(cx, cy, rad, 0, Math.PI * 2);
      ctx.strokeStyle = `rgba(237,194,46,${(1 - phase) * 0.55})`;
      ctx.lineWidth = 3;
      ctx.stroke();
    }
    // Banner
    ctx.fillStyle = "rgba(8,12,20,0.78)";
    const banH = 64;
    const banY = cy - banH / 2;
    ctx.fillRect(L.ox, banY, L.side, banH);
    ctx.fillStyle = "#ffd966";
    ctx.font = "bold 28px sans-serif";
    ctx.textAlign = "center";
    ctx.textBaseline = "middle";
    ctx.fillText("Solved!", cx, banY + banH / 2 - 6);
    ctx.fillStyle = "#cfd6e2";
    ctx.font = "13px sans-serif";
    ctx.fillText(`${moveCount} moves · ${formatTime(elapsedMs)}  ·  tap Shuffle for a new puzzle`, cx, banY + banH / 2 + 18);
  }
}