177 lines
6.7 KiB
JavaScript
177 lines
6.7 KiB
JavaScript
// Offline generator for Katamino puzzle bank.
|
||
//
|
||
// For each Penta level N (3–12) it enumerates every C(12, N) combination of
|
||
// the 12 standard pentominoes and runs a backtracking solver to check whether
|
||
// that set can tile a 5×N rectangle. Valid combinations become the puzzle bank.
|
||
//
|
||
// Usage:
|
||
// node server/scripts/genKatamino.js [outFile]
|
||
|
||
import fs from 'node:fs';
|
||
import path from 'node:path';
|
||
import { fileURLToPath } from 'node:url';
|
||
|
||
const __dirname = path.dirname(fileURLToPath(import.meta.url));
|
||
const OUT_FILE = process.argv[2]
|
||
? path.resolve(process.argv[2])
|
||
: path.join(__dirname, '../data/katamino.json');
|
||
|
||
const ROWS = 5;
|
||
|
||
const PIECES = [
|
||
{ id: 'F', cells: [[0,1],[0,2],[1,0],[1,1],[2,1]] },
|
||
{ id: 'I', cells: [[0,0],[1,0],[2,0],[3,0],[4,0]] },
|
||
{ id: 'L', cells: [[0,0],[1,0],[2,0],[3,0],[3,1]] },
|
||
{ id: 'N', cells: [[0,0],[1,0],[2,0],[2,1],[3,1]] },
|
||
{ id: 'P', cells: [[0,0],[0,1],[1,0],[1,1],[2,0]] },
|
||
{ id: 'T', cells: [[0,0],[0,1],[0,2],[1,1],[2,1]] },
|
||
{ id: 'U', cells: [[0,0],[0,1],[1,0],[2,0],[2,1]] },
|
||
{ id: 'V', cells: [[0,0],[1,0],[2,0],[2,1],[2,2]] },
|
||
{ id: 'W', cells: [[0,0],[1,0],[1,1],[2,1],[2,2]] },
|
||
{ id: 'X', cells: [[0,1],[1,0],[1,1],[1,2],[2,1]] },
|
||
{ id: 'Y', cells: [[0,0],[1,0],[1,1],[2,0],[3,0]] },
|
||
{ id: 'Z', cells: [[0,0],[0,1],[1,1],[2,1],[2,2]] },
|
||
];
|
||
|
||
// ── Orientation precompute ────────────────────────────────────────────────────
|
||
|
||
function normalize(cells) {
|
||
let minR = Infinity, minC = Infinity;
|
||
for (const [r, c] of cells) { if (r < minR) minR = r; if (c < minC) minC = c; }
|
||
return cells.map(([r, c]) => [r - minR, c - minC]).sort((a, b) => a[0] - b[0] || a[1] - b[1]);
|
||
}
|
||
|
||
function keyOf(cells) { return cells.map(([r, c]) => `${r},${c}`).join(';'); }
|
||
|
||
function computeOrientations(cells) {
|
||
const seen = new Map();
|
||
const base = cells.map(([r, c]) => [r, c]);
|
||
for (let flip = 0; flip < 2; flip++) {
|
||
let work = flip ? base.map(([r, c]) => [r, -c]) : base;
|
||
for (let rot = 0; rot < 4; rot++) {
|
||
const norm = normalize(work);
|
||
const k = keyOf(norm);
|
||
if (!seen.has(k)) seen.set(k, norm);
|
||
work = work.map(([r, c]) => [c, -r]);
|
||
}
|
||
}
|
||
return [...seen.values()];
|
||
}
|
||
|
||
// Pre-flatten each orientation to [r0,c0, r1,c1, ...] for fast access
|
||
const ORIS_BY_ID = Object.fromEntries(
|
||
PIECES.map(p => [p.id, computeOrientations(p.cells).map(cells => {
|
||
const flat = new Int8Array(10);
|
||
for (let i = 0; i < 5; i++) { flat[i*2] = cells[i][0]; flat[i*2+1] = cells[i][1]; }
|
||
return flat;
|
||
})])
|
||
);
|
||
|
||
// ── Backtracking solver ───────────────────────────────────────────────────────
|
||
// Iterates a fixed pieceIds[] array + used[] boolean array so we never mutate
|
||
// the structure being iterated (which would cause infinite loops).
|
||
// Cell indices are stored in plain local variables (i0..i4) rather than a
|
||
// shared buffer so recursive calls cannot clobber each other's placed data.
|
||
|
||
function hasSolution(cols, pieceIds) {
|
||
const board = new Int8Array(ROWS * cols); // 0=empty, 1=filled
|
||
const used = new Uint8Array(pieceIds.length);
|
||
return _solve(board, cols, pieceIds, used);
|
||
}
|
||
|
||
function _solve(board, cols, pieceIds, used) {
|
||
// First empty cell (row-major forcing)
|
||
let emptyIdx = -1;
|
||
for (let i = 0; i < board.length; i++) { if (board[i] === 0) { emptyIdx = i; break; } }
|
||
if (emptyIdx === -1) return true; // all cells filled (N pieces × 5 = 5×N board)
|
||
|
||
const targetR = (emptyIdx / cols) | 0;
|
||
const targetC = emptyIdx % cols;
|
||
|
||
for (let pi = 0; pi < pieceIds.length; pi++) {
|
||
if (used[pi]) continue;
|
||
const oris = ORIS_BY_ID[pieceIds[pi]];
|
||
|
||
for (let oi = 0; oi < oris.length; oi++) {
|
||
const ori = oris[oi];
|
||
|
||
// Try each cell of this orientation as the "pin" onto targetR/targetC
|
||
for (let k = 0; k < 5; k++) {
|
||
const anchorR = targetR - ori[k*2];
|
||
const anchorC = targetC - ori[k*2+1];
|
||
|
||
// Validate all 5 cells and collect board indices into local variables
|
||
const a0r = anchorR + ori[0], a0c = anchorC + ori[1];
|
||
const a1r = anchorR + ori[2], a1c = anchorC + ori[3];
|
||
const a2r = anchorR + ori[4], a2c = anchorC + ori[5];
|
||
const a3r = anchorR + ori[6], a3c = anchorC + ori[7];
|
||
const a4r = anchorR + ori[8], a4c = anchorC + ori[9];
|
||
|
||
if (a0r < 0 || a0r >= ROWS || a0c < 0 || a0c >= cols || board[a0r*cols+a0c]) continue;
|
||
if (a1r < 0 || a1r >= ROWS || a1c < 0 || a1c >= cols || board[a1r*cols+a1c]) continue;
|
||
if (a2r < 0 || a2r >= ROWS || a2c < 0 || a2c >= cols || board[a2r*cols+a2c]) continue;
|
||
if (a3r < 0 || a3r >= ROWS || a3c < 0 || a3c >= cols || board[a3r*cols+a3c]) continue;
|
||
if (a4r < 0 || a4r >= ROWS || a4c < 0 || a4c >= cols || board[a4r*cols+a4c]) continue;
|
||
|
||
const i0=a0r*cols+a0c, i1=a1r*cols+a1c, i2=a2r*cols+a2c, i3=a3r*cols+a3c, i4=a4r*cols+a4c;
|
||
board[i0]=1; board[i1]=1; board[i2]=1; board[i3]=1; board[i4]=1;
|
||
used[pi] = 1;
|
||
|
||
if (_solve(board, cols, pieceIds, used)) return true;
|
||
|
||
board[i0]=0; board[i1]=0; board[i2]=0; board[i3]=0; board[i4]=0;
|
||
used[pi] = 0;
|
||
}
|
||
}
|
||
}
|
||
return false;
|
||
}
|
||
|
||
// ── Combination generator ─────────────────────────────────────────────────────
|
||
|
||
function combinations(arr, k) {
|
||
const result = [];
|
||
function pick(start, cur) {
|
||
if (cur.length === k) { result.push([...cur]); return; }
|
||
for (let i = start; i <= arr.length - (k - cur.length); i++) {
|
||
cur.push(arr[i]);
|
||
pick(i + 1, cur);
|
||
cur.pop();
|
||
}
|
||
}
|
||
pick(0, []);
|
||
return result;
|
||
}
|
||
|
||
// ── Main generation ───────────────────────────────────────────────────────────
|
||
|
||
const pieceIds = PIECES.map(p => p.id);
|
||
const pentas = {};
|
||
const t0 = Date.now();
|
||
|
||
for (let n = 3; n <= 12; n++) {
|
||
const combos = combinations(pieceIds, n);
|
||
const valid = [];
|
||
process.stdout.write(`Penta ${n} (5×${n}): ${combos.length} combos … `);
|
||
const t1 = Date.now();
|
||
|
||
for (const combo of combos) {
|
||
if (hasSolution(n, combo)) {
|
||
valid.push({ idx: valid.length, pieces: combo });
|
||
}
|
||
}
|
||
|
||
const dt = ((Date.now() - t1) / 1000).toFixed(1);
|
||
console.log(`${valid.length} valid (${dt}s)`);
|
||
pentas[String(n)] = valid;
|
||
}
|
||
|
||
const output = {
|
||
generatedAt: new Date().toISOString(),
|
||
totalTime: `${((Date.now() - t0) / 1000).toFixed(1)}s`,
|
||
pentas,
|
||
};
|
||
|
||
fs.writeFileSync(OUT_FILE, JSON.stringify(output));
|
||
console.log(`\nWrote ${OUT_FILE} (${(fs.statSync(OUT_FILE).size / 1024).toFixed(0)} KB)`);
|