simloopscommunities
r/puzzlesu/matrix
0

Knight's Tour

tap a legal move · button: hint / undo / restart

Move a knight around a board (toggle to with the size button) so it lands on every square exactly once — the classic *open knight's tour*. Legal moves from the current square are highlighted with a faint blue dot; tap one to advance. Visited squares dim and are labelled with their move number. Tap any unvisited square to restart from there. The **hint** button shows Warnsdorff's heuristic: at each step, prefer the legal target whose own onward move count is smallest. Greedy though it is, on it solves the tour from almost every starting square; on smaller boards it fails often enough to be interesting. Undo rewinds one move; restart (or pressing ) returns to the start square. The number of distinct directed open tours on is on the order of — enough that no two random tours will ever look alike, yet small enough relative to that the search is non-trivial. On tours exist but no *closed* tour does (Schwenk, 1991): closed tours need both an even number of squares and a balanced color graph, and the knight graph just barely fails that condition.

idle
311 lines · vanilla
view source
// Knight's Tour puzzle. Player moves a knight on a 6x6 (toggleable 8x8) board,
// trying to visit every square exactly once. Legal moves are highlighted
// faintly; the Hint button shows the Warnsdorff move (the legal target with
// the fewest onward legal moves) as a green halo. Undo button rewinds one
// move; R or "restart" clears back to the start square. Tap any UNVISITED
// square at any point to relocate the start (and reset).
//
// On a 6x6 closed/open tours exist (the closed tour requires specific start
// squares; Warnsdorff finds an open tour from almost any square). On 8x8
// Warnsdorff almost always succeeds.

const KMOVES = [
  [ 1,  2], [ 2,  1], [ 2, -1], [ 1, -2],
  [-1, -2], [-2, -1], [-2,  1], [-1,  2],
];

let N;                 // board side
let visited;           // Uint8Array NxN, 1 if visited
let path;              // array of [x,y] in move order
let cx, cy;            // current knight pos
let startX, startY;    // start square (for restart)
let hintOn;            // boolean — show Warnsdorff hint this frame onward
let winT;              // frames since win (for flourish)
let pulseT;            // generic pulse for glow

let btnHint, btnUndo, btnRestart, btnSize;

function idx(x, y) { return y * N + x; }

function inBounds(x, y) { return x >= 0 && y >= 0 && x < N && y < N; }

function legalFrom(x, y) {
  const out = [];
  for (const [dx, dy] of KMOVES) {
    const nx = x + dx, ny = y + dy;
    if (inBounds(nx, ny) && !visited[idx(nx, ny)]) out.push([nx, ny]);
  }
  return out;
}

function onwardCount(x, y) {
  // After hypothetically moving to (x,y), how many legal next moves?
  // We mark (x,y) visited temporarily to be exact.
  const i = idx(x, y);
  visited[i] = 1;
  let c = 0;
  for (const [dx, dy] of KMOVES) {
    const nx = x + dx, ny = y + dy;
    if (inBounds(nx, ny) && !visited[idx(nx, ny)]) c++;
  }
  visited[i] = 0;
  return c;
}

function warnsdorffPick() {
  const opts = legalFrom(cx, cy);
  if (!opts.length) return null;
  let best = null, bestC = 99, bestD = 99;
  for (const [x, y] of opts) {
    const c = onwardCount(x, y);
    // Tie-break: prefer the square closer to a corner (canonical heuristic).
    const d = Math.min(x, N - 1 - x) + Math.min(y, N - 1 - y);
    if (c < bestC || (c === bestC && d < bestD)) {
      best = [x, y]; bestC = c; bestD = d;
    }
  }
  return best;
}

function startAt(x, y) {
  visited = new Uint8Array(N * N);
  path = [];
  cx = x; cy = y;
  startX = x; startY = y;
  visited[idx(cx, cy)] = 1;
  path.push([cx, cy]);
  winT = 0;
}

function init() {
  N = 6;
  // Default start: a corner-ish square that admits a tour on 6x6.
  startAt(0, 0);
  hintOn = false;
  pulseT = 0;
}

function undo() {
  if (path.length <= 1) return; // can't undo past start
  const [lx, ly] = path.pop();
  visited[idx(lx, ly)] = 0;
  const [px, py] = path[path.length - 1];
  cx = px; cy = py;
  winT = 0;
}

function toggleSize() {
  N = N === 6 ? 8 : 6;
  // Reset to a sane corner.
  startAt(0, 0);
}

