Skip to main content

nonogram_dart 3.0.0-dev.1 copy "nonogram_dart: ^3.0.0-dev.1" to clipboard
nonogram_dart: ^3.0.0-dev.1 copied to clipboard

Solve and generate nonograms, also known as Paint by Numbers, Picross and Griddlers

nonogram_dart 3.0 #

A pure Dart toolkit for nonogram designers: immutable puzzles, bounded solution validation, technique analysis and structured hints, deduction scarcity, and reproducible goal-guided fill-in plans. Supports monochrome and multicolor rectangular puzzles. Requires Dart 3.7 or later.

import 'package:nonogram_dart/nonogram_dart.dart';

final target = SolutionGrid.fromRows([
  [1, 0],
  [0, 1],
]);
final puzzle = PuzzleDefinition.fromSolution(target);
const analyzer = NonogramAnalyzer();

final report = analyzer.analyze(puzzle, intendedSolution: target);
print(report.validation!.multiplicity); // multiple
print(report.techniques.first.deductionScarcity);

final plan = const FillInPlanner().plan(
  puzzle,
  target: target,
  options: const FillInOptions(seed: 42),
);
print(plan.count);
final playablePuzzle = plan.applyTo(puzzle);
final hint = analyzer.nextHint(playablePuzzle).hint;
print(hint?.toJson());

Puzzle model #

PuzzleDefinition stores dimensions, a palette, immutable row/column clues, and explicit Givens. ClueRun(length, color: id) describes one foreground block. SolutionGrid is a completely resolved rectangular grid, never a partial grid masquerading as a solution. puzzle.accepts(solution) validates dimensions, colors, all clues, and every given.

Colors are palette IDs, not ARGB integers: 0 is background; foreground IDs start at 1. Differently colored blocks may touch; equal colors require a gap. Rendering colors, including opaque white foreground, are independent of this meaning. A palette can contain more than 32 colors; large palettes use an exact BigInt fallback rather than truncating color domains.

Construct directly with PuzzleDefinition(...), PuzzleDefinition.monochrome, or PuzzleDefinition.fromSolution. Constructors reject structural errors with FormatException. Well-formed but unsatisfiable clues remain representable. inspect() reports impossible line spans and mismatched per-color totals. PuzzleDefinition.tryParse(json) converts malformed input into designer diagnostics. All public model collections are defensively copied.

Solving and validation #

  • solveFirst(puzzle): one solution, with explicit termination information.
  • enumerateSolutions(puzzle): a single-use lazy cursor with optional maxSolutions. Its result is populated on exhaustion/limit; stopping iteration early leaves it null. At most two witness grids are retained.
  • checkUniqueness(puzzle): search until two solutions or exhaustive completion.
  • analyze(puzzle): independent technique reports and optional uniqueness check.

SolutionMultiplicity is none, unique, multiple, or undetermined. Only an exhaustive search establishes no solution or uniqueness. Two distinct solutions establish multiplicity immediately. Finding one solution and reaching a limit does not establish uniqueness. witnessDifferences compares two witnesses; it is not a complete map of all ambiguous cells.

An optional intendedSolution must satisfy the puzzle. It establishes existence and directs validation toward finding a different grid. It is never supplied to the human-technique engine. Original puzzle validation remains separate from validation after adding a fill-in plan.

Techniques and structured hints #

analyzeTechniques runs from the supplied givens with a versioned profile. nextHint returns a technique identifier, structured domain changes, positions, and supporting line references. It never invents a hint by consulting a hidden goal or silently accepting a guessed branch.

Profile Techniques
lineV1 Exact single-line deductions of fixed cell colors
lineAndColorV1 Line DP plus cross-line propagation of possible colors
advancedV1 Color propagation, smile, summing, edge, two-way logic

The advanced rules follow the terminology of WebPBN's solving guide:

  • Edge: test all colors at unknown-area boundary cells, propagating up to two crossing-line hops; retain consequences common to surviving cases.
  • Smile: joint arrangements of two binary lines whose unresolved crossing lines each require one remaining foreground cell. Patterns are limited to 64 cells and maxPatternPairs complete pairs. A capped partial enumeration never justifies a deduction.
  • Two-way: test both colors of a two-valued cell with full basic propagation, retaining restrictions valid in every surviving case. No nested search.
  • Summing: exact per-color totals in contiguous row/column bands, checked against crossing-line capacity bounds. Bands span up to maxRegionSpan.

maxProbeCells, maxPatternPairs, and maxRegionSpan are part of the profile definition. A profile reports solved, stalled, contradiction, or limited. Stalling is not proof that guessing is necessary or that no human technique could help.

Analysis statistics and deduction scarcity #

Every technique report includes successful techniqueCounts, resolvedCells, unresolvedCells, startDomainSize, endDomainSize, and propagationRounds. Domain sizes sum the candidate-color counts across all cells; the start is measured after applying givens. These statistics remain available with tracing off.

Techniques run in a fixed order: line, color, edge, smile, two-way, summing. After an advanced deduction or a partial color reduction, analysis returns to line deductions before trying later techniques.

TechniqueAnalysis.deductionScarcity adds a separate 0–1 measure of how hard it is to find a productive line:

q = productive unresolved lines / unresolved lines
deductionScarcity = 1 - mean(q)

