N-Queens Backtracking

// N-queens backtracking visualization.
// DFS places queens row by row; backs up on conflict.
// Once all 92 solutions are found, cycles through them.

const N = 8;
let queens;        // queens[row] = col, or -1 if not placed
let row;           // current row being considered (0..N)
let col;           // current column being tested in that row
let solutions;     // array of arrays (each length N)
let foundAll;
let cycleIdx;
let cycleAcc;
let steps;
let backtracks;
let lastEvent;     // 'try' | 'place' | 'conflict' | 'solution' | 'backtrack'
let lastRow, lastCol;
let conflictCells; // [{r,c}] cells highlighted as causing conflict
let paused;
let stepsPerFrame;
let phase;         // 'search' or 'cycle'

function conflicts(r, c) {
  // Returns the row index of a queen that conflicts with (r,c), or -1.
  for (let i = 0; i < r; i++) {
    const qc = queens[i];
    if (qc === c) return i;
    if (Math.abs(qc - c) === r - i) return i;
  }
  return -1;
}

function init() {
  queens = new Int8Array(N);
  for (let i = 0; i < N; i++) queens[i] = -1;
  row = 0;
  col = 0;
  solutions = [];
  foundAll = false;
  cycleIdx = 0;
  cycleAcc = 0;
  steps = 0;
  backtracks = 0;
  lastEvent = "try";
  lastRow = 0;
  lastCol = 0;
  conflictCells = [];
  paused = false;
  stepsPerFrame = 6;
  phase = "search";
}

function searchStep() {
  if (foundAll) return;
  steps++;
  if (row === N) {
    // Full placement found
    const snap = new Int8Array(N);
    for (let i = 0; i < N; i++) snap[i] = queens[i];
    solutions.push(snap);
    lastEvent = "solution";
    // Begin backtrack
    row = N - 1;
    col = queens[row] + 1;
    queens[row] = -1;
    if (solutions.length >= 92) {
      foundAll = true;
      phase = "cycle";
    }
    return;
  }
  if (col >= N) {
    // No column works in this row — backtrack.
    backtracks++;
    queens[row] = -1;
    row--;
    if (row < 0) {
      // Exhausted entire tree
      foundAll = true;
      phase = "cycle";
      return;
    }
    col = queens[row] + 1;
    queens[row] = -1;
    lastEvent = "backtrack";
    lastRow = row;
    lastCol = col;
    return;
  }
  lastRow = row;
  lastCol = col;
  const conf = conflicts(row, col);
  if (conf === -1) {
    queens[row] = col;
    lastEvent = "place";
    conflictCells = [];
    row++;
    col = 0;
  } else {
    lastEvent = "conflict";
    conflictCells = [{ r: conf, c: queens[conf] }];
    col++;
  }
}

function drawQueen(ctx, x, y, s, color) {
  // Stylized crown glyph drawn with primitives.
  ctx.fillStyle = color;
  const cx = x + s / 2;
  const cy = y + s / 2;
  const r = s * 0.28;
  // Body
  ctx.beginPath();
  ctx.arc(cx, cy + r * 0.55, r * 0.55, 0, Math.PI * 2);
  ctx.fill();
  // Crown trapezoid
  ctx.beginPath();
  ctx.moveTo(cx - r, cy + r * 0.2);
  ctx.lineTo(cx + r, cy + r * 0.2);
  ctx.lineTo(cx + r * 0.75, cy - r * 0.5);
  ctx.lineTo(cx - r * 0.75, cy - r * 0.5);
  ctx.closePath();
  ctx.fill();
  // Spikes
  ctx.beginPath();
  ctx.moveTo(cx - r * 0.75, cy - r * 0.5);
  ctx.lineTo(cx - r * 0.9, cy - r * 1.1);
  ctx.lineTo(cx - r * 0.35, cy - r * 0.65);
  ctx.lineTo(cx, cy - r * 1.2);
  ctx.lineTo(cx + r * 0.35, cy - r * 0.65);
  ctx.lineTo(cx + r * 0.9, cy - r * 1.1);
  ctx.lineTo(cx + r * 0.75, cy - r * 0.5);
  ctx.closePath();
  ctx.fill();
}

