769 lines
29 KiB
TypeScript
769 lines
29 KiB
TypeScript
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",
|
||
];
|