import { createRng, shuffle } from "../rng";

export interface QueensPuzzle {
  size: number;
  regions: number[][];  // regions[row][col] = regionId (0-indexed)
  solution: [number, number][];  // [row, col] per queen
}

// ── solveQueens ────────────────────────────────────────────────────────────────
function solveQueens(size: number, rng: () => number): [number, number][] | null {
  const cols: number[] = [];
  const usedCols = new Set<number>();
  const diag1 = new Set<number>();
  const diag2 = new Set<number>();
  const colOrder = shuffle(Array.from({ length: size }, (_, i) => i), rng);
  function bt(row: number): boolean {
    if (row === size) return true;
    for (const col of colOrder) {
      if (usedCols.has(col) || diag1.has(row - col) || diag2.has(row + col)) continue;
      cols[row] = col;
      usedCols.add(col); diag1.add(row - col); diag2.add(row + col);
      if (bt(row + 1)) return true;
      usedCols.delete(col); diag1.delete(row - col); diag2.delete(row + col);
    }
    return false;
  }
  if (!bt(0)) return null;
  return cols.map((col, row) => [row, col]);
}

// ── buildRegions ───────────────────────────────────────────────────────────────
// Phase 1: organic BFS from each queen in sigma order, pure adjacency, capped at targetSize
// Phase 2: remaining cells → assigned to adjacent region with HIGHEST sigmaK
function buildRegions(size: number, queens: [number, number][], rng: () => number): number[][] {
  const ADJ: [number, number][] = [[-1, 0], [1, 0], [0, -1], [0, 1]];
  const regions: number[][] = Array.from({ length: size }, () => Array(size).fill(-1));
  const regionSizes = new Int32Array(size);

  const sigma = shuffle(Array.from({ length: size }, (_, i) => i), rng);
  const sigmaK = new Int32Array(size);
  for (let k = 0; k < size; k++) sigmaK[sigma[k]] = k;

  const targetSize = size;

  for (let k = 0; k < size; k++) {
    const id = sigma[k];
    const [qr, qc] = queens[id];
    regions[qr][qc] = id;
    regionSizes[id] = 1;

    const queue: [number, number][] = [[qr, qc]];
    let head = 0;

    while (head < queue.length && regionSizes[id] < targetSize) {
      const remaining = queue.length - head;
      const pick = head + Math.floor(rng() * remaining);
      [queue[head], queue[pick]] = [queue[pick], queue[head]];
      const [r, c] = queue[head++];

      for (const [dr, dc] of ADJ) {
        const nr = r + dr, nc = c + dc;
        if (nr < 0 || nr >= size || nc < 0 || nc >= size) continue;
        if (regions[nr][nc] !== -1) continue;
        regions[nr][nc] = id;
        regionSizes[id]++;
        queue.push([nr, nc]);
        if (regionSizes[id] >= targetSize) break;
      }
    }
  }

  let changed = true;
  while (changed) {
    changed = false;
    for (let r = 0; r < size; r++)
      for (let c = 0; c < size; c++) {
        if (regions[r][c] !== -1) continue;
        let bestId = -1, bestK = -1;
        for (const [dr, dc] of ADJ) {
          const nr = r + dr, nc = c + dc;
          if (nr < 0 || nr >= size || nc < 0 || nc >= size) continue;
          const id = regions[nr][nc];
          if (id === -1) continue;
          const k = sigmaK[id];
          if (k > bestK) { bestK = k; bestId = id; }
        }
        if (bestId !== -1) { regions[r][c] = bestId; regionSizes[bestId]++; changed = true; }
      }
  }

  for (let r = 0; r < size; r++)
    for (let c = 0; c < size; c++) {
      if (regions[r][c] !== -1) continue;
      let best = 0, bestDist = Infinity;
      for (let id = 0; id < size; id++) {
        const [qr, qc] = queens[id];
        const d = Math.abs(qr - r) + Math.abs(qc - c);
        if (d < bestDist) { bestDist = d; best = id; }
      }
      regions[r][c] = best;
    }

  return regions;
}

