Finding All Solutions and Instances of Numberlink and Slitherlink by ZDDs
Link puzzles involve finding paths or a cycle in a grid that satisfy given local and global properties. This paper proposes algorithms that enumerate solutions and instances of two link puzzles, Slitherlink and Numberlink, by zero-suppressed binary decision diagrams (ZDDs). A ZDD is a compact data s...
| Main Authors: | , , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2012-04-01
|
| Series: | Algorithms |
| Subjects: | |
| Online Access: | http://www.mdpi.com/1999-4893/5/2/176/ |
| _version_ | 1811273763933650944 |
|---|---|
| author | Shin-ichi Minato Koji Tsuruma Hiroaki Iwashita Ryo Yoshinaka Toshiki Saitoh Jun Kawahara |
| author_facet | Shin-ichi Minato Koji Tsuruma Hiroaki Iwashita Ryo Yoshinaka Toshiki Saitoh Jun Kawahara |
| author_sort | Shin-ichi Minato |
| collection | DOAJ |
| description | Link puzzles involve finding paths or a cycle in a grid that satisfy given local and global properties. This paper proposes algorithms that enumerate solutions and instances of two link puzzles, Slitherlink and Numberlink, by zero-suppressed binary decision diagrams (ZDDs). A ZDD is a compact data structure for a family of sets provided with a rich family of set operations, by which, for example, one can easily extract a subfamily satisfying a desired property. Thanks to the nature of ZDDs, our algorithms offer a tool to assist users to design instances of those link puzzles. |
| first_indexed | 2024-04-12T23:06:20Z |
| format | Article |
| id | doaj.art-e8d4bf7509dd4ca38f67ce7549273c20 |
| institution | Directory Open Access Journal |
| issn | 1999-4893 |
| language | English |
| last_indexed | 2024-04-12T23:06:20Z |
| publishDate | 2012-04-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Algorithms |
| spelling | doaj.art-e8d4bf7509dd4ca38f67ce7549273c202022-12-22T03:12:55ZengMDPI AGAlgorithms1999-48932012-04-015217621310.3390/a5020176Finding All Solutions and Instances of Numberlink and Slitherlink by ZDDsShin-ichi MinatoKoji TsurumaHiroaki IwashitaRyo YoshinakaToshiki SaitohJun KawaharaLink puzzles involve finding paths or a cycle in a grid that satisfy given local and global properties. This paper proposes algorithms that enumerate solutions and instances of two link puzzles, Slitherlink and Numberlink, by zero-suppressed binary decision diagrams (ZDDs). A ZDD is a compact data structure for a family of sets provided with a rich family of set operations, by which, for example, one can easily extract a subfamily satisfying a desired property. Thanks to the nature of ZDDs, our algorithms offer a tool to assist users to design instances of those link puzzles.http://www.mdpi.com/1999-4893/5/2/176/link puzzlesSlitherlinkNumberlinksolversinstance generations |
| spellingShingle | Shin-ichi Minato Koji Tsuruma Hiroaki Iwashita Ryo Yoshinaka Toshiki Saitoh Jun Kawahara Finding All Solutions and Instances of Numberlink and Slitherlink by ZDDs Algorithms link puzzles Slitherlink Numberlink solvers instance generations |
| title | Finding All Solutions and Instances of Numberlink and Slitherlink by ZDDs |
| title_full | Finding All Solutions and Instances of Numberlink and Slitherlink by ZDDs |
| title_fullStr | Finding All Solutions and Instances of Numberlink and Slitherlink by ZDDs |
| title_full_unstemmed | Finding All Solutions and Instances of Numberlink and Slitherlink by ZDDs |
| title_short | Finding All Solutions and Instances of Numberlink and Slitherlink by ZDDs |
| title_sort | finding all solutions and instances of numberlink and slitherlink by zdds |
| topic | link puzzles Slitherlink Numberlink solvers instance generations |
| url | http://www.mdpi.com/1999-4893/5/2/176/ |
| work_keys_str_mv | AT shinichiminato findingallsolutionsandinstancesofnumberlinkandslitherlinkbyzdds AT kojitsuruma findingallsolutionsandinstancesofnumberlinkandslitherlinkbyzdds AT hiroakiiwashita findingallsolutionsandinstancesofnumberlinkandslitherlinkbyzdds AT ryoyoshinaka findingallsolutionsandinstancesofnumberlinkandslitherlinkbyzdds AT toshikisaitoh findingallsolutionsandinstancesofnumberlinkandslitherlinkbyzdds AT junkawahara findingallsolutionsandinstancesofnumberlinkandslitherlinkbyzdds |