2026-08-17T02:43:02Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:19922 2024-05-29T09:43:30Z ddc:004 open_access

PackIt!: Gamified Rectangle Packing Garrison, Thomas Heule, Marijn J. H. Subercaseaux, Bernardo PackIt! rectangle packing SAT NP-hardness 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Thomas Garrison and Marijn J. H. Heule and Bernardo Subercaseaux 2024 Is Part Of LIPIcs, Volume 291, 12th International Conference on Fun with Algorithms (FUN 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FUN.2024.14 urn:nbn:de:0030-drops-199226 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2024.14 eng https://creativecommons.org/licenses/by/4.0/legalcode