3 ms·

Beyond the wall: Working with aperiodic tilings using finite-state transducers

60 points by robinhouston 2y ago

johanvts 2y ago
The original hat tile paper came with a nice webdemo (https://github.com/isohedral/hatviz https://github.com/isohedral/hatviz) for recursively builidng a tiling following the method in the paper. I have a version with a few additions (Truchet patterns) hosted if anyone wants to play around with it here: https://www.johansivertsen.com/customhatviz/app.html https://www.johansivertsen.com/customhatviz/app.html
carb 2y ago
really fun read and great diagrams throughout!
fanf2 2y ago
Simon developed these algorithms for his puzzle Loopy https://www.chiark.greenend.org.uk/~sgtatham/puzzles/js/loopy.html https://www.chiark.greenend.org.uk/~sgtatham/puzzles/js/loop... - bop the “type” menu to choose which tiling to play the game on, including Penrose, Hats, Spectres, and many others.
- o11c 2y ago
  The interesting thing about Loopy (compared to other SGT puzzles) is how differently the game plays depending on choice of tiling: * if vertexes have few edges, it's easier to figure out how/if the loop passes through that vertex, but once you do it doesn't imply much about the rest of the puzzle * if vertexes have many edges, it's harder to figure out how/if the loop passes through that vertex (in particular: just because you know it enters from one face, does not mean it has to exit through any particular other face), but once you do it blocks off many more possibilities * if faces have few edges, you're more likely to get numbers that constrain the puzzle, but those don't do much for you * if faces have many edges, you're less likely to get numbers that constrain the puzzle, but the ones you get have major implications Spectre/Hat (a recent addition, probably not in your distro's version) play a bit funny because unlike the n-gon puzzles there's no instinctive memory of what n-1 is to follow the very-useful S rules (my name): S-rule, edge version: whenever 2 n-minus-one faces touch at an edge, that edge must be marked as part of the loop, adjacent edges remain unknown (only 2 possibilities remain, an S or reverse S shape), and all others are part of the loop S-rule, vertex version: whenever 2 n-minus-one faces touch at a vertex (not possible for all tilings), the edges that touch remain unknown but all other edges of the faces can be marked as part of the loop. Additionally, any other edges that touch the vertex (not possible to all tilings) can be marked as not be part of the loop. Most forms of the S rule are easily shown in the "triangular" tiling by looking for adjacent 2s, though the edge version's "all other edges" set is empty.
  - o11c 2y ago
    Having now sat down and played the new tilings for a bit, I can now say ... the utter lack of QoL features (a problem with all puzzles past the trivialest difficulty) really hits hard, since they are full of chains of 2-4 edges from the start, unlike other tilings where they only appear halfway through a solve and are limited in number.
gilleain 2y ago
I wonder if the enumeration approach from this paper : https://pubs.acs.org/doi/10.1021/ci025526c# https://pubs.acs.org/doi/10.1021/ci025526c# which (I'm aware it's paywalled) essentially enumerates using the inner duals of the tilling and then reconstructs from that inner dual. Seems like if you could just run through the legal tilings, rather than have to reject ones where the random choice of next tile was not legal, it would be faster

60 points by robinhouston 2y ago

The original hat tile paper came with a nice webdemo (https://github.com/isohedral/hatviz https://github.com/isohedral/hatviz) for recursively builidng a tiling following the method in the paper. I have a version with a few additions (Truchet patterns) hosted if anyone wants to play around with it here: https://www.johansivertsen.com/customhatviz/app.html https://www.johansivertsen.com/customhatviz/app.html

carb 2y ago

really fun read and great diagrams throughout!

fanf2 2y ago

Simon developed these algorithms for his puzzle Loopy https://www.chiark.greenend.org.uk/~sgtatham/puzzles/js/loopy.html https://www.chiark.greenend.org.uk/~sgtatham/puzzles/js/loop... - bop the “type” menu to choose which tiling to play the game on, including Penrose, Hats, Spectres, and many others.

o11c 2y ago
The interesting thing about Loopy (compared to other SGT puzzles) is how differently the game plays depending on choice of tiling: * if vertexes have few edges, it's easier to figure out how/if the loop passes through that vertex, but once you do it doesn't imply much about the rest of the puzzle * if vertexes have many edges, it's harder to figure out how/if the loop passes through that vertex (in particular: just because you know it enters from one face, does not mean it has to exit through any particular other face), but once you do it blocks off many more possibilities * if faces have few edges, you're more likely to get numbers that constrain the puzzle, but those don't do much for you * if faces have many edges, you're less likely to get numbers that constrain the puzzle, but the ones you get have major implications Spectre/Hat (a recent addition, probably not in your distro's version) play a bit funny because unlike the n-gon puzzles there's no instinctive memory of what n-1 is to follow the very-useful S rules (my name): S-rule, edge version: whenever 2 n-minus-one faces touch at an edge, that edge must be marked as part of the loop, adjacent edges remain unknown (only 2 possibilities remain, an S or reverse S shape), and all others are part of the loop S-rule, vertex version: whenever 2 n-minus-one faces touch at a vertex (not possible for all tilings), the edges that touch remain unknown but all other edges of the faces can be marked as part of the loop. Additionally, any other edges that touch the vertex (not possible to all tilings) can be marked as not be part of the loop. Most forms of the S rule are easily shown in the "triangular" tiling by looking for adjacent 2s, though the edge version's "all other edges" set is empty.
- o11c 2y ago
  Having now sat down and played the new tilings for a bit, I can now say ... the utter lack of QoL features (a problem with all puzzles past the trivialest difficulty) really hits hard, since they are full of chains of 2-4 edges from the start, unlike other tilings where they only appear halfway through a solve and are limited in number.

gilleain 2y ago

I wonder if the enumeration approach from this paper : https://pubs.acs.org/doi/10.1021/ci025526c# https://pubs.acs.org/doi/10.1021/ci025526c# which (I'm aware it's paywalled) essentially enumerates using the inner duals of the tilling and then reconstructs from that inner dual. Seems like if you could just run through the legal tilings, rather than have to reject ones where the random choice of next tile was not legal, it would be faster