@inproceedings{804448be62be496d95f1b4414654ac2c,
title = "Spatial planning as a hexomino puzzle",
abstract = "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.",
keywords = "Benchmark generation, Dancing links, Exact cover, Hexomino puzzle",
author = "Marcin Cwiek and Jakub Nalepa",
note = "Publisher Copyright: {\textcopyright} Springer International Publishing AG 2017.; 9th Asian Conference on Intelligent Information and Database Systems, ACIIDS 2017 ; Conference date: 03-04-2017 Through 05-04-2017",
year = "2017",
doi = "10.1007/978-3-319-54472-4\_39",
language = "English",
isbn = "9783319544717",
series = "Lecture Notes in Computer Science",
publisher = "Springer Verlag",
pages = "410--420",
editor = "Nguyen, \{Ngoc Thanh\} and Bogdan Trawinski and Satoshi Tojo and Nguyen, \{Le Minh\}",
booktitle = "Intelligent Information and Database Systems - 9th Asian Conference, ACIIDS 2017, Proceedings",
address = "Germany",
}