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
_version_ 1826196309950857216
author 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
author2 Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory
author_facet Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory
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
author_sort Bosboom, Jeffrey
collection MIT
description © 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.
first_indexed 2024-09-23T10:24:33Z
format Article
id mit-1721.1/143956
institution Massachusetts Institute of Technology
language English
last_indexed 2024-09-23T10:24:33Z
publishDate 2022
publisher Information Processing Society of Japan
record_format dspace
spelling mit-1721.1/1439562023-07-28T17:19:30Z Edge Matching with Inequalities, Triangles, Unknown Shape, and Two Players 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 Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory © 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. 2022-07-22T14:10:08Z 2022-07-22T14:10:08Z 2020 2022-07-22T14:06:12Z Article http://purl.org/eprint/type/JournalArticle https://hdl.handle.net/1721.1/143956 Bosboom, Jeffrey, Chen, Charlotte, Chung, Lily, Compton, Spencer, Coulombe, Michael et al. 2020. "Edge Matching with Inequalities, Triangles, Unknown Shape, and Two Players." Journal of Information Processing, 28 (0). en 10.2197/IPSJJIP.28.987 Journal of Information Processing Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/pdf Information Processing Society of Japan arXiv
spellingShingle 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
Edge Matching with Inequalities, Triangles, Unknown Shape, and Two Players
title Edge Matching with Inequalities, Triangles, Unknown Shape, and Two Players
title_full Edge Matching with Inequalities, Triangles, Unknown Shape, and Two Players
title_fullStr Edge Matching with Inequalities, Triangles, Unknown Shape, and Two Players
title_full_unstemmed Edge Matching with Inequalities, Triangles, Unknown Shape, and Two Players
title_short Edge Matching with Inequalities, Triangles, Unknown Shape, and Two Players
title_sort edge matching with inequalities triangles unknown shape and two players
url https://hdl.handle.net/1721.1/143956
work_keys_str_mv AT bosboomjeffrey edgematchingwithinequalitiestrianglesunknownshapeandtwoplayers
AT chencharlotte edgematchingwithinequalitiestrianglesunknownshapeandtwoplayers
AT chunglily edgematchingwithinequalitiestrianglesunknownshapeandtwoplayers
AT comptonspencer edgematchingwithinequalitiestrianglesunknownshapeandtwoplayers
AT coulombemichael edgematchingwithinequalitiestrianglesunknownshapeandtwoplayers
AT demaineerikd edgematchingwithinequalitiestrianglesunknownshapeandtwoplayers
AT demainemartinl edgematchingwithinequalitiestrianglesunknownshapeandtwoplayers
AT filhoivantadeuferreiraantunes edgematchingwithinequalitiestrianglesunknownshapeandtwoplayers
AT hendricksondylan edgematchingwithinequalitiestrianglesunknownshapeandtwoplayers
AT hesterbergadam edgematchingwithinequalitiestrianglesunknownshapeandtwoplayers
AT hsucalvin edgematchingwithinequalitiestrianglesunknownshapeandtwoplayers
AT huwilliam edgematchingwithinequalitiestrianglesunknownshapeandtwoplayers
AT kortenoliver edgematchingwithinequalitiestrianglesunknownshapeandtwoplayers
AT luozhezheng edgematchingwithinequalitiestrianglesunknownshapeandtwoplayers
AT zhanglillian edgematchingwithinequalitiestrianglesunknownshapeandtwoplayers