5

I'm thinking of creating a program to let me play or solve slitherlink puzzles, like on krazydad.com. It consists of tiles of 4, 5, 6, 7 and 8 sides. All but the seven sided tiles seem to have sides with the same length, with the sides between two seven sided tiles (and therefore connecting five-sided tiles to 4 sided tiles) having sides of approximately 70% of the normal length. As you can see in the picture below, octagons are surrounded by alternating pentagons and hexagons. These are attached to others a by the far sides of the hexagons. Attached to the tips of the pentagons are smaller lines connecting to squares connecting to other groups. Around the squares are then formed seven-sided figures with two short sides. I think the outer edge is defined by just omitting tiles that are too far away from the center.

enter image description here

For a data structure I think I need a graph connecting all nodes. I can let the user click to place a solid line on the closest link, and I can check for loops or too many lines entering a node fairly easily. I'll also need to create tiles and associate lines to them, with inner lines being assigned to both tiles, but treated as one line.

As for setting it up, I am thinking of manually figuring out the points and defining the minimal set of repeated tiles (1 8, 4 5, 4 6, 4 7 and 1 4), then placing them next to each other. When placing, I would check for existing close points to each one I'm placing and combine them if found. Then I would need to check for duplicate lines and merge them as well.

Is there an easier or cleaner way to A) generate the tiling or B) merge the nodes and links when doing my tiling?

Improve this question
0

1 Answer 1

Reset to default
3

some observations that might help:

  • if you join the centres of neighbouring polygons you have a delaunay triangulation (1).

  • the dual (2) of the delaunay triangulation is the graph above (with slightly different edge lengths, but you can adjust that if necessary)

  • there's a discussion here (3) of how to generate graphs from delaunay triangulations

so, putting that together, you could:

  • generate the centres of the tiles (see below)

  • construct the delaunay triangulation from the tile centres (by joining neigbours).

  • find the dual to get the graph you want (the process of finding the dual should be supported by a good graph library)

to generate the pattern of tile centres, take the minimal set and start with the centre 8. for each 90 degree rotation about there, add the (rotated) minimal set (plus an 8 in addition to the one you're rotating around), removing duplicates. then do the same on the 8s that you have added (either recurse or use a stack).

once you have the centres, i'm not sure what the best way to connect neighbours would be - you want some efficient way of generating a set of candidates. but it's not a hard problem, just fiddly (a "fancy" solution would be quadtree or spatial hashes, but just a crude binning would probably be enough).

Improve this answer
Sign up to request clarification or add additional context in comments.

4 Comments

So in joining the centers to create the delaunay triangulation, you are taking the dual of the original graph, right? I'm trying to use the python code in your discussion link but can't get ATLAS to compile and therefore scipy won't install. I wouldn't know how to use it in C# anyway. Also I don't think the dual of the delaunay triangulation would place the final points in the right places to form regular polygons, would it?
yes, the delaunay triangulation is the dual of the graph (which is - close to - a voronoi tessellation). the final points would need adjusting, yes (that was what i meant with "slightly different edge lengths) so you would need to fix them up, but that should be a fairly easy problem (is every point a member of either an 8 or 6?).
The points at the tips of the 5s and around the 4s aren't members of 8s or 6s. The centers of the irregular 7s are what would really throw off a generic positioning algorithm I think though. I'm thinking now about creating classes for each size and letting them recursively build the graph breadth-first. So first create the center 8. Create point 0 (let's say top-left). Now create point 1 (clockwise top-right). Create top 5 and set the two points and line, but move on with 8 by rotating the vector from point 0 to 1 by 45 degrees to create another point, the new line creates a 6, etc.
yeah, i think in retrospect that is probably as good a way as any. :o( ps i have fond childhood memories of the "altair design" books that puzzle is based on - amazon.com/Altair-Design-Special-Patterns-Everyone/dp/…

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.