function hit(b, x, y) {
  return b && x >= b.x && x <= b.x + b.w && y >= b.y && y <= b.y + b.h;
}

function drawButton(ctx, b, label, active, accent) {
  const bg = active ? (accent || "rgba(80,180,120,0.85)") : "rgba(40,44,68,0.85)";
  ctx.fillStyle = bg;
  ctx.fillRect(b.x, b.y, b.w, b.h);
  ctx.strokeStyle = "rgba(200,210,255,0.6)"; ctx.lineWidth = 1;
  ctx.strokeRect(b.x + 0.5, b.y + 0.5, b.w - 1, b.h - 1);
  ctx.fillStyle = "#e8ecff";
  ctx.font = "bold 12px monospace";
  ctx.textAlign = "center"; ctx.textBaseline = "middle";
  ctx.fillText(label, b.x + b.w / 2, b.y + b.h / 2);
}

// Draw a stylized knight glyph centered at (cx,cy) with size s.
function drawKnight(ctx, cxp, cyp, s, color) {
  // We render the unicode chess knight glyph; it's compact and readable on
  // both small phones and desktops.
  ctx.save();
  ctx.fillStyle = color;
  ctx.font = `bold ${Math.round(s)}px serif`;
  ctx.textAlign = "center";
  ctx.textBaseline = "middle";
  // Slight shadow so it pops on light squares.
  ctx.shadowColor = "rgba(0,0,0,0.55)";
  ctx.shadowBlur = Math.max(2, s * 0.12);
  ctx.fillText("♘", cxp, cyp + s * 0.04); // ♘
  ctx.restore();
}

