numberlink.generator

Procedural level generator for the numberlink environment.

This module implements two procedural generators and a set of internal helpers used to create valid NumberLink puzzles. The primary entry point is generate_level(). The function generate_level() dispatches to _gen_hamiltonian_partition() or _gen_random_walk() depending on the provided configuration. All generator functions return a numberlink.levels.Level representing the puzzle grid and optional bridge positions.

The implementation organizes helpers for path creation, rewiring, partitioning, validation, and rendering. See individual function docstrings for algorithmic notes and usage details.

Module Contents

Functions

generate_level	Generate a puzzle level using the configured generator settings.
_gen_hamiltonian_partition	Deterministic generator that assembles a valid, fully filled puzzle.
_are_adjacent	Return whether two coordinates are orthogonally adjacent.
_paths_cover_grid	Return whether the supplied solution paths cover every cell in the grid.
_build_neighbor_map	Precompute orthogonal neighbours for every cell in the grid.
_random_hamiltonian_path	Generate a Hamiltonian path using randomized backtracking.
_hamiltonian_backtrack	Backtracking helper used by _random_hamiltonian_path().
_shuffle_letter_assignments	Randomize which letter is assigned to each solution path.
_rotated_dims	Compute grid dimensions after applying a rotation.
_transform_coord	Transform a coordinate by a rotation of the grid.
_apply_random_orientation	Randomly rotate and optionally mirror a generated level.
_enhance_variability	Apply post processing steps that introduce additional visual variety.
_build_serpentine_segments	Construct a deterministic Hamiltonian path and partition it into segments.
_build_initial_path	Create a Hamiltonian path that covers the entire grid using a serpentine sweep.
_apply_loop_moves	Apply random 2-opt style loop reversals to introduce variety while preserving coverage.
_compute_conflict_min_starts	Identify the earliest valid segment start index for each position in the Hamiltonian path.
_partition_choices	Compute viable segment endpoints for dynamic partitioning of a Hamiltonian path.
_build_partition	Recursively construct segment bounds for a Hamiltonian path partition.
_partition_path_into_segments	Split a Hamiltonian path into contiguous segments while avoiding adjacent endpoints.
_compute_segment_map	Compute a 2D numpy array that maps each grid cell to its segment index.
_validate_segments	Validate that every segment is a simple path and meets NumberLink constraints.
_segments_to_level	Render segment endpoints onto the puzzle grid.
_shortest_dist	Compute the shortest grid distance between two coordinates using the configured movement rules.
_sample_start_cell	Sample a start cell uniformly among cells not in used_endpoints.
_gen_random_walk	Generate a puzzle by placing endpoints using per-color random walks.

Data

DIR_STEPS

API

numberlink.generator.DIR_STEPS: tuple[Coord, ...] = ((), (0, 1), (1, 0), (0,))

numberlink.generator.generate_level(cfg: numberlink.config.GeneratorConfig, *, variant: numberlink.config.VariantConfig | None = None) → numberlink.levels.Level

Generate a puzzle level using the configured generator settings.

Dispatch to either _gen_hamiltonian_partition() or _gen_random_walk() depending on the value of cfg.mode. The returned value is a numberlink.levels.Level instance suitable for immediate use by the environment or saving to disk.

Parameters:

• cfg (GeneratorConfig) – Generator configuration object. See numberlink.config.GeneratorConfig for options and defaults.

• variant (VariantConfig or None) – Variant configuration object. If None, defaults to VariantConfig() with standard settings. The must_fill and allow_diagonal settings are taken from this parameter.

Returns:

Generated puzzle level as a numberlink.levels.Level.

Return type:

Level

Raises:

ValueError – If cfg.mode is not one of 'hamiltonian' or 'random_walk'.

numberlink.generator._gen_hamiltonian_partition(cfg: numberlink.config.GeneratorConfig, *, variant: numberlink.config.VariantConfig, allow_random_fallback: bool = True) → numberlink.levels.Level

Deterministic generator that assembles a valid, fully filled puzzle.

The generator builds a Hamiltonian path that covers every cell and partitions that path into segments that become colored paths for the puzzle. The high level steps are:

1. Build a Hamiltonian backbone using a serpentine sweep implemented by _build_initial_path().

2. Apply randomized 2 opt style rewiring to the backbone using _apply_loop_moves() to introduce variety while preserving full coverage.

3. Partition the Hamiltonian path into contiguous segments using _partition_path_into_segments() so that each segment meets the minimum node length.

4. Validate that the partitioned segments are simple paths and meet rules using _validate_segments() and _compute_segment_map().

