127 lines
3.9 KiB
TypeScript
127 lines
3.9 KiB
TypeScript
import fc from "fast-check";
|
|
import { describe, expect, it } from "vitest";
|
|
import {
|
|
classicRegions,
|
|
isSolved,
|
|
type PuzzleDefinition,
|
|
} from "../../src/domain";
|
|
import {
|
|
countSolutions,
|
|
generateClassic,
|
|
minimizePuzzle,
|
|
solveExact,
|
|
} from "../../src/solver";
|
|
|
|
const solution4 = [1, 2, 3, 4, 3, 4, 1, 2, 4, 3, 2, 1, 2, 1, 4, 3] as const;
|
|
|
|
const puzzle4: PuzzleDefinition = {
|
|
version: 1,
|
|
size: 4,
|
|
givens: [1, 0, 0, 4, 0, 4, 1, 0, 4, 0, 2, 0, 0, 1, 0, 3],
|
|
regions: classicRegions(4),
|
|
constraints: [],
|
|
};
|
|
|
|
describe("exact solver", () => {
|
|
it("solves a classic puzzle with MRV without mutating its input", () => {
|
|
const original = [...puzzle4.givens];
|
|
const result = solveExact(puzzle4);
|
|
expect(result.count).toBe(1);
|
|
expect(result.solutions[0]).toEqual(solution4);
|
|
expect(result.truncated).toBe(false);
|
|
expect(puzzle4.givens).toEqual(original);
|
|
expect(isSolved(puzzle4, result.solutions[0] ?? [])).toBe(true);
|
|
});
|
|
|
|
it("caps solution counting and reports that unexplored work remains", () => {
|
|
const empty: PuzzleDefinition = {
|
|
...puzzle4,
|
|
givens: new Array<number>(16).fill(0),
|
|
};
|
|
const result = solveExact(empty, { maxSolutions: 2 });
|
|
expect(result.count).toBe(2);
|
|
expect(result.truncated).toBe(true);
|
|
expect(result.limitReason).toBe("solution-cap");
|
|
expect(countSolutions(empty)).toBe(2);
|
|
});
|
|
|
|
it("solves a puzzle combining supported local constraints", () => {
|
|
const variant: PuzzleDefinition = {
|
|
...puzzle4,
|
|
givens: solution4.map((value, cell) => (cell % 3 === 0 ? 0 : value)),
|
|
constraints: [
|
|
{ type: "diagonal", direction: "main" },
|
|
{ type: "diagonal", direction: "anti" },
|
|
{ type: "killer-cage", cells: [0, 1], sum: 3 },
|
|
{ type: "thermo", cells: [0, 1, 2, 3] },
|
|
{ type: "arrow", bulb: [3], line: [0, 2] },
|
|
{ type: "kropki", a: 0, b: 1, kind: "black" },
|
|
{ type: "xv", a: 0, b: 3, total: 5 },
|
|
{ type: "inequality", lesser: 0, greater: 1 },
|
|
{ type: "renban", cells: [0, 1, 2, 3] },
|
|
{ type: "palindrome", cells: [0, 6] },
|
|
],
|
|
};
|
|
expect(solveExact(variant).solutions[0]).toEqual(solution4);
|
|
});
|
|
|
|
it("generates deterministic, unique 4x4 puzzles for arbitrary seeds", () => {
|
|
fc.assert(
|
|
fc.property(fc.integer(), (seed) => {
|
|
const generated = generateClassic({
|
|
size: 4,
|
|
seed,
|
|
targetClues: 8,
|
|
symmetry: "rotational",
|
|
});
|
|
const again = generateClassic({
|
|
size: 4,
|
|
seed,
|
|
targetClues: 8,
|
|
symmetry: "rotational",
|
|
});
|
|
expect(generated.givens).toEqual(again.givens);
|
|
const checked = solveExact(generated, { maxSolutions: 2 });
|
|
expect(checked.count).toBe(1);
|
|
expect(checked.truncated).toBe(false);
|
|
expect(checked.solutions[0]).toEqual(generated.solution);
|
|
}),
|
|
{ numRuns: 12 },
|
|
);
|
|
});
|
|
|
|
it("minimizes only when uniqueness is retained", () => {
|
|
const full: PuzzleDefinition = {
|
|
version: 1,
|
|
size: 4,
|
|
givens: solution4,
|
|
solution: solution4,
|
|
regions: classicRegions(4),
|
|
constraints: [],
|
|
};
|
|
const minimized = minimizePuzzle(full, {
|
|
seed: "minimal",
|
|
targetClues: 6,
|
|
symmetry: "none",
|
|
});
|
|
expect(minimized.givens.filter(Boolean).length).toBeLessThan(16);
|
|
expect(solveExact(minimized).count).toBe(1);
|
|
});
|
|
|
|
it("generates a practical uniquely solvable 9x9 puzzle", () => {
|
|
const generated = generateClassic({
|
|
size: 9,
|
|
seed: "nine-by-nine",
|
|
targetClues: 35,
|
|
symmetry: "rotational",
|
|
maxChecks: 60,
|
|
solveTimeoutMs: 2_000,
|
|
});
|
|
expect(generated.givens.filter(Boolean).length).toBeGreaterThanOrEqual(35);
|
|
const result = solveExact(generated, { timeoutMs: 5_000 });
|
|
expect(result.count).toBe(1);
|
|
expect(result.truncated).toBe(false);
|
|
expect(result.solutions[0]).toEqual(generated.solution);
|
|
});
|
|
});
|