// ── getAllPlacements ───────────────────────────────────────────────────────────
// Enumerate valid Queens-game placements (one per row, one per col,
// no two consecutive-row queens king-adjacent: |col_r - col_{r+1}| > 1).
// For large N the count grows ~10× per step; use maxP + optional rng to get
// a random sample instead of the first-in-lex-order batch.
function getAllPlacements(size: number, maxP = Infinity, rng?: () => number): Int8Array[] {
  const sols: Int8Array[] = [];
  const uc = new Uint8Array(size);
  const cols = new Array<number>(size);

  // Per-row column order (shuffled when rng provided, for random sampling)
  const colOrders: number[][] = Array.from({ length: size }, () => {
    const order = Array.from({ length: size }, (_, i) => i);
    if (rng) {
      for (let i = order.length - 1; i > 0; i--) {
        const j = (rng() * (i + 1)) | 0;
        [order[i], order[j]] = [order[j], order[i]];
      }
    }
    return order;
  });

  function bt(row: number): void {
    if (sols.length >= maxP) return;
    if (row === size) { sols.push(new Int8Array(cols)); return; }
    for (const col of colOrders[row]) {
      if (uc[col]) continue;
      if (row > 0 && Math.abs(cols[row - 1] - col) <= 1) continue;
      uc[col] = 1; cols[row] = col;
      bt(row + 1);
      uc[col] = 0;
      if (sols.length >= maxP) return;
    }
  }
  bt(0);
  return sols;
}