5. Convert segment endpoints into a puzzle grid with _segments_to_level() and return the resulting numberlink.levels.Level.

Parameters:

cfg (GeneratorConfig) – Generator configuration object. See numberlink.config.GeneratorConfig for details.

Returns:

Generated puzzle level as a numberlink.levels.Level.

Return type:

Level

Raises:

ValueError – If the grid dimensions or color count are not positive, or if bridge placement is requested in the configuration. If the generator fails to produce a valid partition within a bounded number of attempts it falls back to _gen_random_walk() and does not raise here.

numberlink.generator._are_adjacent(a: Coord, b: Coord) → bool

Return whether two coordinates are orthogonally adjacent.

Adjacency is measured by the Manhattan distance and requires a distance of exactly 1.

Parameters:

• a (Coord) – First coordinate as a (row, column) pair.

• b (Coord) – Second coordinate as a (row, column) pair.

Returns:

True when the coordinates are adjacent, otherwise False.

Return type:

bool

numberlink.generator._paths_cover_grid(paths: list[list[Coord]], height: int, width: int) → bool

Return whether the supplied solution paths cover every cell in the grid.

Parameters:

• paths (list[list[Coord]]) – Collection of solution paths where each path is a list of coordinates.

• height (int) – Grid row count.

• width (int) – Grid column count.

Returns:

True when every cell in the height by width grid is included in paths, otherwise False.

Return type:

bool

numberlink.generator._build_neighbor_map(height: int, width: int) → dict[Coord, list[Coord]]

Precompute orthogonal neighbours for every cell in the grid.

Parameters:

• height (int) – Number of grid rows.

• width (int) – Number of grid columns.

Returns:

Mapping from a coordinate to a list of orthogonally adjacent coordinates.

Return type:

dict[Coord, list[Coord]]

numberlink.generator._random_hamiltonian_path(height: int, width: int, rng: numpy.random.Generator, *, attempts: int = 128) → list[Coord] | None

Generate a Hamiltonian path using randomized backtracking.

The search performs Warnsdorff style tie breaking by preferring candidates with the fewest onward moves to improve success probability. When all attempts fail the function returns None and callers may fall back to deterministic patterns such as _build_initial_path().

Parameters:

• height (int) – Grid row count.

• width (int) – Grid column count.

• rng (numpy.random.Generator) – Random number generator used for stochastic decisions.

• attempts (int, optional) – Number of random start attempts to try.

Returns:

Hamiltonian path covering every cell as a list of coordinates, or None if no path is found.

Return type:

list[Coord] or None

numberlink.generator._hamiltonian_backtrack(path: list[Coord], visited: set[Coord], neighbours: dict[Coord, list[Coord]], total_cells: int, max_steps: int, steps: list[int], rng: numpy.random.Generator) → bool

Backtracking helper used by _random_hamiltonian_path().

The helper advances the recursive search and respects max_steps to avoid excessively long runs. It implements Warnsdorff style tie breaking by ordering candidate moves according to the number of onward moves.

Parameters:

• path (list[Coord]) – Current path under construction.

• visited (set[Coord]) – Set of visited coordinates.

• neighbours (dict[Coord, list[Coord]]) – Mapping from a coordinate to its orthogonal neighbours.

• total_cells (int) – Total number of cells to cover.

• max_steps (int) – Maximum allowed search steps to limit runtime.

• steps (list[int]) – Mutable single element list used as a counter for steps.

• rng (numpy.random.Generator) – Random number generator used for tie breaking.

Returns:

True when a Hamiltonian path covering all cells is found.

Return type:

bool

numberlink.generator._shuffle_letter_assignments(level: numberlink.levels.Level, rng: numpy.random.Generator) → numberlink.levels.Level

Randomize which letter is assigned to each solution path.

The function returns a new numberlink.levels.Level with grid characters remapped and with the solution paths reordered to match the new assignment. When level.solution is None or contains fewer than two paths the input level is returned unchanged.

Parameters:

• level (Level) – Level to remap.

• rng (numpy.random.Generator) – Random number generator used to shuffle assignments.

Returns:

New numberlink.levels.Level with shuffled letter assignments.

Return type:

Level

numberlink.generator._rotated_dims(height: int, width: int, rotation: int) → Coord

Compute grid dimensions after applying a rotation.

Determine the resulting (height, width) pair when a rectangular grid with the supplied height and width is rotated by rotation steps of 90 degrees clockwise. Rotation values are integers in the range 0..3 where each increment represents a 90 degree clockwise rotation. When the rotation is odd the dimensions are swapped.