function tick({ ctx, width: W, height: H, input }) {
  // Input: space or tap toggles pause; r resets.
  if (input && input.justPressed) {
    if (input.justPressed(" ") || input.justPressed("Space") || input.justPressed("Spacebar")) {
      paused = !paused;
    }
    if (input.justPressed("r") || input.justPressed("R")) init();
  }
  if (input && input.consumeClicks) {
    const clicks = input.consumeClicks();
    if (clicks && clicks > 0) paused = !paused;
  }

  if (!paused) {
    if (phase === "search") {
      for (let i = 0; i < stepsPerFrame; i++) {
        searchStep();
        if (phase === "cycle") break;
      }
    } else {
      cycleAcc += 1;
      if (cycleAcc >= 45) {
        cycleAcc = 0;
        cycleIdx = (cycleIdx + 1) % solutions.length;
        const s = solutions[cycleIdx];
        for (let i = 0; i < N; i++) queens[i] = s[i];
        lastRow = -1;
        lastCol = -1;
        conflictCells = [];
      }
    }
  }

  // Layout — board is centered square, HUD on the side or top.
  const hudH = 56;
  const boardSize = Math.min(W - 16, H - hudH - 16);
  const bx = ((W - boardSize) / 2) | 0;
  const by = hudH + (((H - hudH) - boardSize) / 2) | 0;
  const cell = boardSize / N;

  // Background
  ctx.fillStyle = "#0a0a12";
  ctx.fillRect(0, 0, W, H);

  // Board squares
  for (let r = 0; r < N; r++) {
    for (let c = 0; c < N; c++) {
      const light = ((r + c) & 1) === 0;
      ctx.fillStyle = light ? "#2a2540" : "#16142a";
      ctx.fillRect(bx + c * cell, by + r * cell, cell + 0.5, cell + 0.5);
    }
  }

  // Highlight current row band (while searching)
  if (phase === "search" && lastRow >= 0 && lastRow < N) {
    ctx.fillStyle = "rgba(255,255,255,0.04)";
    ctx.fillRect(bx, by + lastRow * cell, boardSize, cell);
  }

  // Conflict cells (the existing queen(s) that block)
  for (const cc of conflictCells) {
    ctx.fillStyle = "rgba(255, 70, 90, 0.45)";
    ctx.fillRect(bx + cc.c * cell, by + cc.r * cell, cell, cell);
  }

  // Currently considered cell
  if (phase === "search" && lastRow >= 0 && lastRow < N && lastCol >= 0 && lastCol < N) {
    let stroke = "#ffd84a";
    if (lastEvent === "conflict") stroke = "#ff5572";
    else if (lastEvent === "place") stroke = "#5cffae";
    else if (lastEvent === "backtrack") stroke = "#a070ff";
    ctx.strokeStyle = stroke;
    ctx.lineWidth = 2.5;
    ctx.strokeRect(bx + lastCol * cell + 1, by + lastRow * cell + 1, cell - 2, cell - 2);
  }

  // Diagonals from the considered cell (faint guide)
  if (phase === "search" && lastEvent !== "backtrack" && lastRow >= 0 && lastRow < N && lastCol >= 0 && lastCol < N) {
    ctx.strokeStyle = "rgba(255,216,74,0.18)";
    ctx.lineWidth = 1;
    const cx = bx + lastCol * cell + cell / 2;
    const cy = by + lastRow * cell + cell / 2;
    // Column
    ctx.beginPath();
    ctx.moveTo(cx, by);
    ctx.lineTo(cx, by + boardSize);
    ctx.stroke();
    // Diagonals
    ctx.beginPath();
    ctx.moveTo(cx - boardSize, cy - boardSize);
    ctx.lineTo(cx + boardSize, cy + boardSize);
    ctx.moveTo(cx - boardSize, cy + boardSize);
    ctx.lineTo(cx + boardSize, cy - boardSize);
    ctx.stroke();
  }

  // Queens
  for (let r = 0; r < N; r++) {
    const c = queens[r];
    if (c < 0) continue;
    const color = phase === "cycle" ? "#9fffd9" : "#f0f0ff";
    drawQueen(ctx, bx + c * cell, by + r * cell, cell, color);
  }

  // Board border
  ctx.strokeStyle = "#3a3560";
  ctx.lineWidth = 1;
  ctx.strokeRect(bx + 0.5, by + 0.5, boardSize, boardSize);

  // HUD
  ctx.fillStyle = "#f4f4ff";
  ctx.font = "bold 14px monospace";
  ctx.fillText(`N-Queens · N=${N}`, 10, 20);
  ctx.font = "12px monospace";
  ctx.fillStyle = "#c7c7e0";
  const placed = queens.reduce((a, v) => a + (v >= 0 ? 1 : 0), 0);
  const line1 = `steps ${steps}  backtracks ${backtracks}  placed ${placed}/${N}`;
  ctx.fillText(line1, 10, 38);
  const sols = solutions.length;
  const phaseTxt = phase === "cycle" ? `cycling ${cycleIdx + 1}/${sols}` : `searching · ${sols}/92 found`;
  ctx.fillText(phaseTxt + (paused ? "  [PAUSED]" : ""), 10, 52);

  // Right-side legend (only if wide enough)
  if (W >= 360) {
    ctx.textAlign = "right";
    ctx.fillStyle = "#9aa0c8";
    ctx.font = "11px monospace";
    ctx.fillText("tap/space pause · r reset", W - 10, 20);
    ctx.fillStyle = "#5cffae"; ctx.fillText("place", W - 10, 36);
    ctx.fillStyle = "#ff5572"; ctx.fillText("conflict", W - 10, 50);
    ctx.textAlign = "left";
  }
}