Further Hardness Results for Stephen’s Sausage Roll

Stephen’s Sausage Roll is a relatively unstudied puzzle game with a fascinating set of mechanics for computational hardness problems. The only past results are from a class project in MIT’s 6.5440 class of Fall 2023, which only dealt with two specific subsets of the mechanics restricted to two-dimensional forms of the game [1]. This project presents a more complete characterization of problems based off of Stephen’s Sausage Roll, and provides solutions for a significant portion. In particular, both variants of Stephen’s Sausage Roll considered in prior work can be solved by one of these results.

Name thesis:degree_name

Master

Department dc:contributor.department

Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science

Grantor dc:publisher

Massachusetts Institute of Technology

Year dc:date.issued

2024

Author dc:creator

• Liu, Jason

Advisor dc:contributor.advisor

• Demaine, Erik D.

Statement dc:rights

• In Copyright - Educational Use Permitted
• Copyright retained by author(s)

Licence dc:rights.uri

• https://rightsstatements.org/page/InC-EDU/1.0/

Handle dc:identifier.uri

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

OAI identifier oai:identifier

oai:dspace.mit.edu:1721.1/156825