// ── optimizeRegions ────────────────────────────────────────────────────────────
// Iterated Local Search: greedy hill-climbing with perturbation kicks.
//
// Theory: moving cell (r,c) from region A to B affects only placements where
// the queen in row r sits at column c.
//   • vDestroyed: valid placements where region B already has another queen
//     → moving queen-r to B creates a collision → placement becomes invalid.
//   • aCreated: almost-valid placements (conflict=1) whose collision is in A
//     AND region B is empty → moving queen-r from A to B resolves the collision.
// Accept swaps where vDestroyed > aCreated (net reduction in valid count).
// When stuck, apply random "kick" swaps, then resume greedy from the best state.
function optimizeRegions(
  size: number,
  regions: number[][],
  queens: [number, number][],
  placements: Int8Array[],
  rng: () => number
): boolean {
  const ADJ: [number, number][] = [[-1, 0], [1, 0], [0, -1], [0, 1]];
  const P = placements.length;

  // Queen cell lookup
  const isQueen = new Uint8Array(size * size);
  for (const [r, c] of queens) isQueen[r * size + c] = 1;

  // Region cell lists — kept in sync after every swap
  const regCells: [number, number][][] = Array.from({ length: size }, () => []);
  for (let r = 0; r < size; r++)
    for (let c = 0; c < size; c++)
      regCells[regions[r][c]].push([r, c]);

  // Reusable buffers
  const conflictOf = new Uint8Array(P);
  const visitBuf = new Uint8Array(size * size);
  const queueBuf = new Int32Array(size * size);

  function recomputeConflicts(): void {
    for (let p = 0; p < P; p++) {
      const pl = placements[p];
      const regCount = new Uint8Array(size);
      let conf = 0;
      for (let r = 0; r < size; r++) {
        const reg = regions[r][pl[r]];
        if (++regCount[reg] === 2) { conf++; if (conf >= 2) break; }
      }
      conflictOf[p] = conf;
    }
  }

  function countCurrentValid(): number {
    let cnt = 0;
    for (let p = 0; p < P; p++) if (conflictOf[p] === 0) cnt++;
    return cnt;
  }

  function isConnectedWithout(regId: number, remR: number, remC: number): boolean {
    const [qr, qc] = queens[regId];
    const target = regCells[regId].length - 1;
    if (target <= 1) return true;
    visitBuf.fill(0);
    const start = qr * size + qc;
    visitBuf[start] = 1;
    queueBuf[0] = start;
    let head = 0, tail = 1, count = 1;
    while (head < tail) {
      const idx = queueBuf[head++];
      const r = (idx / size) | 0, c = idx % size;
      for (const [dr, dc] of ADJ) {
        const nr = r + dr, nc = c + dc;
        if (nr < 0 || nr >= size || nc < 0 || nc >= size) continue;
        if (regions[nr][nc] !== regId || (nr === remR && nc === remC)) continue;
        const key = nr * size + nc;
        if (visitBuf[key]) continue;
        visitBuf[key] = 1;
        queueBuf[tail++] = key;
        if (++count === target) return true;
      }
    }
    return count === target;
  }

  function applySwap(r: number, c: number, newReg: number): void {
    const oldReg = regions[r][c];
    const idx = regCells[oldReg].findIndex(([rr, cc]) => rr === r && cc === c);
    if (idx !== -1) regCells[oldReg].splice(idx, 1);
    regCells[newReg].push([r, c]);
    regions[r][c] = newReg;
  }

  // Run one pass of greedy hill-climbing.
  // Returns number of improvements applied (0 = stuck).
  function greedyPass(shuffledCells: [number, number][]): number {
    recomputeConflicts();
    const validIdx: number[] = [], almostIdx: number[] = [];
    for (let p = 0; p < P; p++) {
      if (conflictOf[p] === 0) validIdx.push(p);
      else if (conflictOf[p] === 1) almostIdx.push(p);
    }
    if (validIdx.length <= 1) return 0; // done or impossible

    const byCRValid: number[][] = Array.from({ length: size * size }, () => []);
    const byCRAlmost: number[][] = Array.from({ length: size * size }, () => []);
    for (const p of validIdx) {
      const pl = placements[p];
      for (let r = 0; r < size; r++) byCRValid[r * size + pl[r]].push(p);
    }
    for (const p of almostIdx) {
      const pl = placements[p];
      for (let r = 0; r < size; r++) byCRAlmost[r * size + pl[r]].push(p);
    }

    const pMask = new Int32Array(P);
    for (const p of validIdx) {
      const pl = placements[p];
      let m = 0;
      for (let r = 0; r < size; r++) m |= (1 << regions[r][pl[r]]);
      pMask[p] = m;
    }
    for (const p of almostIdx) {
      const pl = placements[p];
      let m = 0;
      for (let r = 0; r < size; r++) m |= (1 << regions[r][pl[r]]);
      pMask[p] = m;
    }

    const almostColReg = new Int8Array(P).fill(-1);
    for (const p of almostIdx) {
      const pl = placements[p];
      const regCount = new Uint8Array(size);
      for (let r = 0; r < size; r++) {
        const reg = regions[r][pl[r]];
        if (++regCount[reg] === 2) { almostColReg[p] = reg; break; }
      }
    }

    // Best-improvement: scan all cells, find globally best swap
    let bestDelta = 0, bestR = -1, bestC = -1, bestNewReg = -1;

    for (const [r, c] of shuffledCells) {
      const oldReg = regions[r][c];
      const adjRegs: number[] = [];
      for (const [dr, dc] of ADJ) {
        const nr = r + dr, nc = c + dc;
        if (nr < 0 || nr >= size || nc < 0 || nc >= size) continue;
        const ar = regions[nr][nc];
        if (ar !== oldReg && !adjRegs.includes(ar)) adjRegs.push(ar);
      }
      if (adjRegs.length === 0 || !isConnectedWithout(oldReg, r, c)) continue;

      const validHere = byCRValid[r * size + c];
      const almostHere = byCRAlmost[r * size + c];

      for (const newReg of adjRegs) {
        let vDestroyed = 0;
        for (const p of validHere) if ((pMask[p] >> newReg) & 1) vDestroyed++;
        let aCreated = 0;
        for (const p of almostHere)
          if (almostColReg[p] === oldReg && !((pMask[p] >> newReg) & 1)) aCreated++;
        const delta = vDestroyed - aCreated;
        if (delta > bestDelta) { bestDelta = delta; bestR = r; bestC = c; bestNewReg = newReg; }
      }
    }

    if (bestR === -1) return 0; // stuck
    applySwap(bestR, bestC, bestNewReg);
    return 1;
  }

  // Run greedy until stuck; return current valid count
  function runGreedy(): number {
    const cells: [number, number][] = [];
    for (let r = 0; r < size; r++)
      for (let c = 0; c < size; c++)
        if (!isQueen[r * size + c]) cells.push([r, c]);

    for (let round = 0; round < 300; round++) {
      // Shuffle for variety
      for (let i = cells.length - 1; i > 0; i--) {
        const j = (rng() * (i + 1)) | 0;
        [cells[i], cells[j]] = [cells[j], cells[i]];
      }
      recomputeConflicts();
      const vc = countCurrentValid();
      if (vc <= 1) return vc;
      if (greedyPass(cells) === 0) break;
    }
    recomputeConflicts();
    return countCurrentValid();
  }

  // Apply K random connectivity-preserving swaps (kick)
  function kick(K: number): void {
    const cells: [number, number][] = [];
    for (let r = 0; r < size; r++)
      for (let c = 0; c < size; c++)
        if (!isQueen[r * size + c]) cells.push([r, c]);
    // Shuffle
    for (let i = cells.length - 1; i > 0; i--) {
      const j = (rng() * (i + 1)) | 0;
      [cells[i], cells[j]] = [cells[j], cells[i]];
    }

    let applied = 0;
    for (const [r, c] of cells) {
      if (applied >= K) break;
      const oldReg = regions[r][c];
      const adjRegs: number[] = [];
      for (const [dr, dc] of ADJ) {
        const nr = r + dr, nc = c + dc;
        if (nr < 0 || nr >= size || nc < 0 || nc >= size) continue;
        const ar = regions[nr][nc];
        if (ar !== oldReg && !adjRegs.includes(ar)) adjRegs.push(ar);
      }
      if (adjRegs.length === 0 || !isConnectedWithout(oldReg, r, c)) continue;
      const newReg = adjRegs[(rng() * adjRegs.length) | 0];
      applySwap(r, c, newReg);
      applied++;
    }
  }

  // Snapshot helpers
  function snapshot(): number[][] {
    return regions.map(row => [...row]);
  }
  function restore(snap: number[][]): void {
    for (let r = 0; r < size; r++)
      for (let c = 0; c < size; c++)
        regions[r][c] = snap[r][c];
    regCells.forEach(rc => rc.length = 0);
    for (let r = 0; r < size; r++)
      for (let c = 0; c < size; c++)
        regCells[regions[r][c]].push([r, c]);
  }

  // Scale kick budget with sample size: more kicks for smaller P (more reliable)
  const MAX_KICKS = P <= 10000 ? 15 : P <= 100000 ? 40 : 20;

  // ILS: run greedy, kick when stuck, restore best if worsened
  let bestSnap = snapshot();
  let bestValid = runGreedy();
  if (bestValid <= 1) return bestValid === 1;

  for (let k = 0; k < MAX_KICKS; k++) {
    restore(bestSnap);
    kick(2 + (k % 3)); // vary kick size 2-4
    const vc = runGreedy();
    if (vc === 1) return true;
    if (vc < bestValid) {
      bestValid = vc;
      bestSnap = snapshot();
    }
  }

  restore(bestSnap);
  recomputeConflicts();
  return countCurrentValid() === 1;
}