A productive line determines the final color of at least one unresolved cell, without consulting crossing lines. Eliminating candidates while leaving several possible colors does not count as productive, regardless of the selected profile. Partial color reductions still propagate and their resulting board states are sampled, so they can unlock productive lines. Each sample inspects all unresolved rows and columns against the same board without changing it. Samples are taken before basic propagation and after successful deduction batches; unchanged states and solved boards are excluded. Advanced deductions are reflected in the next propagation sample. This measures availability of resolved-cell line deductions, not availability of every advanced technique.

Zero means productive lines are plentiful; larger values mean they are scarce. Fully given puzzles score zero. Stalled, contradictory, or interrupted analyses return null. The metric is independent of trace retention. Sampling adds line scans to technique analysis and shares its work/time/cancellation budget. Hint requests and fill-in planning do not collect scarcity samples.

Hints and deduction scarcity are separate from gameplay policies and artwork previews.

Reproducible fill-ins #

FillInPlanner (also named FillInSolver) uses a valid target, tries the chosen technique profile, and reveals a target cell only when that profile stalls. Both empty and foreground reveals count. It returns an ordered FillInPlan, never a claim about a mathematical minimum.

  • seededShuffleV1: choose from a seeded shuffle of currently eligible cells.
  • seededGreedyV1: score up to maxCandidates seeded candidates by the number of color possibilities eliminated; break ties by seeded order.
  • Optional deterministic backward removal of redundant reveals produces an inclusion-minimal subset for the selected profile, not a global optimum.

The seed is an unsigned 32-bit integer. The specified generator is the LCG state = (1664525 * state + 1013904223) mod 2^32, followed by modulo selection and Fisher–Yates shuffling. It does not rely on SDK-dependent Random streams. Completed plans are reproducible for identical puzzle, target, seed, strategy, profile, and options across supported runtimes. Store the actual reveals, plannerVersion, options, and fingerprints for replay.

maxFillIns is optional; there is no built-in 15-cell gameplay policy. Limits produce typed partial results. A plan can remain usable (isComplete) if pruning is interrupted; planningComplete distinguishes a finished planning operation. Time-limited partial results are not reproducibility guarantees. Use deterministic work limits for reproducible stopping points.

Limits and cooperative execution #

WorkLimits controls counted work units, elapsed duration, and a cancellation callback. The line cache has an internal cap of 512 entries. Set maxTraceSteps on AnalysisOptions, analyzeTechniques, or nextHint to limit retained cell-domain changes (default 10000 per profile). Trace truncation does not discard proof or analysis statistics. Limits are cooperative, not OS process or hard heap limits. Large palettes and difficult searches still need appropriate budgets.

final session = analyzer.startAnalysis(
  puzzle,
  options: const AnalysisOptions(limits: WorkLimits(maxWorkUnits: 1000000)),
);
while (!session.advance(maxWorkUnits: 4096)) {
  // Yield to the UI/event loop, or advance in a worker.
}
final result = session.result!;

advance has a soft quantum between line/rule operations. Hard request limits are checked inside DP and search too. cancel() takes effect while advancing. The API is synchronous/cooperative; Flutter code should schedule advances or run analysis in a worker. Paused sessions expose counters, not hypothetical branch grids. Techniques run before uniqueness and share the request budget; use focused methods when validating is the priority.

Serialization, images, and generation #

Models, reports, hints, and plans have versioned JSON representations. Fingerprints include canonical dimensions, palette, clues, and normalized givens; solution fingerprints include dimensions and color IDs.

nonogram_images.dart provides NonogramImages PNG adapters and PuzzleArtwork. The default mask matches v2: fully opaque non-white pixels are foreground. Supply isForeground for a different mask. This optional entry point uses the image dependency; the core analysis library does not decode images. PuzzleArtwork.sourcePng and encodeArtwork preserve decorative background colors/alpha separately from the logical mask. toMonochrome() collapses foreground IDs when the artwork should become a monochrome puzzle.

nonogram_generation.dart provides seeded palette-ID artwork generation. Generation proposes artwork; explicitly validate uniqueness and technique difficulty before publishing. The 2.x API and geometric generators have been removed.

Performance and verification #

The core uses flat typed domains for small palettes, reusable DP workspaces, dirty-line queues, bounded exact line-result caches, and a reversible search trail instead of cloning the grid and history at every decision. Line DP costs O(L * (K + C + 1)) time/space for length L, K runs, C colors. Whole-puzzle search remains exponential in the worst case. The large-palette fallback additionally scales with the width of its BigInt bitsets.

fvm dart test
fvm dart analyze
fvm dart compile exe benchmark/v3_benchmark.dart -o /tmp/nonogram_v3_benchmark
/tmp/nonogram_v3_benchmark

See benchmark/README.md for WebPBN corpus tooling. Tests include exhaustive small-puzzle oracles and soundness checks for named rules. tool/v3_smoke.dart produces portable JSON; compile it to JS/Wasm and compare with VM output to check fingerprints and seeded plans.

For replacements for the removed 2.x API, see MIGRATION.md.

1
likes
160
points
304
downloads

Documentation

API reference

Publisher

unverified uploader

Weekly Downloads

Solve and generate nonograms, also known as Paint by Numbers, Picross and Griddlers

Repository (GitHub)
View/report issues

License

MIT (license)

Dependencies

crypto, image

More

Packages that depend on nonogram_dart