A Polyomino Tiling Algorithm (2018)

Over eight years ago I created the Polyomino Tiler (a browser application that attempts to tile arbitrary grids with sets of polyominoes), but I haven't ever written about the algorithm it uses. If any aspects of what follows are confusing, it may help to play with the polyomino tiler a bit to get a better idea for what it's doing. There are a couple aspects of the problem that combine to make it challenging: the set of available polyominos is fully customizable up to the heptominoes; each polyomino can be restricted to specific flips/rotations the grid can be any subset of a rectangular grid (or a cylinder/torus) So the algorithm needs to be generic enough to not get bogged down in all the edge cases resulting from these two facts. The two key components of the algorithm are: abstract away the geometric details by constructing a graph that describes all the possibilities apply certain heuristics to a generic backtracking search algorithm on that graph Placements The main pre ... Read full article.