// ── optimizeRegionsLargeN ──────────────────────────────────────────────────────
// Solution-separation optimizer for large N (≥10) where enumerating all
// placements is too expensive.
//
// Strategy: repeatedly find a spurious solution S2 (via backtracking) and apply
// a targeted "separation swap" that creates a region conflict for S2 without
// breaking the intended solution S1. When no targeted swap exists, apply a
// random kick, then retry.
function optimizeRegionsLargeN(
  size: number,
  regions: number[][],
  queens: [number, number][],
  solution: [number, number][],
  rng: () => number
): boolean {
  const ADJ: [number, number][] = [[-1, 0], [1, 0], [0, -1], [0, 1]];
  const isQueen = new Uint8Array(size * size);
  for (const [r, c] of queens) isQueen[r * size + c] = 1;

  const regCells: [number, number][][] = Array.from({ length: size }, () => []);
  for (let r = 0; r < size; r++)
    for (let c = 0; c < size; c++)
      regCells[regions[r][c]].push([r, c]);

  const visitBuf = new Uint8Array(size * size);
  const queueBuf = new Int32Array(size * size);

  function isConnectedWithout(regId: number, remR: number, remC: number): boolean {
    const [qr, qc] = queens[regId];
    const target = regCells[regId].length - 1;
    if (target <= 1) return true;
    visitBuf.fill(0);
    const start = qr * size + qc;
    visitBuf[start] = 1; queueBuf[0] = start;
    let head = 0, tail = 1, count = 1;
    while (head < tail) {
      const idx = queueBuf[head++];
      const r = (idx / size) | 0, c = idx % size;
      for (const [dr, dc] of ADJ) {
        const nr = r + dr, nc = c + dc;
        if (nr < 0 || nr >= size || nc < 0 || nc >= size) continue;
        if (regions[nr][nc] !== regId || (nr === remR && nc === remC)) continue;
        const key = nr * size + nc;
        if (visitBuf[key]) continue;
        visitBuf[key] = 1; queueBuf[tail++] = key;
        if (++count === target) return true;
      }
    }
    return count === target;
  }

  function applySwap(r: number, c: number, newReg: number): void {
    const oldReg = regions[r][c];
    const idx = regCells[oldReg].findIndex(([rr, cc]) => rr === r && cc === c);
    if (idx !== -1) regCells[oldReg].splice(idx, 1);
    regCells[newReg].push([r, c]);
    regions[r][c] = newReg;
  }

  // Find a spurious (non-solution) valid placement via backtracking.
  // Returns the spurious placement's column array, or null if unique.
  const solCols = solution.map(([, c]) => c);
  function findSpurious(): number[] | null {
    const uc = new Uint8Array(size), ur = new Uint8Array(size);
    const pR = new Int32Array(size), pC = new Int32Array(size);
    let found: number[] | null = null, depth = 0;
    function bt(row: number): void {
      if (found) return;
      if (row === size) {
        for (let r = 0; r < size; r++) if (pC[r] !== solCols[r]) { found = [...pC]; return; }
        return; // this IS the game solution
      }
      for (let col = 0; col < size; col++) {
        if (uc[col]) continue;
        const reg = regions[row][col];
        if (ur[reg]) continue;
        let adj = false;
        for (let i = 0; i < depth; i++)
          if (Math.abs(row - pR[i]) <= 1 && Math.abs(col - pC[i]) <= 1) { adj = true; break; }
        if (adj) continue;
        uc[col] = 1; ur[reg] = 1; pR[depth] = row; pC[depth] = col; depth++;
        bt(row + 1);
        depth--; uc[col] = 0; ur[reg] = 0;
        if (found) return;
      }
    }
    bt(0);
    return found;
  }

  // Try to separate spurious S2 from the game solution by swapping a cell
  // at position (r, S2[r]) — where S2's queen sits but S1's doesn't — into
  // an adjacent region already occupied by S2, creating a collision for S2.
  function eliminate(s2cols: number[]): boolean {
    const s2regSet = new Set(s2cols.map((c, r) => regions[r][c]));
    // Shuffle row order for variety
    const rows = Array.from({ length: size }, (_, i) => i);
    for (let i = rows.length - 1; i > 0; i--) {
      const j = (rng() * (i + 1)) | 0;
      [rows[i], rows[j]] = [rows[j], rows[i]];
    }
    for (const r of rows) {
      const c = s2cols[r];
      if (solCols[r] === c) continue;  // S1 also has queen here — skip
      if (isQueen[r * size + c]) continue;  // it's the game queen cell — never move
      const oldReg = regions[r][c];
      // Check connectivity before the loop (avoid redundant BFS per adjacent region)
      if (!isConnectedWithout(oldReg, r, c)) continue;
      for (const [dr, dc] of ADJ) {
        const nr = r + dr, nc = c + dc;
        if (nr < 0 || nr >= size || nc < 0 || nc >= size) continue;
        const adjReg = regions[nr][nc];
        if (adjReg === oldReg) continue;
        // adjReg is occupied in S2 → moving (r,c) to adjReg creates a collision for S2
        if (s2regSet.has(adjReg)) {
          applySwap(r, c, adjReg);
          return true;
        }
      }
    }
    return false;
  }

  // Random connectivity-preserving kick
  function kick(K: number): void {
    const cells: [number, number][] = [];
    for (let r = 0; r < size; r++)
      for (let c = 0; c < size; c++)
        if (!isQueen[r * size + c]) cells.push([r, c]);
    for (let i = cells.length - 1; i > 0; i--) {
      const j = (rng() * (i + 1)) | 0;
      [cells[i], cells[j]] = [cells[j], cells[i]];
    }
    let applied = 0;
    for (const [r, c] of cells) {
      if (applied >= K) break;
      const oldReg = regions[r][c];
      const adjRegs: number[] = [];
      for (const [dr, dc] of ADJ) {
        const nr = r + dr, nc = c + dc;
        if (nr < 0 || nr >= size || nc < 0 || nc >= size) continue;
        const ar = regions[nr][nc];
        if (ar !== oldReg && !adjRegs.includes(ar)) adjRegs.push(ar);
      }
      if (adjRegs.length === 0 || !isConnectedWithout(oldReg, r, c)) continue;
      applySwap(r, c, adjRegs[(rng() * adjRegs.length) | 0]);
      applied++;
    }
  }

  const MAX_ITERS = 300;
  let kicksWithoutProgress = 0;

  for (let iter = 0; iter < MAX_ITERS; iter++) {
    const s2 = findSpurious();
    if (!s2) return true;            // unique!

    if (!eliminate(s2)) {
      kick(2 + (kicksWithoutProgress % 3));
      kicksWithoutProgress++;
      if (kicksWithoutProgress > 30) return false; // hopelessly stuck
    } else {
      kicksWithoutProgress = 0;
    }
  }
  return false;
}

