Spatial Planning as a Hexomino Puzzle

摘要

Exact cover problem is a well-known NP-complete decision problem to determine if the exact cover really exists. In this paper, we show how to solve a modified version of the famous Hexomino puzzle (being a noteworthy example of an exact cover problem) using a Dancing-links based algorithm. In this modified problem, a limited number of gaps in the rectangular box may be left uncovered (this is a common scenario in a variety of spatial planning problems). Additionally, we present the benchmark generator which allows for elaborating very demanding yet solvable problem instances. These instances were used during the qualifying round of Deadline24 - an international 24-h programming marathon. Finally, we confront our baseline solutions with those submitted by the contestants, and elaborated using our two solvers.