gaps reassembles jigsaw puzzles with a genetic algorithm and automatic piece size detection

A photograph that gets cut up and has to be put back

gaps takes an ordinary image, cuts it into square tiles, and then solves the puzzle it just created. The README describes it as a genetic algorithm based solver for jigsaw puzzles with piece size auto-detection, and the project is written in Python under the MIT License. The hard part is not the cutting. Once the tiles exist, none of them carries a printed border, a corner marker or a coordinate, so the tool has to recover both which pieces touch and what the finished rectangle looks like from raw pixels. The project cites a 2016 paper by Dror Sholomon, Omid E. David and Nathan S. Netanyahu on automatically solving very large jigsaw puzzles using genetic algorithms, and the solver keeps that shape of thinking: score candidate neighbours cheaply, then let an evolutionary search explore arrangements. People who end up using it tend to be photographers who want a printable puzzle, teachers looking for a visual exercise, and engineers curious about how a search over permutations behaves when the only signal is image continuity.

How the fitness function turns pixels into neighbour preferences

The core of the solver is a cost function over tile edges, and the README describes it in a precise order. First it extracts directed horizontal and vertical edge costs using multi scale pixel and gradient comparisons, so a tile is scored against its neighbour on both sides. The population is then seeded by mixing confidence aware beam searched arrangements with random ones, which keeps useful regions while preserving variety for ambiguous edges and repetitive textures. Evolution uses tournament selection and a crossover that preserves strong parent edges and high confidence blocks. On top of that come adaptive mutation, local search over swaps, relocations and block moves, exact small window constraint repair, elitism, and restarts triggered by stagnation. The run ends by returning the best valid arrangement it found. Two consequences follow from that design. Fitness is edge based rather than whole image based, so a locally convincing seam can still lead to a globally wrong layout, and the local search operators matter as much as the genetic machinery in practice.

From a clone to a solved image in four commands

Installation is documented as a plain clone plus a uv sync, and the README is explicit that Python 3.12.x is required, which matches the requires-python constraint of ">=3.12,<3.13" in pyproject.toml. Start by copying the repository and entering it:

git clone https://github.com/nemanja-m/gaps.git
cd gaps

Then install the project and its development requirements. The README suggests installing uv first if it is not already available, and then syncing the environment:

uv sync

The gaps command lives in the project environment, so it is run through uv. A first useful step is generating the puzzle itself from an image that ships with the repository:

uv run gaps create images/pillars.jpg puzzle.jpg --size=64

That produces a puzzle of 240 pieces where each piece is 64 by 64 pixels. Solving it is the same shape of command, with the search budget spelled out:

uv run gaps run puzzle.jpg solution.jpg --generations=20 --population=600

The README notes that the created puzzle image dimensions may be smaller than the original image depending on the given piece size, because the maximum possible rectangle is cropped from the source.

Size detection is convenient, and it is the most likely thing to go wrong

The feature that sets this project apart from a plain genetic algorithm demo is the piece size auto detection. If you do not pass --size to the run command, the tool infers it, which removes the most annoying guesswork when you already generated a puzzle and lost the original numbers. You can always pin it explicitly, and the README shows that form with a fixed 48 pixel piece size:

uv run gaps run puzzle.jpg solution.jpg --generations=20 --population=600 --size=48

The caveat is stated plainly in the same document: the size detection feature works for most images, but there are some edge cases where it fails and detects an incorrect piece size. That is a real failure mode rather than a theoretical one, because a wrong piece size means the tile grid does not match the image, and no amount of search effort can fix that. For automated pipelines, the safe path is to record the --size value used at creation time and pass it to the run command rather than relying on inference. The README also suggests using --seed on both create and run when reproducible shuffling and solving are required, which is the pairing that makes a pipeline result repeatable.

Worker processes speed up child generation but change the search path

Child generation is the CPU bound part of the loop, so the solver can spread it over several processes. The parallel invocation looks almost identical to the serial one:

uv run gaps run puzzle.jpg solution.jpg --generations=20 --population=600 --workers=4

The README is unusually clear about what this does to the algorithm, and it is worth reading before benchmarking anything. Worker mode uses deterministic per-child seeds, so runs with the same input, seed and worker count are reproducible. The serial mode with --workers=1 remains the reference backend, and parallel runs may produce a different valid genetic search trajectory. In other words, reproducibility is guaranteed within a fixed worker count, not across worker counts, and a parallel run is not a drop in equivalent for the serial one in terms of the intermediate solutions it passes through. The available options are --size, --generations, --population, --debug, --seed and --workers, where --debug shows the best solution after each generation, which is the most useful flag when you want to see whether a run is actually improving or sitting flat.

The run stops on stagnation, not on a solved puzzle

The termination logic follows the standard argument for genetic algorithms, and the README spells the reasoning out: early iterations tend to bring better solutions every few steps, and that progress saturates later, where the improvements are very small. Rather than keep burning cycles for marginal gains, gaps ends the run when there has been no improvement in the population for a set number of iterations, or when it reaches an absolute number of generations. The practical reading is that a run which ends has not necessarily been solved. It has simply stopped finding anything better, which is exactly the state a human solver would also reach, squinting at an image that looks almost right. There is no separate quality threshold in the documented options, so judging the output is on the reader. Because the solver assumes a known rectangular layout and fixed piece orientation, it also cannot handle irregular piece shapes, rotated pieces or a variable row and column count, and the README does not document any way to relax that assumption.

MIT licensed, small dependency set, no tagged releases

The project publishes under the MIT License, which is permissive and carries no notable conditions beyond preserving the copyright notice, though the legal text itself is what governs use. The runtime dependencies listed in pyproject.toml are pillow, numpy, opencv-python and click, and the project is packaged with the uv build backend. Development tooling includes pytest, pytest-benchmark, ruff and pyrefly, and the pytest configuration deselects the benchmark marker by default, so benchmarks are opt in rather than part of a normal test run. The package version in pyproject.toml is 0.1.0, the repository has no GitHub releases, and the last push was on 2026-09-20. That combination says the project is recent and lightly versioned: there is no release history to upgrade through, so upgrading means pulling the main branch and re-running uv sync, and there is no published changelog to tell you what changed between two points in time.

Editorial conclusion

gaps fits photographers, teachers and engineers who want a puzzle generator and solver in one command line tool, and it is a reasonable base for image matching experiments since the code is small and MIT licensed. It is the wrong choice for irregular or rounded piece sets, for puzzles whose piece count is unknown, or for anyone who needs a guaranteed optimal arrangement, because the search is heuristic and the README states that size detection fails on some edge cases. Before adopting it, generate a puzzle from an image close to your own, check the detected piece size against the value you expected, and confirm that a worker run with your chosen --workers count still converges inside the generation budget you set.

Frequently asked questions

Official sources

1. Issues
2. License: MIT
3. nemanja-m/gaps on GitHub
4. README