DROPS

Document

DOI: 10.4230/LIPIcs.FUN.2024.14

PackIt!: Gamified Rectangle Packing

Authors: Thomas Garrison, Marijn J. H. Heule, and Bernardo Subercaseaux

Published in: LIPIcs, Volume 291, 12th International Conference on Fun with Algorithms (FUN 2024)

Abstract

We present and analyze PackIt!, a turn-based game consisting of packing rectangles on an n × n grid. PackIt! can be easily played on paper, either as a competitive two-player game or in solitaire fashion. On the t-th turn, a rectangle of area t or t+1 must be placed in the grid. In the two-player format of PackIt! whichever player places a rectangle last wins, whereas the goal in the solitaire variant is to perfectly pack the n × n grid. We analyze necessary conditions for the existence of a perfect packing over n × n, then present an automated reasoning approach that allows finding perfect games of PackIt! up to n = 50 which includes a novel SAT-encoding technique of independent interest, and conclude by proving an NP-hardness result.

Cite as

Thomas Garrison, Marijn J. H. Heule, and Bernardo Subercaseaux. PackIt!: Gamified Rectangle Packing. In 12th International Conference on Fun with Algorithms (FUN 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 291, pp. 14:1-14:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{garrison_et_al:LIPIcs.FUN.2024.14,
  author =	{Garrison, Thomas and Heule, Marijn J. H. and Subercaseaux, Bernardo},
  title =	{{PackIt!: Gamified Rectangle Packing}},
  booktitle =	{12th International Conference on Fun with Algorithms (FUN 2024)},
  pages =	{14:1--14:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-314-0},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{291},
  editor =	{Broder, Andrei Z. and Tamir, Tami},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2024.14},
  URN =		{urn:nbn:de:0030-drops-199226},
  doi =		{10.4230/LIPIcs.FUN.2024.14},
  annote =	{Keywords: PackIt!, rectangle packing, SAT, NP-hardness}
}

Search Results

Documents authored by Garrison, Thomas

PackIt!: Gamified Rectangle Packing

Abstract

Cite as