// ── genCombinations ───────────────────────────────────────────────────────────
function* genCombinations(arr: number[], n: number, start = 0): Generator<number[]> {
  if (n === 0) { yield []; return; }
  for (let i = start; i <= arr.length - n; i++)
    for (const rest of genCombinations(arr, n - 1, i + 1))
      yield [arr[i], ...rest];
}

// ── isLogicallySolvable ────────────────────────────────────────────────────────
// Returns true iff the puzzle can be solved by pure constraint propagation
// (no guessing). Same rules as the hint finder in QueensBoard.tsx.
function isLogicallySolvable(size: number, regions: number[][]): boolean {
  const poss = new Uint8Array(size * size).fill(1);
  const doneRows = new Uint8Array(size);
  const doneRegs = new Uint8Array(size);

  function placeQueen(r: number, c: number) {
    const reg = regions[r][c];
    doneRows[r] = 1;
    doneRegs[reg] = 1;
    for (let i = 0; i < size; i++) {
      poss[r * size + i] = 0; // same row
      poss[i * size + c] = 0; // same col
    }
    for (let rr = 0; rr < size; rr++)
      for (let cc = 0; cc < size; cc++)
        if (regions[rr][cc] === reg || (Math.abs(rr - r) <= 1 && Math.abs(cc - c) <= 1))
          poss[rr * size + cc] = 0;
  }

  let placed = 0;
  let progress = true;
  while (placed < size && progress) {
    progress = false;

    // Rules 1-3: naked singles (region / row / col)
    for (let id = 0; id < size; id++) {
      if (doneRegs[id]) continue;
      let fr = -1, fc = -1, cnt = 0;
      for (let r = 0; r < size; r++)
        for (let c = 0; c < size; c++)
          if (regions[r][c] === id && poss[r * size + c]) { fr = r; fc = c; cnt++; }
      if (cnt === 1) { placeQueen(fr, fc); placed++; progress = true; }
    }
    for (let r = 0; r < size; r++) {
      if (doneRows[r]) continue;
      let fc = -1, cnt = 0;
      for (let c = 0; c < size; c++) if (poss[r * size + c]) { fc = c; cnt++; }
      if (cnt === 1 && fc !== -1) { placeQueen(r, fc); placed++; progress = true; }
    }
    for (let c = 0; c < size; c++) {
      let fr = -1, cnt = 0;
      for (let r = 0; r < size; r++) if (!doneRows[r] && poss[r * size + c]) { fr = r; cnt++; }
      if (cnt === 1 && fr !== -1) { placeQueen(fr, c); placed++; progress = true; }
    }

    // Rule 4: N-subset — N regions confined to N rows or N cols
    if (!progress) {
      const unreg: number[] = [];
      for (let id = 0; id < size; id++) {
        if (doneRegs[id]) continue;
        let ok = false;
        for (let r = 0; r < size && !ok; r++)
          for (let c = 0; c < size && !ok; c++)
            if (regions[r][c] === id && poss[r * size + c]) ok = true;
        if (ok) unreg.push(id);
      }
      outer:
      for (let n = 1; n < unreg.length; n++) {
        for (const combo of genCombinations(unreg, n)) {
          const comboSet = new Set(combo);
          const rowSet = new Set<number>(), colSet = new Set<number>();
          for (const id of combo)
            for (let r = 0; r < size; r++)
              for (let c = 0; c < size; c++)
                if (regions[r][c] === id && poss[r * size + c]) { rowSet.add(r); colSet.add(c); }

          if (rowSet.size === n) {
            let changed = false;
            for (const row of rowSet)
              for (let c = 0; c < size; c++)
                if (poss[row * size + c] && !comboSet.has(regions[row][c])) { poss[row * size + c] = 0; changed = true; }
            if (changed) { progress = true; break outer; }
          }
          if (colSet.size === n) {
            let changed = false;
            for (const col of colSet)
              for (let r = 0; r < size; r++)
                if (poss[r * size + col] && !comboSet.has(regions[r][col])) { poss[r * size + col] = 0; changed = true; }
            if (changed) { progress = true; break outer; }
          }
        }
      }
    }
  }
  return placed === size;
}

