Generate a Word-Fit puzzle grid

by Ben Gillbanks

HTML

<pre></pre>

JavaScript

/**
 * Generate a Word-Fit (Kriss-Kross) puzzle grid
 * with no merges and no touching.
 * @param {string[]} words - List of uppercase words.
 * @returns {{grid:string[][], placed:object[]}}
 */
function generateWordFit(words) {
	// sort words longest first
	words = words.slice().sort((a, b) => b.length - a.length);

	// map "x,y" -> letter
	const grid = new Map();
	let minX = 0, maxX = 0, minY = 0, maxY = 0;

	// place first word at 1,1 horizontally
	place("H", words[0], 1, 1);
	const placed = [{ word: words[0], dir: "H", x: 1, y: 1 }];

	for (let i = 1; i < words.length; i++) {
		const w = words[i];
		const fits = getFits(w);

		if (!fits.length) {
			// no overlap—append on next odd row
			const y = maxY + 2;
			place("H", w, 1, y);
			placed.push({ word: w, dir: "H", x: 1, y });
		} else {
			// pick best (max overlaps, then min area)
			fits.sort((a, b) => {
				if (b.overlap !== a.overlap) return b.overlap - a.overlap;
				return a.newArea - b.newArea;
			});
			const best = fits[0];
			place(best.dir, w, best.x, best.y);
			placed.push({ word: w, dir: best.dir, x: best.x, y: best.y });
		}
	}

	// build 2D array
	const width = maxX - minX + 1;
	const height = maxY - minY + 1;
	const out = Array.from({ length: height }, () => Array(width).fill(" "));
	for (let [k, v] of grid.entries()) {
		const [x, y] = k.split(",").map(Number);
		out[y - minY][x - minX] = v;
	}

	return { grid: out, placed };

	// helpers

	function key(x, y) { return `${x},${y}`; }

	function place(dir, word, x, y) {
		for (let i = 0; i < word.length; i++) {
			const xx = x + (dir === "H" ? i : 0);
			const yy = y + (dir === "V" ? i : 0);
			grid.set(key(xx, yy), word[i]);
			minX = Math.min(minX, xx);
			maxX = Math.max(maxX, xx);
			minY = Math.min(minY, yy);
			maxY = Math.max(maxY, yy);
		}
	}

	function getFits(word) {
		const fits = [];
		for (let [k, v] of grid.entries()) {
			const [gx, gy] = k.split(",").map(Number);
			for (let i = 0; i < word.length; i++) {
				if (word[i] !==...