Table of Contents
Given a 2D grid and a predicate that defines when one cell is reachable from another, how can we find a set of loops that visit each cell exactly once?
One solution is to convert this problem into an instance of the more general exact-cover problem, then use an exact-cover solver like DLX from Python to find solutions.
Encoding
Note: For the rest of the text, columns and rows will refer to the columns and rows of the exact-cover problem, not the 2D grid that is being tiled.
If the grid is fully filled with directed loops, each cell is entered
once and exited once.
We'll encode this through incoming and outgoing columns
for each cell.
from itertools import product def columns(width: int, height: int) -> set[str]: return { f"{d}_{x}_{y}" for d, x, y in product(("I", "O"), range(width), range(height)) }
The rows encode how cells are connected to each other. We'll express
this as a predicate on the absolute distances in x and y directions,
limiting the search to within
dist
of the current position.
from typing import Callable Pred = Callable[[int, int], bool] def gen_problem(width: int, height: int, pred: Pred, dist: int): p = Problem(columns(width, height)) for x1, y1 in product(range(width), range(height)): rx = range(max(0, x1 - dist), min(width, x1 + dist + 1)) ry = range(max(0, y1 - dist), min(height, y1 + dist + 1)) for x2, y2 in product(rx, ry): dx = abs(x1 - x2) dy = abs(y1 - y2) if pred(dx, dy): p.add_row({f"O_{x1}_{y1}", f"I_{x2}_{y2}"}) return p
Decoding
Each row in the solution corresponds to a line between two cells. The start and end points of these lines can be found by parsing each column name into a direction and an (x,y) position.
from typing import Generator Line = tuple[tuple[int, int], tuple[int, int]] def decode_solution(rows) -> Generator[Line]: for row in rows: toks = (e.split("_") for e in row) lu = {d: (int(x), int(y)) for d, x, y in toks} yield lu["O"], lu["I"]
SVG Rendering
An easy way to visualize the solutions is to draw all lines in an SVG file.
from dataclasses import dataclass, field @dataclass class Renderer: width: int height: int _lines: list[Line] = field(default_factory=list) def add_line(self, line): self._lines.append(line) def _format_line(self, line, scale): (x1, y1), (x2, y2) = line def tr(p): return (p + 0.5) * scale return f'<line x1="{tr(x1)}" y1="{tr(y1)}" x2="{tr(x2)}" y2="{tr(y2)}" stroke="black" />' def _format(self, scale: int): width = self.width * scale height = self.height * scale yield f'<svg xmlns="http://www.w3.org/2000/svg" width="{width}" height="{height}">\n' for line in self._lines: yield self._format_line(line, scale) yield '</svg>' def render_file(self, path: str, scale: int): with open(path, "w") as f: for line in self._format(scale): f.write(line)
Results
Finally, we define a helper function to find and render a tiling for a given predicate.
<<init_problem>> <<columns>> <<encoder>> <<decoder>> <<renderer>> def render_pred(name, width, height, scale, pred, dist): s = Solver(limit=1) p = gen_problem(width, height, pred, dist=dist) if solution := s.solve_single(p): lines = decode_solution(solution) r = Renderer(width, height) for line in lines: r.add_line(line) r.render_file(f"{output_dir}/{name}.svg", scale)
Four Neighbors
One simple predicate connects each cell to its top, right, bottom and left neighbors.
<<render_helper>> def can_reach(dx, dy) -> bool: return min(dx, dy) == 0 and max(dx, dy) == 1 render_pred("n4", 32, 16, 40, can_reach, 1)
What look like single lines here are loops (a)->(b)->(a). Rather than switching to a more complicated encoding to prevent these, we'll explore a few other predicates.
Eight Neighbors
<<render_helper>> def can_reach(dx, dy) -> bool: return max(dx, dy) == 1 render_pred("n8", 32, 16, 40, can_reach, 1)
Knight Moves
A chess knight can move two squares in one direction and one square in a direction perpendicular to the first.
<<render_helper>> def can_reach(dx, dy) -> bool: return min(dx, dy) == 1 and max(dx, dy) == 2 render_pred("knight", 32, 16, 40, can_reach, 2)