// ── isUnique ───────────────────────────────────────────────────────────────────
// Backtracking check — kept as fallback when optimizeRegions cannot find uniqueness.
function isUnique(size: number, regions: number[][]): boolean {
  const usedCols = new Uint8Array(size);
  const usedRegs = new Uint8Array(size);
  const placedR = new Int32Array(size);
  const placedC = new Int32Array(size);
  let depth = 0;
  let count = 0;

  function bt(row: number): void {
    if (count > 1) return;
    if (row === size) { count++; return; }
    for (let col = 0; col < size; col++) {
      if (usedCols[col]) continue;
      const reg = regions[row][col];
      if (usedRegs[reg]) continue;
      let adj = false;
      for (let i = 0; i < depth; i++)
        if (Math.abs(row - placedR[i]) <= 1 && Math.abs(col - placedC[i]) <= 1) { adj = true; break; }
      if (adj) continue;
      usedCols[col] = 1; usedRegs[reg] = 1;
      placedR[depth] = row; placedC[depth] = col; depth++;
      bt(row + 1);
      depth--; usedCols[col] = 0; usedRegs[reg] = 0;
      if (count > 1) return;
    }
  }

  bt(0);
  return count === 1;
}

// ── Public exports ─────────────────────────────────────────────────────────────

export function queensSizeForDate(date: string): number {
  const start = new Date("2024-01-01").getTime();
  const d = new Date(date).getTime();
  const days = Math.max(0, Math.floor((d - start) / 86400000));
  if (days < 100) return 6;
  if (days < 400) return 7;
  if (days < 900) return 8;
  if (days < 1400) return 9;
  return 10;
}