This helper is used by _apply_random_orientation() to allocate the transformed grid matrix before mapping characters and coordinates. It does not validate the numeric range of rotation and will return a swapped pair for odd values and the original pair for even values.

Parameters:

• height (int) – Original grid row count.

• width (int) – Original grid column count.

• rotation (int) – Number of 90 degree clockwise rotations to apply.

Returns:

Tuple (new_height, new_width) after rotation.

Return type:

tuple of two int

See also

_transform_coord() for per-coordinate transformation under the same rotation convention.

numberlink.generator._transform_coord(r: int, c: int, height: int, width: int, rotation: int) → Coord

Transform a coordinate by a rotation of the grid.

Map an input coordinate (r, c) from the original grid to the corresponding coordinate in the grid rotated by rotation steps of 90 degrees clockwise. Rotation values follow the same convention used by _rotated_dims() where 0 represents no rotation and 1 represents a 90 degree clockwise rotation.

The mapping rules are:

• rotation == 0: (r, c) -> (r, c) (identity)

• rotation == 1: (r, c) -> (c, height - 1 - r)

• rotation == 2: (r, c) -> (height - 1 - r, width - 1 - c)

• rotation == 3: (r, c) -> (width - 1 - c, r)

This function is used by _apply_random_orientation() when copying grid characters and when transforming solution paths and bridge coordinates.

Parameters:

• r (int) – Row index in the original grid.

• c (int) – Column index in the original grid.

• height (int) – Original grid row count.

• width (int) – Original grid column count.

• rotation (int) – Number of 90 degree clockwise rotations to apply.

Returns:

Transformed coordinate (new_row, new_col) in the rotated grid.

Return type:

tuple of two int

Raises:

ValueError – When rotation is not one of 0, 1, 2, or 3.

See also

_rotated_dims() for computing the dimensions of the rotated grid used when allocating the destination matrix.

numberlink.generator._apply_random_orientation(level: numberlink.levels.Level, rng: numpy.random.Generator) → numberlink.levels.Level

Randomly rotate and optionally mirror a generated level.

Apply a random rotation and an independent horizontal flip when selected. The returned numberlink.levels.Level uses transformed coordinates for the numberlink.levels.Level.solution attribute and for the numberlink.levels.Level.bridges attribute when present.

Parameters:

• level (numberlink.levels.Level) – Level to transform.

• rng (numpy.random.Generator) – Random number generator used to select rotation and flip.

Returns:

Transformed level with updated grid, bridges, and solution.

Return type:

numberlink.levels.Level

Raises:

ValueError – If an unsupported rotation value is passed to _transform_coord().

numberlink.generator._enhance_variability(level: numberlink.levels.Level, rng: numpy.random.Generator) → numberlink.levels.Level

Apply post processing steps that introduce additional visual variety.

Compose _apply_random_orientation() and _shuffle_letter_assignments() to produce a visually varied puzzle instance. The returned object preserves the semantics of numberlink.levels.Level.

Parameters:

• level (numberlink.levels.Level) – Base level to vary.

• rng (numpy.random.Generator) – Random number generator used for stochastic steps.

Returns:

Varied level with normalized types for attributes.

Return type:

numberlink.levels.Level

numberlink.generator._build_serpentine_segments(height: int, width: int, n_colors: int, min_nodes: int, rng: numpy.random.Generator) → list[list[Coord]] | None

Construct a deterministic Hamiltonian path and partition it into segments.

Use _build_initial_path() to create a serpentine Hamiltonian path and then partition it into n_colors contiguous segments. Each segment meets the min_nodes requirement when partitioning succeeds.

Parameters:

• height (int) – Grid row count.

• width (int) – Grid column count.

• n_colors (int) – Number of segments to produce.

• min_nodes (int) – Minimum allowed nodes in each segment.

• rng (numpy.random.Generator) – Random number generator used to preserve call signature.

Returns:

List of segments when partitioning succeeds or None when it fails.

Return type:

list[list[Coord]] or None

numberlink.generator._build_initial_path(height: int, width: int, rng: numpy.random.Generator) → list[Coord]

Create a Hamiltonian path that covers the entire grid using a serpentine sweep.

Construct a full coverage path by sweeping rows or columns in alternating directions. The initial sweep axis and an optional reversal are selected using the provided random number generator.

Parameters:

• height (int) – Number of rows in the grid.

• width (int) – Number of columns in the grid.

• rng (numpy.random.Generator) – Numpy random number generator used to choose orientation and reversal. See numpy.random.

Returns:

List of coordinates that covers every cell exactly once.

Return type:

list[Coord]

Raises:

ValueError – If height or width is not positive.

numberlink.generator._apply_loop_moves(path: list[Coord], rng: numpy.random.Generator, attempts: int = 128) → None

Apply random 2-opt style loop reversals to introduce variety while preserving coverage.

Modify path in place by performing loop reversals that preserve path contiguity. A reversal is applied only when the candidate move keeps the path contiguous according to _are_adjacent(). Increase attempts for more mixing or reduce it for speed.

Parameters:

• path (list[Coord]) – Hamiltonian path represented as a list of (row, column) coordinates.

• rng (numpy.random.Generator) – Numpy random number generator used to select indices. See numpy.random.

• attempts (int, optional) – Number of random move trials to perform. Defaults to 128.

Returns:

None. The input path is modified in place.

Return type:

None

numberlink.generator._compute_conflict_min_starts(path: list[Coord]) → list[int]

Identify the earliest valid segment start index for each position in the Hamiltonian path.

Compute constraints that prevent partitioned segments from producing adjacent endpoints that belong to different segments. For each path index i the returned list contains the minimum allowed start index for a segment that ends at i.

Parameters:

path (list[Coord]) – Hamiltonian path as a list of coordinates.

Returns:

For each index i the earliest allowed start index for a segment ending at i.

Return type:

list[int]

numberlink.generator._partition_choices(pos: int, segments_left: int, total_cells: int, min_len: int, min_start: list[int], rng: numpy.random.Generator, memo: dict[Coord, tuple[int, ...] | None]) → tuple[int, ...] | None

Compute viable segment endpoints for dynamic partitioning of a Hamiltonian path.

This recursive helper for _partition_path_into_segments() uses memoization to avoid repeated work. It enforces the minimum segment length and the adjacency constraints produced by _compute_conflict_min_starts().

Parameters:

• pos (int) – Current path index where a new segment would begin.

• segments_left (int) – Number of segments remaining to place.

• total_cells (int) – Total number of cells in the Hamiltonian path.

• min_len (int) – Minimum allowed length for a segment.

• min_start (list[int]) – Constraint list returned by _compute_conflict_min_starts().

• rng (numpy.random.Generator) – Random number generator used to break ties when the caller needs a random choice.

• memo (dict[Coord, tuple[int, ...] | None]) – Memoization mapping keyed by tuples (pos, segments_left).

Returns:

Tuple of viable end indices for a segment starting at pos or None when no viable choices exist.

Return type:

tuple[int, …] or None

numberlink.generator._build_partition(pos: int, segments_left: int, total_cells: int, min_len: int, min_start: list[int], rng: numpy.random.Generator, memo: dict[Coord, tuple[int, ...] | None], segments_bounds: list[Coord]) → bool

Recursively construct segment bounds for a Hamiltonian path partition.

Attempt to place segments_left contiguous segments starting at pos. For the current position query _partition_choices() to obtain viable end indices and choose one uniformly using rng. Append chosen bounds to segments_bounds. The recursion succeeds when the chosen bounds cover total_cells.

Parameters:

• pos (int) – Current start index for the next segment.

• segments_left (int) – Number of segments remaining to place.

• total_cells (int) – Total number of cells in the path.

• min_len (int) – Minimum allowed length of each segment.

• min_start (list[int]) – Adjacency constraint list returned by _compute_conflict_min_starts().

• rng (numpy.random.Generator) – Random number generator used for uniform tie breaking.

• memo (dict[Coord, tuple[int, ...] | None]) – Memoization mapping shared with _partition_choices().

• segments_bounds (list[Coord]) – Output list that will receive chosen (start, end) index tuples.

Returns:

True if a complete partition covering total_cells was constructed, otherwise False.

Return type:

bool

numberlink.generator._partition_path_into_segments(path: list[Coord], n_segments: int, min_len: int, rng: numpy.random.Generator) → list[list[Coord]] | None

Split a Hamiltonian path into contiguous segments while avoiding adjacent endpoints.

Attempt to partition path into n_segments contiguous subpaths. Each subpath has at least min_len nodes. The endpoints of different segments are not adjacent on the grid. The partitioning uses _partition_choices() and the adjacency constraints from _compute_conflict_min_starts().

Parameters:

• path (list[Coord]) – Hamiltonian path that covers every grid cell.

• n_segments (int) – Desired number of segments.

• min_len (int) – Minimum allowed length of each segment.

• rng (numpy.random.Generator) – Random number generator used to break ties when multiple partitions are possible.

