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-dimen...
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Thesis |
| Published: |
Massachusetts Institute of Technology
2024
|
| Online Access: | https://hdl.handle.net/1721.1/156825 |
| _version_ | 1811071642216955904 |
|---|---|
| author | Liu, Jason |
| author2 | Demaine, Erik D. |
| author_facet | Demaine, Erik D. Liu, Jason |
| author_sort | Liu, Jason |
| collection | MIT |
| description | 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. |
| first_indexed | 2024-09-23T08:54:24Z |
| format | Thesis |
| id | mit-1721.1/156825 |
| institution | Massachusetts Institute of Technology |
| last_indexed | 2024-09-23T08:54:24Z |
| publishDate | 2024 |
| publisher | Massachusetts Institute of Technology |
| record_format | dspace |
| spelling | mit-1721.1/1568252024-09-17T04:00:48Z Further Hardness Results for Stephen’s Sausage Roll Liu, Jason Demaine, Erik D. Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science 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. M.Eng. 2024-09-16T13:51:26Z 2024-09-16T13:51:26Z 2024-05 2024-07-11T14:37:04.884Z Thesis https://hdl.handle.net/1721.1/156825 In Copyright - Educational Use Permitted Copyright retained by author(s) https://rightsstatements.org/page/InC-EDU/1.0/ application/pdf Massachusetts Institute of Technology |
| spellingShingle | Liu, Jason Further Hardness Results for Stephen’s Sausage Roll |
| title | Further Hardness Results for Stephen’s Sausage Roll |
| title_full | Further Hardness Results for Stephen’s Sausage Roll |
| title_fullStr | Further Hardness Results for Stephen’s Sausage Roll |
| title_full_unstemmed | Further Hardness Results for Stephen’s Sausage Roll |
| title_short | Further Hardness Results for Stephen’s Sausage Roll |
| title_sort | further hardness results for stephen s sausage roll |
| url | https://hdl.handle.net/1721.1/156825 |
| work_keys_str_mv | AT liujason furtherhardnessresultsforstephenssausageroll |