export function generateQueens(date: string, size?: number): QueensPuzzle {
  const resolvedSize = size ?? queensSizeForDate(date);
  const baseSeed = date.split("-").reduce((a, n) => a * 1000 + parseInt(n), 0);

  // N ≤ 9: enumerate all placements once (fast).
  // N ≥ 10: use solution-separation optimizer (no placements enumeration needed).
  const largeN = resolvedSize >= 10;
  const allPlacements = largeN ? null : getAllPlacements(resolvedSize);

  // Tier 1: unique + logically solvable (no guessing needed)
  // Tier 2: unique only (may require guessing — hint finder will always find something)
  let fallbackUnique: QueensPuzzle | null = null;

  const MAX_ATTEMPTS = largeN ? 30 : 20;

  for (let attempt = 0; attempt < MAX_ATTEMPTS; attempt++) {
    const rng1 = createRng(baseSeed + attempt * 1000003);
    const solution = solveQueens(resolvedSize, rng1)!;
    const regions = buildRegions(resolvedSize, solution, rng1);

    // Deep-copy regions before optimization (mutates in-place)
    const regCopy = regions.map(row => [...row]);
    const rng2 = createRng(baseSeed + attempt * 999983 + 42);

    const optimized = largeN
      ? optimizeRegionsLargeN(resolvedSize, regCopy, solution, solution, rng2)
      : optimizeRegions(resolvedSize, regCopy, solution, allPlacements!, rng2);

    if (optimized) {
      // Best case: unique + logically solvable
      if (isLogicallySolvable(resolvedSize, regCopy)) {
        return { size: resolvedSize, regions: regCopy, solution };
      }
      // Keep as tier-2 fallback (unique but may need guessing)
      if (!fallbackUnique) fallbackUnique = { size: resolvedSize, regions: regCopy, solution };
    }

    // Also save non-optimized unique puzzles as tier-2 fallback
    if (!fallbackUnique && isUnique(resolvedSize, regions)) {
      fallbackUnique = { size: resolvedSize, regions, solution };
    }
  }

  if (fallbackUnique) return fallbackUnique;

  // Absolute last resort (should never reach here in practice)
  const rng = createRng(baseSeed);
  const solution = solveQueens(resolvedSize, rng)!;
  const regions = buildRegions(resolvedSize, solution, rng);
  return { size: resolvedSize, regions, solution };
}

export const QUEEN_COLORS = [
  "#e63946", "#f4a261", "#2a9d8f", "#457b9d",
  "#6a4c93", "#264653", "#e9c46a", "#8ecae6",
];