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

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

Internet

https://hdl.handle.net/1721.1/143956

Similar Items