Edge Matching with Inequalities, Triangles, Unknown Shape, and Two Players

© 2020 Information Processing Society of Japan. We analyze the computational complexity of several new variants of edge-matching puzzles. First we analyze inequality (instead of equality) constraints between adjacent tiles, proving the problem NP-complete for strict inequalities but polynomial-time...

Full description

Bibliographic Details
Main Authors: Bosboom, Jeffrey, Chen, Charlotte, Chung, Lily, Compton, Spencer, Coulombe, Michael, Demaine, Erik D, Demaine, Martin L, Filho, Ivan Tadeu Ferreira Antunes, Hendrickson, Dylan, Hesterberg, Adam, Hsu, Calvin, Hu, William, Korten, Oliver, Luo, Zhezheng, Zhang, Lillian
Other Authors: Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory
Format: Article
Language:English
Published: Information Processing Society of Japan 2022
Online Access:https://hdl.handle.net/1721.1/143956
Description
Summary:© 2020 Information Processing Society of Japan. We analyze the computational complexity of several new variants of edge-matching puzzles. First we analyze inequality (instead of equality) constraints between adjacent tiles, proving the problem NP-complete for strict inequalities but polynomial-time solvable for nonstrict inequalities. Second we analyze three types of triangular edge matching, of which one is polynomial-time solvable and the other two are NP-complete; all three are #P-complete. Third we analyze the case where no target shape is specified and we merely want to place the (square) tiles so that edges match exactly; this problem is NP-complete. Fourth we consider four 2-player games based on 1×n edge matching, all four of which are PSPACE-complete. Most of our NP-hardness reductions are parsimonious, newly proving #P and ASP-completeness for, e.g., 1 × n edge matching. Along the way, we prove #P-and ASP-completeness of planar 3-regular directed Hamiltonicity; we provide linear-time algorithms to find antidirected and forbidden-transition Eulerian paths; and we characterize the complexity of new partizan variants of the Geography game on graphs.