PackIt! Gamified Rectangle Packing
<|reference_start|>PackIt! Gamified Rectangle Packing: We present and analyze PackIt!, a turn-based game consisting of packing rectangles on an $n \times n$ grid. PackIt! can be easily played on paper, either as a competitive two-player game or in \emph{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 \times n$ grid. We analyze conditions for the existence of a perfect packing over $n \times 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.<|reference_end|>
@article{garrison2024packit!,
    title={PackIt! Gamified Rectangle Packing},
    author={Thomas Garrison, Marijn J.H. Heule, and Bernardo Subercaseaux},
    journal={arXiv preprint arXiv:2403.12195},
    year={2024},
    archivePrefix={arXiv},
    eprint={2403.12195},
    primaryClass={math.CO cs.DS cs.GT}
}