function tick({ dt, time, ctx, width: W, height: H, input }) {
  pulseT += dt;

  // ----- layout -----
  const pad = 10;
  const topBar = 44;            // for buttons row
  const botInfo = 28;           // for status text
  const boardSize = Math.max(
    60,
    Math.min(W - pad * 2, H - topBar - botInfo - pad * 2)
  );
  const boardX = (W - boardSize) / 2;
  const boardY = topBar + pad;
  const cell = boardSize / N;

  // Buttons: hint | undo | restart | size — right-aligned in top bar.
  // On narrow screens we shrink button widths so they all fit.
  const minBw = 60;
  const maxBw = 92;
  const gap = 6;
  const availW = W - pad * 2;
  let bw = Math.min(maxBw, Math.floor((availW - gap * 3) / 4));
  if (bw < minBw) bw = Math.max(40, Math.floor((availW - gap * 3) / 4));
  const bh = 32;
  const btnsTotalW = bw * 4 + gap * 3;
  const btnsX = W - pad - btnsTotalW;
  const btnsY = pad;
  btnHint    = { x: btnsX + 0 * (bw + gap), y: btnsY, w: bw, h: bh };
  btnUndo    = { x: btnsX + 1 * (bw + gap), y: btnsY, w: bw, h: bh };
  btnRestart = { x: btnsX + 2 * (bw + gap), y: btnsY, w: bw, h: bh };
  btnSize    = { x: btnsX + 3 * (bw + gap), y: btnsY, w: bw, h: bh };

  // ----- input -----
  const total = N * N;
  const won = path.length === total;
  const moves = legalFrom(cx, cy);
  const stuck = !won && moves.length === 0;

  // Compute hint (Warnsdorff) target. We compute every frame so the halo
  // tracks the current state; cheap on 6x6/8x8.
  const hintMove = hintOn && !won ? warnsdorffPick() : null;

  let toggledHint = false;
  let didUndo = false;
  let didRestart = false;
  let didResize = false;
  let boardClick = null;

  const clicks = input && typeof input.consumeClicks === "function"
    ? input.consumeClicks() : [];
  for (const c of clicks) {
    if (hit(btnHint, c.x, c.y))         toggledHint = true;
    else if (hit(btnUndo, c.x, c.y))    didUndo = true;
    else if (hit(btnRestart, c.x, c.y)) didRestart = true;
    else if (hit(btnSize, c.x, c.y))    didResize = true;
    else {
      // Board click?
      const bxp = c.x - boardX;
      const byp = c.y - boardY;
      if (bxp >= 0 && byp >= 0 && bxp < boardSize && byp < boardSize) {
        boardClick = [Math.floor(bxp / cell), Math.floor(byp / cell)];
      }
    }
  }

  // Keyboard: R restart, U undo, H hint.
  if (input && typeof input.justPressed === "function") {
    if (input.justPressed("r") || input.justPressed("R")) didRestart = true;
    if (input.justPressed("u") || input.justPressed("U")) didUndo = true;
    if (input.justPressed("h") || input.justPressed("H")) toggledHint = true;
  }

  if (didResize)  toggleSize();
  if (toggledHint) hintOn = !hintOn;
  if (didUndo)    undo();
  if (didRestart) startAt(startX, startY);

  if (boardClick) {
    const [bx, by] = boardClick;
    if (visited[idx(bx, by)]) {
      // Tapping an already-visited square does nothing (cleaner UX than
      // surprise-rewind). Exception: tapping the START square restarts.
      if (bx === startX && by === startY) startAt(startX, startY);
    } else {
      // Is it a legal knight move from current pos? If yes, advance.
      let isLegal = false;
      for (const [mx, my] of moves) if (mx === bx && my === by) { isLegal = true; break; }
      if (isLegal) {
        cx = bx; cy = by;
        visited[idx(cx, cy)] = 1;
        path.push([cx, cy]);
      } else {
        // Not legal and not visited → treat as "restart from here".
        startAt(bx, by);
      }
    }
  }

  // Recompute after possible mutations. If nothing happened we can reuse
  // the `moves` we already computed at the top of this tick (saves a small
  // allocation per frame, which adds up).
  const mutated = didResize || didUndo || didRestart || boardClick !== null;
  const movesNow = mutated ? legalFrom(cx, cy) : moves;
  const wonNow = path.length === N * N;
  if (wonNow) winT += dt;

  // ----- draw background -----
  ctx.fillStyle = "#0b0b12";
  ctx.fillRect(0, 0, W, H);

  // Top bar background.
  ctx.fillStyle = "rgba(20,22,36,0.6)";
  ctx.fillRect(0, 0, W, topBar);

  // Title
  ctx.fillStyle = "#cfd6ff";
  ctx.font = "bold 14px monospace";
  ctx.textAlign = "left"; ctx.textBaseline = "top";
  ctx.fillText("Knight's Tour", pad, 9);
  ctx.font = "11px monospace";
  ctx.fillStyle = "#8a92b8";
  ctx.fillText(`${N}×${N}   ${path.length}/${N * N}`, pad, 26);

  // ----- draw board -----
  // Cell colors: light / dark chess scheme.
  const LIGHT = "#e7d6b3";
  const DARK  = "#8d6a3f";
  const LIGHT_VISITED = "#3a3a48";
  const DARK_VISITED  = "#22222c";

  for (let y = 0; y < N; y++) {
    for (let x = 0; x < N; x++) {
      const px = boardX + x * cell;
      const py = boardY + y * cell;
      const isLight = ((x + y) & 1) === 0;
      const v = visited[idx(x, y)];
      let base;
      if (v) base = isLight ? LIGHT_VISITED : DARK_VISITED;
      else   base = isLight ? LIGHT : DARK;
      ctx.fillStyle = base;
      ctx.fillRect(px, py, cell + 0.5, cell + 0.5);

      // Win flourish — color sweep across the board over ~1.5s.
      if (wonNow) {
        const diag = (x + y) / Math.max(1, (N - 1) * 2);
        const t = Math.max(0, winT - diag * 0.9);
        const a = Math.min(0.75, t * 1.8) * Math.max(0, 1 - (t - 0.6));
        if (a > 0.01) {
          const hue = (220 + (x - y) * 18 + winT * 90) % 360;
          ctx.fillStyle = `hsla(${hue},80%,60%,${a})`;
          ctx.fillRect(px, py, cell + 0.5, cell + 0.5);
        }
      }
    }
  }

  // Move-order numbers on visited squares — small, only when board is large
  // enough for them to be legible.
  if (cell >= 36) {
    ctx.font = `${Math.round(cell * 0.22)}px monospace`;
    ctx.textAlign = "left"; ctx.textBaseline = "top";
    for (let i = 0; i < path.length; i++) {
      const [x, y] = path[i];
      ctx.fillStyle = ((x + y) & 1) === 0 ? "rgba(220,220,240,0.55)" : "rgba(220,220,240,0.45)";
      ctx.fillText(String(i + 1), boardX + x * cell + 3, boardY + y * cell + 2);
    }
  }

  // Highlight legal next moves faintly.
  if (!wonNow) {
    const pulse = 0.5 + 0.5 * Math.sin(pulseT * 3);
    for (const [x, y] of movesNow) {
      const px = boardX + x * cell;
      const py = boardY + y * cell;
      ctx.fillStyle = `rgba(120,200,255,${0.10 + pulse * 0.10})`;
      ctx.fillRect(px, py, cell + 0.5, cell + 0.5);
      // Small dot in the center so the legal target is obvious even when the
      // square is light.
      ctx.fillStyle = `rgba(140,210,255,${0.55 + pulse * 0.25})`;
      ctx.beginPath();
      ctx.arc(px + cell / 2, py + cell / 2, Math.max(2, cell * 0.085), 0, Math.PI * 2);
      ctx.fill();
    }
  }

  // Path trail — thin polyline through visited squares.
  if (path.length >= 2) {
    ctx.strokeStyle = "rgba(180,200,255,0.55)";
    ctx.lineWidth = Math.max(1.2, cell * 0.04);
    ctx.lineJoin = "round";
    ctx.beginPath();
    for (let i = 0; i < path.length; i++) {
      const [x, y] = path[i];
      const px = boardX + x * cell + cell / 2;
      const py = boardY + y * cell + cell / 2;
      if (i === 0) ctx.moveTo(px, py); else ctx.lineTo(px, py);
    }
    ctx.stroke();
  }

  // Hint halo (Warnsdorff target).
  if (hintMove && !wonNow) {
    const [hx, hy] = hintMove;
    const px = boardX + hx * cell + cell / 2;
    const py = boardY + hy * cell + cell / 2;
    const r = cell * 0.45;
    const pulse = 0.5 + 0.5 * Math.sin(pulseT * 4);
    const g = ctx.createRadialGradient(px, py, r * 0.2, px, py, r);
    g.addColorStop(0, `rgba(120,255,160,${0.55 + pulse * 0.25})`);
    g.addColorStop(1, "rgba(120,255,160,0)");
    ctx.fillStyle = g;
    ctx.fillRect(px - r, py - r, r * 2, r * 2);
    ctx.strokeStyle = `rgba(140,255,170,${0.6 + pulse * 0.3})`;
    ctx.lineWidth = 2;
    ctx.beginPath();
    ctx.arc(px, py, cell * 0.36, 0, Math.PI * 2);
    ctx.stroke();
  }

  // Start-square marker.
  {
    const px = boardX + startX * cell;
    const py = boardY + startY * cell;
    ctx.strokeStyle = "rgba(255,220,120,0.85)";
    ctx.lineWidth = 2;
    ctx.strokeRect(px + 2, py + 2, cell - 4, cell - 4);
  }

  // Current-cell glow + knight glyph.
  {
    const px = boardX + cx * cell + cell / 2;
    const py = boardY + cy * cell + cell / 2;
    const pulse = 0.5 + 0.5 * Math.sin(pulseT * 3.2);
    const r = cell * 0.7;
    const g = ctx.createRadialGradient(px, py, 0, px, py, r);
    g.addColorStop(0, `rgba(255,210,120,${0.55 + pulse * 0.25})`);
    g.addColorStop(1, "rgba(255,210,120,0)");
    ctx.fillStyle = g;
    ctx.fillRect(px - r, py - r, r * 2, r * 2);
    drawKnight(ctx, px, py, cell * 0.72, "#1a1a22");
  }

  // Board border.
  ctx.strokeStyle = wonNow ? "#5fd29a" : "#3a3a48";
  ctx.lineWidth = 2;
  ctx.strokeRect(boardX - 1, boardY - 1, boardSize + 2, boardSize + 2);

  // ----- buttons -----
  drawButton(ctx, btnHint,    "hint",    hintOn, "rgba(70,160,110,0.85)");
  drawButton(ctx, btnUndo,    "undo",    false);
  drawButton(ctx, btnRestart, "restart", false);
  drawButton(ctx, btnSize,    `${N}×${N}`, false);

  // ----- bottom status -----
  ctx.textAlign = "center"; ctx.textBaseline = "alphabetic";
  ctx.font = "11px monospace";
  let msg, color;
  if (wonNow) {
    msg = "tour complete — every square visited";
    color = "#7ee2a8";
  } else if (stuck || movesNow.length === 0) {
    msg = "no legal moves — undo or tap an unvisited square to restart there";
    color = "#ffb070";
  } else {
    msg = "tap a highlighted square to move · tap unvisited to restart there";
    color = "#9aa3c7";
  }
  ctx.fillStyle = color;
  ctx.fillText(msg, W / 2, H - 9);
}

Comments (0)

Log in to comment.