356 lines
11 KiB
TypeScript
356 lines
11 KiB
TypeScript
import { describe, expect, it } from "vitest";
|
|
import {
|
|
candidatesForCell,
|
|
classicRegions,
|
|
constraintIsFeasible,
|
|
normalizePuzzle,
|
|
validatePuzzle,
|
|
type PuzzleDefinition,
|
|
type VariantConstraint,
|
|
} from "../../src/domain";
|
|
import { solveExact } from "../../src/solver";
|
|
|
|
const solved4 = [1, 2, 3, 4, 3, 4, 1, 2, 4, 3, 2, 1, 2, 1, 4, 3] as const;
|
|
const solved6 = [
|
|
1, 2, 3, 4, 5, 6, 4, 5, 6, 1, 2, 3, 2, 3, 4, 5, 6, 1, 5, 6, 1, 2, 3, 4, 3, 4,
|
|
5, 6, 1, 2, 6, 1, 2, 3, 4, 5,
|
|
] as const;
|
|
|
|
function puzzle(
|
|
size: number,
|
|
overrides: Partial<PuzzleDefinition> = {},
|
|
): PuzzleDefinition {
|
|
return {
|
|
version: 1,
|
|
size,
|
|
givens: new Array<number>(size * size).fill(0),
|
|
regions: classicRegions(size),
|
|
constraints: [],
|
|
...overrides,
|
|
};
|
|
}
|
|
|
|
const semantic4: readonly VariantConstraint[] = [
|
|
{ type: "modular-line", cells: [0, 1, 2, 3] },
|
|
{ type: "zipper-line", cells: [0, 2, 1] },
|
|
{ type: "double-arrow", cells: [0, 2, 1] },
|
|
{ type: "indexer", kind: "row", cell: 7 },
|
|
{ type: "indexer", kind: "column", cell: 5 },
|
|
{ type: "indexer", kind: "box", cell: 14 },
|
|
];
|
|
|
|
describe("Pack 3 validation and cloning", () => {
|
|
it("accepts all production shapes and preserves canonical fog data", () => {
|
|
const definition = puzzle(4, {
|
|
solution: solved4,
|
|
constraints: [
|
|
...semantic4,
|
|
{ type: "fog", lights: [0, 5], revealRadius: 1 },
|
|
],
|
|
});
|
|
expect(validatePuzzle(definition)).toEqual({ valid: true, issues: [] });
|
|
const normalized = normalizePuzzle(definition);
|
|
expect(normalized.constraints).toEqual(definition.constraints);
|
|
expect(normalized.constraints.find(({ type }) => type === "fog")).toEqual({
|
|
type: "fog",
|
|
lights: [0, 5],
|
|
revealRadius: 1,
|
|
});
|
|
|
|
expect(
|
|
validatePuzzle(
|
|
puzzle(6, {
|
|
constraints: [{ type: "entropic-line", cells: [0, 2, 4] }],
|
|
}),
|
|
).valid,
|
|
).toBe(true);
|
|
});
|
|
|
|
it.each([
|
|
[4, { type: "modular-line", cells: [0, 1] }],
|
|
[4, { type: "entropic-line", cells: [0, 1, 2] }],
|
|
[6, { type: "entropic-line", cells: [0, 1] }],
|
|
[4, { type: "zipper-line", cells: [0, 1, 2, 3] }],
|
|
[4, { type: "zipper-line", cells: [0, 1] }],
|
|
[4, { type: "double-arrow", cells: [0, 1] }],
|
|
[4, { type: "indexer", kind: "diagonal", cell: 0 }],
|
|
[4, { type: "indexer", kind: "row", cell: 16 }],
|
|
[4, { type: "fog", lights: [], revealRadius: 1 }],
|
|
[4, { type: "fog", lights: [0], revealRadius: 2 }],
|
|
] as const)(
|
|
"rejects malformed Pack 3 data on size %i",
|
|
(size, constraint) => {
|
|
const result = validatePuzzle({
|
|
...puzzle(size),
|
|
solution: size === 4 ? solved4 : solved6,
|
|
constraints: [constraint],
|
|
});
|
|
expect(result.valid).toBe(false);
|
|
expect(
|
|
result.issues.some(({ path }) => path.startsWith("constraints[0]")),
|
|
).toBe(true);
|
|
},
|
|
);
|
|
|
|
it("requires a complete valid trusted solution for fog", () => {
|
|
const withoutSolution = validatePuzzle(
|
|
puzzle(4, { constraints: [{ type: "fog", lights: [0] }] }),
|
|
);
|
|
expect(withoutSolution.issues).toContainEqual({
|
|
path: "constraints[0]",
|
|
message: "fog requires a complete trusted puzzle solution",
|
|
});
|
|
expect(
|
|
validatePuzzle(
|
|
puzzle(4, {
|
|
solution: new Array<number>(16).fill(0),
|
|
constraints: [{ type: "fog", lights: [0] }],
|
|
}),
|
|
).valid,
|
|
).toBe(false);
|
|
});
|
|
|
|
it("rejects box indexers on custom regions while row and column remain valid", () => {
|
|
const jigsaw = [0, 0, 1, 1, 0, 2, 2, 1, 0, 2, 3, 1, 2, 3, 3, 3];
|
|
expect(
|
|
validatePuzzle(
|
|
puzzle(4, {
|
|
regions: jigsaw,
|
|
constraints: [{ type: "indexer", kind: "box", cell: 0 }],
|
|
}),
|
|
).issues,
|
|
).toContainEqual({
|
|
path: "constraints[0]",
|
|
message: "box indexers require the standard rectangular box layout",
|
|
});
|
|
expect(
|
|
validatePuzzle(
|
|
puzzle(4, {
|
|
regions: jigsaw,
|
|
constraints: [{ type: "indexer", kind: "row", cell: 0 }],
|
|
}),
|
|
).valid,
|
|
).toBe(true);
|
|
});
|
|
});
|
|
|
|
describe("Pack 3 line semantics", () => {
|
|
it("enforces modular residue windows and their negation", () => {
|
|
const constraint = {
|
|
type: "modular-line",
|
|
cells: [0, 1, 2, 3],
|
|
} as const;
|
|
const partial = new Array<number>(16).fill(0);
|
|
partial[0] = 1;
|
|
partial[1] = 2;
|
|
expect(
|
|
candidatesForCell(puzzle(4, { constraints: [constraint] }), partial, 2),
|
|
).toEqual([3]);
|
|
expect(constraintIsFeasible(constraint, solved4, 4)).toBe(true);
|
|
expect(
|
|
constraintIsFeasible({ ...constraint, negated: true }, solved4, 4),
|
|
).toBe(false);
|
|
const invalid = [1, 2, 4, 1, ...new Array<number>(12).fill(0)];
|
|
expect(constraintIsFeasible(constraint, invalid, 4)).toBe(false);
|
|
expect(
|
|
constraintIsFeasible({ ...constraint, negated: true }, invalid, 4),
|
|
).toBe(true);
|
|
});
|
|
|
|
it("enforces equal entropic bands on divisible grids", () => {
|
|
const constraint = {
|
|
type: "entropic-line",
|
|
cells: [0, 1, 2],
|
|
} as const;
|
|
const partial = new Array<number>(36).fill(0);
|
|
partial[0] = 1;
|
|
partial[1] = 3;
|
|
expect(
|
|
candidatesForCell(puzzle(6, { constraints: [constraint] }), partial, 2),
|
|
).toEqual([5, 6]);
|
|
const valid = [1, 3, 5, ...new Array<number>(33).fill(0)];
|
|
const invalid = [1, 2, 5, ...new Array<number>(33).fill(0)];
|
|
expect(constraintIsFeasible(constraint, valid, 6)).toBe(true);
|
|
expect(constraintIsFeasible(constraint, invalid, 6)).toBe(false);
|
|
expect(
|
|
constraintIsFeasible({ ...constraint, negated: true }, valid, 6),
|
|
).toBe(false);
|
|
expect(
|
|
constraintIsFeasible({ ...constraint, negated: true }, invalid, 6),
|
|
).toBe(true);
|
|
});
|
|
|
|
it("enforces zipper pair sums around the centre", () => {
|
|
const constraint = { type: "zipper-line", cells: [0, 1, 2] } as const;
|
|
const partial = new Array<number>(16).fill(0);
|
|
partial[0] = 1;
|
|
partial[1] = 3;
|
|
expect(
|
|
candidatesForCell(puzzle(4, { constraints: [constraint] }), partial, 2),
|
|
).toEqual([2]);
|
|
const valid = [1, 3, 2, ...new Array<number>(13).fill(0)];
|
|
const invalid = [1, 3, 3, ...new Array<number>(13).fill(0)];
|
|
expect(constraintIsFeasible(constraint, valid, 4)).toBe(true);
|
|
expect(constraintIsFeasible(constraint, invalid, 4)).toBe(false);
|
|
expect(
|
|
constraintIsFeasible({ ...constraint, negated: true }, valid, 4),
|
|
).toBe(false);
|
|
expect(
|
|
constraintIsFeasible({ ...constraint, negated: true }, invalid, 4),
|
|
).toBe(true);
|
|
const impossibleCentre = new Array<number>(16).fill(0);
|
|
impossibleCentre[1] = 1;
|
|
expect(constraintIsFeasible(constraint, impossibleCentre, 4)).toBe(false);
|
|
});
|
|
|
|
it("balances double-arrow endpoints against all interior digits", () => {
|
|
const constraint = { type: "double-arrow", cells: [0, 1, 2] } as const;
|
|
const partial = new Array<number>(16).fill(0);
|
|
partial[0] = 1;
|
|
partial[2] = 2;
|
|
expect(
|
|
candidatesForCell(puzzle(4, { constraints: [constraint] }), partial, 1),
|
|
).toEqual([3]);
|
|
const valid = [1, 3, 2, ...new Array<number>(13).fill(0)];
|
|
const invalid = [1, 4, 2, ...new Array<number>(13).fill(0)];
|
|
expect(constraintIsFeasible(constraint, valid, 4)).toBe(true);
|
|
expect(constraintIsFeasible(constraint, invalid, 4)).toBe(false);
|
|
expect(
|
|
constraintIsFeasible({ ...constraint, negated: true }, valid, 4),
|
|
).toBe(false);
|
|
expect(
|
|
constraintIsFeasible({ ...constraint, negated: true }, invalid, 4),
|
|
).toBe(true);
|
|
});
|
|
|
|
it("keeps sound partial bounds when peer rules may narrow remaining digits", () => {
|
|
const empty = new Array<number>(16).fill(0);
|
|
expect(
|
|
constraintIsFeasible(
|
|
{ type: "zipper-line", cells: [0, 1, 2, 3, 4] },
|
|
empty,
|
|
4,
|
|
),
|
|
).toBe(true);
|
|
expect(
|
|
constraintIsFeasible(
|
|
{ type: "double-arrow", cells: [0, 1, 2, 3] },
|
|
empty,
|
|
4,
|
|
),
|
|
).toBe(true);
|
|
expect(
|
|
constraintIsFeasible(
|
|
{ type: "modular-line", cells: [0, 1, 2], negated: true },
|
|
empty,
|
|
4,
|
|
),
|
|
).toBe(true);
|
|
expect(
|
|
constraintIsFeasible(
|
|
{ type: "zipper-line", cells: [0, 1, 2], negated: true },
|
|
empty,
|
|
4,
|
|
),
|
|
).toBe(true);
|
|
expect(
|
|
constraintIsFeasible(
|
|
{ type: "double-arrow", cells: [0, 1, 2], negated: true },
|
|
empty,
|
|
4,
|
|
),
|
|
).toBe(true);
|
|
expect(
|
|
constraintIsFeasible(
|
|
{ type: "indexer", kind: "row", cell: 0, negated: true },
|
|
empty,
|
|
4,
|
|
),
|
|
).toBe(true);
|
|
});
|
|
});
|
|
|
|
describe("Pack 3 indexers and fog", () => {
|
|
it("resolves row, column and rectangular-box targets", () => {
|
|
const row = { type: "indexer", kind: "row", cell: 1 } as const;
|
|
const rowValues = new Array<number>(16).fill(0);
|
|
rowValues[1] = 2;
|
|
expect(
|
|
candidatesForCell(puzzle(4, { constraints: [row] }), rowValues, 5),
|
|
).toEqual([1]);
|
|
|
|
const column = { type: "indexer", kind: "column", cell: 5 } as const;
|
|
expect(constraintIsFeasible(column, solved4, 4)).toBe(true);
|
|
|
|
const box = { type: "indexer", kind: "box", cell: 1 } as const;
|
|
const boxValues = new Array<number>(16).fill(0);
|
|
boxValues[1] = 2;
|
|
expect(
|
|
candidatesForCell(puzzle(4, { constraints: [box] }), boxValues, 3),
|
|
).toEqual([1]);
|
|
boxValues[3] = 2;
|
|
expect(constraintIsFeasible(box, boxValues, 4)).toBe(false);
|
|
expect(constraintIsFeasible({ ...box, negated: true }, boxValues, 4)).toBe(
|
|
true,
|
|
);
|
|
|
|
// In a 2x3-box grid, r2c5 has within-box position 5. Digit 3 points at
|
|
// the same position in box 3 (r4c2), which must contain box index 2.
|
|
const rectangularBox = {
|
|
type: "indexer",
|
|
kind: "box",
|
|
cell: 10,
|
|
} as const;
|
|
const rectangularValues = new Array<number>(36).fill(0);
|
|
rectangularValues[10] = 3;
|
|
expect(
|
|
candidatesForCell(
|
|
puzzle(6, { constraints: [rectangularBox] }),
|
|
rectangularValues,
|
|
19,
|
|
),
|
|
).toEqual([2]);
|
|
});
|
|
|
|
it("keeps fog entirely non-semantic in exact search", () => {
|
|
const givens = [1, 0, 0, 4, 0, 4, 1, 0, 4, 0, 2, 0, 0, 1, 0, 3];
|
|
const plain = solveExact(puzzle(4, { givens }));
|
|
const fogged = solveExact(
|
|
puzzle(4, {
|
|
givens,
|
|
solution: solved4,
|
|
constraints: [{ type: "fog", lights: [0], revealRadius: 1 }],
|
|
}),
|
|
);
|
|
expect(fogged.solutions).toEqual(plain.solutions);
|
|
expect(fogged.count).toBe(plain.count);
|
|
});
|
|
});
|
|
|
|
describe("Pack 3 exact solving", () => {
|
|
it.each(
|
|
semantic4.map((constraint) => [constraint.type, constraint] as const),
|
|
)("solves a 4x4 puzzle containing %s", (_type, constraint) => {
|
|
const givens: number[] = [...solved4];
|
|
givens[5] = 0;
|
|
givens[10] = 0;
|
|
const result = solveExact(puzzle(4, { givens, constraints: [constraint] }));
|
|
expect(result.count).toBe(1);
|
|
expect(result.solutions[0]).toEqual(solved4);
|
|
});
|
|
|
|
it("solves a 6x6 puzzle with an entropic line", () => {
|
|
const givens: number[] = [...solved6];
|
|
givens[2] = 0;
|
|
givens[20] = 0;
|
|
const result = solveExact(
|
|
puzzle(6, {
|
|
givens,
|
|
constraints: [{ type: "entropic-line", cells: [0, 2, 4] }],
|
|
}),
|
|
);
|
|
expect(result.count).toBe(1);
|
|
expect(result.solutions[0]).toEqual(solved6);
|
|
});
|
|
});
|