sudoku-tools/tests/solver/logical.test.ts

import { describe, expect, it } from "vitest";
import {
  PuzzleValidationError,
  classicRegions,
  type PuzzleDefinition,
} from "../../src/domain";
import { killerDigitCombinations, solveLogically } from "../../src/solver";

const easy: PuzzleDefinition = {
  version: 1,
  size: 9,
  givens: [
    5, 3, 0, 0, 7, 0, 0, 0, 0, 6, 0, 0, 1, 9, 5, 0, 0, 0, 0, 9, 8, 0, 0, 0, 0,
    6, 0, 8, 0, 0, 0, 6, 0, 0, 0, 3, 4, 0, 0, 8, 0, 3, 0, 0, 1, 7, 0, 0, 0, 2,
    0, 0, 0, 6, 0, 6, 0, 0, 0, 0, 2, 8, 0, 0, 0, 0, 4, 1, 9, 0, 0, 5, 0, 0, 0,
    0, 8, 0, 0, 7, 9,
  ],
  regions: classicRegions(9),
  constraints: [],
};

const emptyFour: PuzzleDefinition = {
  version: 1,
  size: 4,
  givens: Array<number>(16).fill(0),
  regions: classicRegions(4),
  constraints: [],
};

describe("logical solver", () => {
  it("solves a standard puzzle and emits inspectable steps", () => {
    const result = solveLogically(easy);
    expect(result.status).toBe("solved");
    expect(result.values.every((value) => value > 0)).toBe(true);
    expect(result.steps.length).toBeGreaterThan(0);
    expect(result.steps.every((step) => step.explanation.length > 0)).toBe(
      true,
    );
    expect(
      result.steps.some(
        ({ technique }) =>
          technique === "naked-single" || technique === "hidden-single",
      ),
    ).toBe(true);
  });

  it("stops safely at the configured step bound", () => {
    const result = solveLogically(easy, { maxSteps: 1 });
    expect(result.status).toBe("step-limit");
    expect(result.steps).toHaveLength(1);
  });

  it("does not apply positive cage reductions to a false cage", () => {
    const result = solveLogically({
      version: 1,
      size: 4,
      givens: Array<number>(16).fill(0),
      regions: classicRegions(4),
      constraints: [
        {
          type: "killer-cage",
          cells: [0, 1],
          sum: 3,
          noRepeat: false,
          negated: true,
        },
      ],
    });

    expect(result.status).toBe("stuck");
    expect(result.steps).toEqual([]);
    expect(result.candidates[0]).toEqual([1, 2, 3, 4]);
  });

  it("resumes after an elimination-only step from exposed candidates", () => {
    const candidates = Array.from({ length: 16 }, () => [1, 2, 3, 4]);
    candidates[0] = [1, 2];
    candidates[1] = [1, 2];
    candidates[4] = [1, 3];
    candidates[5] = [1, 3];

    const first = solveLogically(emptyFour, {
      candidates,
      maxSteps: 1,
    });
    expect(first.steps[0]).toMatchObject({
      technique: "naked-pair",
      focusCells: [0, 1],
      placements: [],
    });
    expect(first.candidates[2]).toEqual([3, 4]);
    expect(first.candidates[3]).toEqual([3, 4]);

    const next = solveLogically(emptyFour, {
      candidates: first.candidates,
      maxSteps: 1,
    });
    expect(next.steps[0]?.placements).toEqual([]);
    expect(next.steps[0]?.eliminations.length).toBeGreaterThan(0);
    expect(next.steps[0]?.eliminations).not.toEqual(
      first.steps[0]?.eliminations,
    );
    // The first elimination remains applied while the solver advances to a
    // different logical effect. This is the key resume contract for guided
    // hints that do not place a digit.
    expect(next.candidates[2]).toEqual([3, 4]);
    expect(next.candidates[3]).toEqual([3, 4]);
  });

  it("intersects supplied restrictions with candidates legal on the board", () => {
    const candidates = Array.from({ length: 81 }, () =>
      Array.from({ length: 9 }, (_, index) => index + 1),
    );

    const result = solveLogically(easy, { candidates, maxSteps: 1 });
    expect(result.candidates[2]).not.toContain(3);
    expect(result.candidates[2]).not.toContain(5);
    expect(result.candidates[2]).not.toContain(6);
    expect(result.candidates[2]).not.toContain(7);
    expect(result.candidates[2]).not.toContain(8);
    expect(result.candidates[2]).not.toContain(9);
  });

  it("reports a valid empty restriction as an invalid logical state", () => {
    const candidates = Array.from({ length: 16 }, () => [1, 2, 3, 4]);
    candidates[0] = [];

    const result = solveLogically(emptyFour, { candidates });
    expect(result.status).toBe("invalid");
    expect(result.steps).toEqual([]);
    expect(result.candidates[0]).toEqual([]);
  });

  it("rejects malformed candidate restrictions with precise issues", () => {
    expect(() =>
      solveLogically(emptyFour, {
        candidates: Array.from({ length: 15 }, () => [1, 2, 3, 4]),
      }),
    ).toThrow(PuzzleValidationError);

    try {
      solveLogically(emptyFour, {
        candidates: [
          [1, 1],
          [0, 5],
          ...Array.from({ length: 14 }, () => [1, 2, 3, 4]),
        ],
      });
      throw new Error("Expected malformed candidates to be rejected");
    } catch (error) {
      expect(error).toBeInstanceOf(PuzzleValidationError);
      expect((error as PuzzleValidationError).issues).toEqual(
        expect.arrayContaining([
          expect.objectContaining({ path: "candidates[0][1]" }),
          expect.objectContaining({ path: "candidates[1][0]" }),
          expect.objectContaining({ path: "candidates[1][1]" }),
        ]),
      );
    }

    expect(() =>
      solveLogically(emptyFour, {
        candidates: [
          [1, 2, 3, 4],
          null,
          ...Array.from({ length: 14 }, () => [1, 2, 3, 4]),
        ] as unknown as readonly (readonly number[])[],
      }),
    ).toThrow(PuzzleValidationError);
  });

  it("returns bounded killer combinations", () => {
    expect(
      killerDigitCombinations({ size: 9, count: 2, sum: 10 }).combinations,
    ).toEqual([
      [1, 9],
      [2, 8],
      [3, 7],
      [4, 6],
    ]);
    expect(
      killerDigitCombinations({ size: 9, count: 2, sum: 10, noRepeat: false })
        .combinations,
    ).toContainEqual([5, 5]);
    expect(
      killerDigitCombinations({ size: 16, count: 8, sum: 68, maxResults: 1 })
        .truncated,
    ).toBe(true);
  });
});