An Eight-Year-Old Polyomino Tiling Algorithm: Backtracking Search with Heuristics
This article details an algorithm for solving the polyomino tiling problem. The core idea is to transform the geometric problem into a graph theory problem and use a backtracking search algorithm with various heuristics. First, the algorithm preprocesses to calculate all possible placements, constructing a bipartite graph representing all possibilities. Then, a backtracking search algorithm finds a subset of placements satisfying the conditions, optimized by heuristics such as prioritizing constrained grid points and splitting the grid. The algorithm demonstrates good generality and robustness in handling arbitrary grid shapes and polyomino sets. The author also discusses limitations and future improvements, such as transforming the problem into a SAT problem for solution.