Returns:

List of segments when partitioning succeeds or None when no valid partition exists.

Return type:

list[list[Coord]] or None

numberlink.generator._compute_segment_map(segments: list[list[Coord]], height: int, width: int) → numpy.typing.NDArray[numpy.int16]

Compute a 2D numpy array that maps each grid cell to its segment index.

The returned array uses -1 to indicate unassigned cells. Raise ValueError when a segment contains a coordinate that is outside the grid bounds or when two segments assign the same cell.

Parameters:

• segments (list[list[Coord]]) – List of segments where each segment is a list of coordinates.

• height (int) – Grid row count.

• width (int) – Grid column count.

Returns:

Numpy array with shape (height, width) mapping each cell to its segment index.

Return type:

numpy.ndarray

Raises:

ValueError – If a segment cell is outside grid bounds or if segments overlap on the same cell.

numberlink.generator._validate_segments(segments: list[list[Coord]], seg_map: numpy.typing.NDArray[numpy.int16], min_nodes: int) → None

Validate that every segment is a simple path and meets NumberLink constraints.

Perform the following checks. Each segment length is at least max(3, min_nodes). Each segment is contiguous as defined by _are_adjacent(). Segment endpoints are not adjacent to each other. Using seg_map ensure that each grid cell is assigned and that each segment has exactly two endpoints when measured on the grid.

Parameters:

• segments (list[list[Coord]]) – Partitioned segments to validate.

• seg_map (numpy.ndarray) – Grid mapping produced by _compute_segment_map().

• min_nodes (int) – Minimum nodes a single segment must contain. Effective minimum is max(3, min_nodes).

Returns:

None when validation succeeds.

Return type:

None

Raises:

ValueError – When any validation rule fails.

numberlink.generator._segments_to_level(segments: list[list[Coord]], height: int, width: int) → list[str]

Render segment endpoints onto the puzzle grid.

Assign an uppercase letter to each segment starting at 'A'. Place only the endpoints of each segment on the returned grid. Return a list of strings where each string represents a row and the dot character represents an empty cell.

Parameters:

• segments (list[list[Coord]]) – List of segments where each segment is a list of coordinates.

• height (int) – Grid row count.

• width (int) – Grid column count.

Returns:

Puzzle grid as a list of row strings.

Return type:

list[str]

numberlink.generator._shortest_dist(a: Coord, b: Coord, allow_diagonal: bool = False) → int

Compute the shortest grid distance between two coordinates using the configured movement rules.

Return the Chebyshev distance when allow_diagonal is True. Otherwise return the Manhattan distance.

Parameters:

• a (Coord) – First coordinate as a (row, column) pair.

• b (Coord) – Second coordinate as a (row, column) pair.

• allow_diagonal (bool) – Whether diagonal movement is permitted.

Returns:

Shortest distance between a and b according to the configured movement rules.

Return type:

int

numberlink.generator._sample_start_cell(used_endpoints: set[Coord], h: int, w: int, rng: numpy.random.Generator) → Coord

Sample a start cell uniformly among cells not in used_endpoints.

Parameters:

• used_endpoints (set[Coord]) – Set of coordinates already used as endpoints.

• h (int) – Grid row count.

• w (int) – Grid column count.

• rng (numpy.random.Generator) – Random number generator used for uniform sampling.

Returns:

Sampled coordinate that is not in used_endpoints.

Return type:

Coord

numberlink.generator._gen_random_walk(cfg: numberlink.config.GeneratorConfig, *, variant: numberlink.config.VariantConfig) → numberlink.levels.Level

Generate a puzzle by placing endpoints using per-color random walks.

For each color the algorithm performs the following steps

1. Choose a random start cell that is not already used as an endpoint.

2. Perform a random walk that avoids cells occupied by previous walks.

3. End at a different cell when the walk satisfies the minimum length requirement.

4. Ensure the shortest path distance between endpoints meets the configured minimum.

Only endpoints are placed on the returned grid. Intermediate walk cells are marked as occupied to prevent other colors from using them. When cfg.bridges_probability is greater than 0.0 the function may return a set of bridge coordinates in the numberlink.levels.Level result.

Parameters:

cfg (numberlink.config.GeneratorConfig) – Generator configuration object. See numberlink.config.GeneratorConfig.

Returns:

Generated puzzle level with endpoint letters and optional bridges.

Return type:

numberlink.levels.Level

Raises:

ValueError – If grid dimensions or color count are invalid, if the configured minimum path length is too large for the board, or if the generator cannot place valid endpoints after the configured number of attempts.