268 lines
9.2 KiB
TypeScript
268 lines
9.2 KiB
TypeScript
import { describe, expect, it } from "vitest";
|
|
import { classicRegions, type PuzzleDefinition } from "../../src/domain";
|
|
import { analyzePuzzleQuality, qualityItemCells } from "../../src/solver";
|
|
|
|
const solution4 = [1, 2, 3, 4, 3, 4, 1, 2, 4, 3, 2, 1, 2, 1, 4, 3] as const;
|
|
|
|
const unique4: 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("setter quality analysis", () => {
|
|
it("audits a unique puzzle without mutating it", () => {
|
|
const before = JSON.stringify(unique4);
|
|
const result = analyzePuzzleQuality(unique4, { proveMinimality: true });
|
|
|
|
expect(result.solutionStatus).toBe("unique");
|
|
expect(result.solution).toEqual(solution4);
|
|
expect(result.ambiguityWitness).toBeUndefined();
|
|
expect(result.contradiction.status).toBe("not-applicable");
|
|
expect(result.redundancy.givens).toHaveLength(
|
|
unique4.givens.filter(Boolean).length,
|
|
);
|
|
expect(
|
|
result.redundancy.givens.every(
|
|
({ classification }) => classification !== "unknown",
|
|
),
|
|
).toBe(true);
|
|
expect(
|
|
result.redundancy.givens.every(({ classification }) =>
|
|
["critical", "redundant"].includes(classification),
|
|
),
|
|
).toBe(true);
|
|
expect(result.criticalityHeatmap).toHaveLength(16);
|
|
expect(result.budget.checksPerformed).toBe(
|
|
1 + unique4.givens.filter(Boolean).length,
|
|
);
|
|
expect(result.budget.truncated).toBe(false);
|
|
expect(result.minimality?.status).toMatch(
|
|
/^(proven-minimal|not-minimal)$/u,
|
|
);
|
|
expect(JSON.stringify(unique4)).toBe(before);
|
|
});
|
|
|
|
it("returns two concrete solutions and their differing cells for ambiguity", () => {
|
|
const ambiguous: PuzzleDefinition = {
|
|
...unique4,
|
|
givens: [1, ...new Array<number>(15).fill(0)],
|
|
};
|
|
const result = analyzePuzzleQuality(ambiguous);
|
|
|
|
expect(result.solutionStatus).toBe("multiple");
|
|
expect(result.ambiguityWitness?.firstSolution).toHaveLength(16);
|
|
expect(result.ambiguityWitness?.secondSolution).toHaveLength(16);
|
|
expect(result.ambiguityWitness?.differences.length).toBeGreaterThan(0);
|
|
for (const difference of result.ambiguityWitness?.differences ?? []) {
|
|
expect(difference.first).not.toBe(difference.second);
|
|
}
|
|
expect(result.redundancy.givens).toEqual([
|
|
{
|
|
item: { kind: "given", cell: 0, value: 1 },
|
|
classification: "unknown",
|
|
unknownReason: "baseline-not-unique",
|
|
},
|
|
]);
|
|
});
|
|
|
|
it("localizes direct contradictory givens and reports each as critical", () => {
|
|
const contradictory: PuzzleDefinition = {
|
|
...unique4,
|
|
givens: [1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
|
|
};
|
|
const before = JSON.stringify(contradictory);
|
|
const result = analyzePuzzleQuality(contradictory);
|
|
|
|
expect(result.solutionStatus).toBe("unsatisfiable");
|
|
expect(
|
|
result.redundancy.givens.map((entry) => entry.classification),
|
|
).toEqual(["critical", "critical"]);
|
|
expect(result.contradiction.status).toBe("localized");
|
|
expect(result.contradiction.core).toEqual([
|
|
{ kind: "given", cell: 0, value: 1 },
|
|
{ kind: "given", cell: 1, value: 1 },
|
|
]);
|
|
expect(result.contradiction.necessary).toEqual(result.contradiction.core);
|
|
expect(result.contradiction.removable).toEqual([]);
|
|
expect(JSON.stringify(contradictory)).toBe(before);
|
|
});
|
|
|
|
it("finds a minimal contradictory core made from overlapping constraints", () => {
|
|
const contradictory: PuzzleDefinition = {
|
|
...unique4,
|
|
givens: [0, 0, 0, 0, 0, 4, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
|
|
constraints: [
|
|
{ type: "killer-cage", cells: [0], sum: 1 },
|
|
{ type: "killer-cage", cells: [0], sum: 2 },
|
|
],
|
|
};
|
|
const result = analyzePuzzleQuality(contradictory);
|
|
|
|
expect(result.solutionStatus).toBe("unsatisfiable");
|
|
expect(
|
|
result.redundancy.constraints.map(({ classification }) => classification),
|
|
).toEqual(["critical", "critical"]);
|
|
expect(result.redundancy.givens[0]?.classification).toBe("redundant");
|
|
expect(result.contradiction.status).toBe("localized");
|
|
expect(result.contradiction.core).toEqual([
|
|
{ kind: "constraint", index: 0, constraintType: "killer-cage" },
|
|
{ kind: "constraint", index: 1, constraintType: "killer-cage" },
|
|
]);
|
|
expect(result.contradiction.removable).toEqual([
|
|
{ kind: "given", cell: 5, value: 4 },
|
|
]);
|
|
expect(result.contradiction.unknown).toEqual([]);
|
|
});
|
|
|
|
it("identifies redundant givens and constraints and derives non-minimality", () => {
|
|
const overSpecified: PuzzleDefinition = {
|
|
...unique4,
|
|
givens: solution4,
|
|
solution: solution4,
|
|
constraints: [
|
|
{ type: "diagonal", direction: "main" },
|
|
{ type: "diagonal", direction: "main" },
|
|
],
|
|
};
|
|
const result = analyzePuzzleQuality(overSpecified, {
|
|
proveMinimality: true,
|
|
});
|
|
|
|
expect(result.solutionStatus).toBe("unique");
|
|
expect(
|
|
result.redundancy.givens.every(
|
|
({ classification }) => classification === "redundant",
|
|
),
|
|
).toBe(true);
|
|
expect(
|
|
result.redundancy.constraints.every(
|
|
({ classification }) => classification === "redundant",
|
|
),
|
|
).toBe(true);
|
|
expect(result.minimality?.status).toBe("not-minimal");
|
|
expect(result.minimality?.redundant).toHaveLength(18);
|
|
expect(result.criticalityHeatmap[0]).toMatchObject({
|
|
score: 0,
|
|
criticalWeight: 0,
|
|
redundantWeight: 3,
|
|
unknownWeight: 0,
|
|
});
|
|
});
|
|
|
|
it("never turns per-check truncation into a uniqueness proof", () => {
|
|
const result = analyzePuzzleQuality(unique4, {
|
|
perCheckMaxNodes: 1,
|
|
aggregateMaxNodes: 100,
|
|
aggregateMaxChecks: 100,
|
|
proveMinimality: true,
|
|
});
|
|
|
|
expect(result.solutionStatus).toBe("unknown");
|
|
expect(result.checks).toHaveLength(1);
|
|
expect(result.checks[0]).toMatchObject({
|
|
solutionStatus: "unknown",
|
|
conclusive: false,
|
|
truncated: true,
|
|
limitReason: "node-cap",
|
|
unknownReason: "per-check-node-cap",
|
|
});
|
|
expect(
|
|
result.redundancy.givens.every(
|
|
({ classification }) => classification === "unknown",
|
|
),
|
|
).toBe(true);
|
|
expect(result.minimality?.status).toBe("not-applicable");
|
|
expect(result.budget.unknownReasons).toContain("per-check-node-cap");
|
|
expect(result.budget.unknownReasons).toContain("baseline-unknown");
|
|
});
|
|
|
|
it("shares an aggregate check budget across all removal checks", () => {
|
|
const result = analyzePuzzleQuality(
|
|
{ ...unique4, givens: solution4, solution: solution4 },
|
|
{
|
|
aggregateMaxChecks: 1,
|
|
aggregateMaxNodes: 1_000,
|
|
proveMinimality: true,
|
|
},
|
|
);
|
|
|
|
expect(result.solutionStatus).toBe("unique");
|
|
expect(result.budget.checksPerformed).toBe(1);
|
|
expect(result.budget.checksPlanned).toBe(17);
|
|
expect(result.budget.truncated).toBe(true);
|
|
expect(result.budget.unknownReasons).toContain("aggregate-check-cap");
|
|
expect(
|
|
result.redundancy.givens.every(
|
|
({ classification, unknownReason }) =>
|
|
classification === "unknown" &&
|
|
unknownReason === "aggregate-check-cap",
|
|
),
|
|
).toBe(true);
|
|
expect(result.minimality?.status).toBe("unknown");
|
|
});
|
|
|
|
it("leaves contradiction-core items unknown when the shared budget ends", () => {
|
|
const contradictory: PuzzleDefinition = {
|
|
...unique4,
|
|
givens: [1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
|
|
};
|
|
const result = analyzePuzzleQuality(contradictory, {
|
|
aggregateMaxChecks: 1,
|
|
});
|
|
|
|
expect(result.solutionStatus).toBe("unsatisfiable");
|
|
expect(result.contradiction.status).toBe("incomplete");
|
|
expect(result.contradiction.necessary).toEqual([]);
|
|
expect(result.contradiction.unknown).toEqual(result.contradiction.core);
|
|
expect(result.budget.checksPerformed).toBe(1);
|
|
expect(result.budget.unknownReasons).toContain("aggregate-check-cap");
|
|
});
|
|
|
|
it("supports a cheap baseline-only depth", () => {
|
|
const result = analyzePuzzleQuality(unique4, {
|
|
analysisDepth: "baseline",
|
|
proveMinimality: true,
|
|
});
|
|
|
|
expect(result.analysisDepth).toBe("baseline");
|
|
expect(result.solutionStatus).toBe("unique");
|
|
expect(result.redundancy).toEqual({ givens: [], constraints: [] });
|
|
expect(result.criticalityHeatmap).toEqual([]);
|
|
expect(result.contradiction.status).toBe("not-applicable");
|
|
expect(result.minimality?.status).toBe("not-applicable");
|
|
expect(result.budget.checksPlanned).toBe(1);
|
|
expect(result.budget.checksPerformed).toBe(1);
|
|
});
|
|
|
|
it("maps given, local and outside findings to their board cells", () => {
|
|
const puzzle: PuzzleDefinition = {
|
|
...unique4,
|
|
constraints: [
|
|
{ type: "killer-cage", cells: [4, 5], sum: 7 },
|
|
{ type: "x-sum", side: "top", index: 2, sum: 6 },
|
|
],
|
|
};
|
|
|
|
expect(
|
|
qualityItemCells(puzzle, { kind: "given", cell: 0, value: 1 }),
|
|
).toEqual([0]);
|
|
expect(
|
|
qualityItemCells(puzzle, {
|
|
kind: "constraint",
|
|
index: 0,
|
|
constraintType: "killer-cage",
|
|
}),
|
|
).toEqual([4, 5]);
|
|
expect(
|
|
qualityItemCells(puzzle, {
|
|
kind: "constraint",
|
|
index: 1,
|
|
constraintType: "x-sum",
|
|
}),
|
|
).toEqual([2, 6, 10, 14]);
|
|
});
|
|
});
|