sudoku-tools/tests/domain/pack1Constraints.test.ts

import { describe, expect, it } from "vitest";
import {
  candidatesForCell,
  classicRegions,
  compilePuzzle,
  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;

function puzzle4(overrides: Partial<PuzzleDefinition> = {}): PuzzleDefinition {
  return {
    version: 1,
    size: 4,
    givens: new Array<number>(16).fill(0),
    regions: classicRegions(4),
    constraints: [],
    ...overrides,
  };
}

const packOneConstraints: readonly VariantConstraint[] = [
  { type: "minimum", cell: 0 },
  { type: "odd", cell: 0 },
  { type: "even", cell: 1 },
  { type: "disjoint-groups" },
  {
    type: "little-killer",
    side: "top",
    index: 0,
    direction: "down-right",
    sum: 10,
  },
  { type: "sandwich", side: "left", index: 0, sum: 5 },
];

describe("Pack 1 constraint validation", () => {
  it("accepts and clones every production shape", () => {
    const source = puzzle4({ constraints: packOneConstraints });
    expect(validatePuzzle(source)).toEqual({ valid: true, issues: [] });
    const normalized = normalizePuzzle(source);
    expect(normalized.constraints).toEqual(packOneConstraints);
    expect(normalized.constraints).not.toBe(packOneConstraints);
  });

  it("rejects invalid cells, fields, directions, paths and unreachable sums", () => {
    const invalid: readonly unknown[] = [
      { type: "minimum", cell: 16 },
      { type: "odd", cell: 0, surprise: true },
      { type: "even", cell: -1 },
      { type: "disjoint-groups", negated: true },
      {
        type: "little-killer",
        side: "top",
        index: 0,
        direction: "up-right",
        sum: 10,
      },
      {
        type: "little-killer",
        side: "top",
        index: 0,
        direction: "down-left",
        sum: 4,
      },
      {
        type: "little-killer",
        side: "top",
        index: 0,
        direction: "down-right",
        sum: 17,
      },
      { type: "sandwich", side: "left", index: 0, sum: 1 },
      { type: "sandwich", side: "inside", index: 0, sum: 5 },
    ];
    for (const constraint of invalid) {
      const result = validatePuzzle({
        ...puzzle4(),
        constraints: [constraint],
      });
      expect(result.valid, JSON.stringify(constraint)).toBe(false);
      expect(
        result.issues.some(({ path }) => path.startsWith("constraints[0]")),
      ).toBe(true);
    }
  });

  it("rejects disjoint groups on jigsaw regions but accepts renamed standard boxes", () => {
    const jigsaw = [0, 0, 1, 1, 0, 2, 2, 1, 0, 2, 3, 1, 2, 3, 3, 3];
    const rejected = validatePuzzle(
      puzzle4({ regions: jigsaw, constraints: [{ type: "disjoint-groups" }] }),
    );
    expect(rejected.valid).toBe(false);
    expect(rejected.issues).toContainEqual({
      path: "constraints[0]",
      message: "disjoint groups require the standard rectangular box layout",
    });

    const renamed = classicRegions(4).map((region) => [2, 0, 3, 1][region]!);
    expect(
      validatePuzzle(
        puzzle4({
          regions: renamed,
          constraints: [{ type: "disjoint-groups" }],
        }),
      ).valid,
    ).toBe(true);
  });
});

describe("Pack 1 partial feasibility", () => {
  it("prunes minimum, odd and even cells before the grid is complete", () => {
    const values = new Array<number>(16).fill(0);
    values[1] = 3;
    expect(
      candidatesForCell(
        puzzle4({ constraints: [{ type: "minimum", cell: 0 }] }),
        values,
        0,
      ),
    ).toEqual([1, 2]);
    expect(
      candidatesForCell(
        puzzle4({ constraints: [{ type: "odd", cell: 0 }] }),
        new Array<number>(16).fill(0),
        0,
      ),
    ).toEqual([1, 3]);
    expect(
      candidatesForCell(
        puzzle4({ constraints: [{ type: "even", cell: 0 }] }),
        new Array<number>(16).fill(0),
        0,
      ),
    ).toEqual([2, 4]);

    const impossibleMinimum = new Array<number>(16).fill(0);
    impossibleMinimum[1] = 1;
    expect(
      constraintIsFeasible({ type: "minimum", cell: 0 }, impossibleMinimum, 4),
    ).toBe(false);
    expect(
      constraintIsFeasible(
        { type: "minimum", cell: 0, negated: true },
        [2, 1, ...new Array<number>(14).fill(0)],
        4,
      ),
    ).toBe(true);
  });

  it("compiles four disjoint houses and enforces their remote peers", () => {
    const plain = normalizePuzzle(puzzle4());
    const disjoint = compilePuzzle(
      normalizePuzzle(puzzle4({ constraints: [{ type: "disjoint-groups" }] })),
    );
    expect(
      disjoint.units.filter(({ kind }) => kind === "disjoint-group"),
    ).toHaveLength(4);
    const values = new Array<number>(16).fill(0);
    values[0] = 1;
    expect(candidatesForCell(plain, values, 10)).toContain(1);
    expect(candidatesForCell(disjoint, values, 10)).not.toContain(1);
  });

  it("uses the whole little-killer diagonal for partial sum bounds", () => {
    const constraint = {
      type: "little-killer",
      side: "top",
      index: 1,
      direction: "down-right",
      sum: 6,
    } as const;
    const values = new Array<number>(16).fill(0);
    values[1] = 4;
    expect(
      candidatesForCell(puzzle4({ constraints: [constraint] }), values, 6),
    ).toEqual([1]);

    const complete = [...solved4];
    expect(
      constraintIsFeasible(
        {
          type: "little-killer",
          side: "top",
          index: 0,
          direction: "down-right",
          sum: 10,
        },
        complete,
        4,
      ),
    ).toBe(true);
    expect(
      constraintIsFeasible(
        {
          type: "little-killer",
          side: "top",
          index: 0,
          direction: "down-right",
          sum: 10,
          negated: true,
        },
        complete,
        4,
      ),
    ).toBe(false);
  });

  it("computes exact sandwich possibilities from partial permutations", () => {
    const partial = [1, 2, 0, 4, ...new Array<number>(12).fill(0)];
    expect(
      constraintIsFeasible(
        { type: "sandwich", side: "left", index: 0, sum: 5 },
        partial,
        4,
      ),
    ).toBe(true);
    expect(
      constraintIsFeasible(
        { type: "sandwich", side: "left", index: 0, sum: 3 },
        partial,
        4,
      ),
    ).toBe(false);
    expect(
      constraintIsFeasible(
        {
          type: "sandwich",
          side: "left",
          index: 0,
          sum: 5,
          negated: true,
        },
        solved4,
        4,
      ),
    ).toBe(false);
    expect(
      constraintIsFeasible(
        {
          type: "sandwich",
          side: "left",
          index: 0,
          sum: 3,
          negated: true,
        },
        solved4,
        4,
      ),
    ).toBe(true);
  });
});

describe("Pack 1 exact solving", () => {
  it.each(
    packOneConstraints.map(
      (constraint) => [constraint.type, constraint] as const,
    ),
  )("solves a puzzle containing %s", (_type, constraint) => {
    const givens: number[] = [...solved4];
    givens[5] = 0;
    givens[10] = 0;
    const result = solveExact(puzzle4({ givens, constraints: [constraint] }));
    expect(result.count).toBe(1);
    expect(result.truncated).toBe(false);
    expect(result.solutions[0]).toEqual(solved4);
  });
});