Reconstructing a tiling from "is-adjacent-to" data?

[Envelope Generator]

I was idly Wikisurfing, trying to navigate through a province county by county by clicking through listings of neighboring counties on the Wikipedia pages of individual counties, and this popped into my head: is reconstructing a tiling (I'm not sure if that's the right word) from a set of "X is adjacent to Y" data a known problem? How hard is it?

[jaap]

You can think of this data as a graph, where the countries are vertices and the 'is adjacent to' relation gives you the edges.
Your question then boils down to this: Given a planar graph, draw it without any crossing edges. Or in more mathematical terms, find an embedding of a planar graph in the plane.
According to this wiki page it's of linear time complexity (in the number of edges). Determining whether a graph is planar or not is therefore also linear time.

[Xanthir]

It's also an enjoyable puzzle game.

[Envelope Generator]

Cool, thanks!

[jaap]

By the way, the solution is usually not unique. For example, if you have 4 countries where each is adjacent to all three others, then you can draw a map in 8 distinct ways: You can choose any of the 4 countries to be in the middle, landlocked by the other three countries, and those other three can be in arranged in two different ways around it which are mirror images of one another.

Edit: Even if you specify which countries have a coast line (essentially adding an extra "country" representing the oceans), then there can still be different ways of drawing a map, beyond just mirror images.

[troyp]

It's also an enjoyable puzzle game.

That's actually a lot easier than it looks (I guess that's not surprising if it's a linear time algorithm). There's something oddly satisfying about it, though.

[Xanthir]

Yeah, it's simple, but has a great "organizing things" feel to it.

(Try all the other games at his site - he just took a bunch of games he liked from the web or random OSes and recoded them in JS for his own use. I'm in love with Towers right now.)

[Flumble]

(Try all the other games at his site - he just took a bunch of games he liked from the web or random OSes and recoded them in JS for his own use. I'm in love with Towers right now.)

This needs a tvtropes-tier warning. I've probably sunk as much time into that site as into minecraft. (mostly Loopy)

[troyp]

I've bookmarked the site to check out the other games later. (Actually, I'm sure I've come across this site before, a couple of times. I remember the name.)

It's pretty cool that he's compiled the same C code to Java applets, Javascript and native code on 3 platforms.

[Wildcard]

(Try all the other games at his site - he just took a bunch of games he liked from the web or random OSes and recoded them in JS for his own use. I'm in love with Towers right now.)

This needs a tvtropes-tier warning. I've probably sunk as much time into that site as into minecraft. (mostly Loopy)

Undead. For some reason it's really tricky to reason correctly about it for me. For instance, try this puzzle, which I finally resorted to sketching out the two different possibilities to see which one worked.

EDIT: Actually, once you realize that zombies are almost always the last to get filled in, it's often much easier.

[Xanthir]

Eh, I fill in everybody together. That particular puzzle was relatively difficult, but I was able to get it done without backtracking, just holding a few relationships in my mind at once. Are you familiar with clicking on the numbers to turn them gray and indicate you've solved their paths? It makes it a lot easier to think about things.

0s are manna from heaven - they dictate *precisely* what everything is along their path - ghosts before the first mirror, vamps after. Numbers equal to the path length are valuable, too - they constrain the before/after first mirror parts to v/z and g/z respectively, and the number on the other side dictates how many zombies (or between-two-mirrors ghosts) there must be. Any path that starts with a mirror is great (or has its first mirror on its last square), too, because that limits you significantly in what possibilities there are. In general, the difference between the numbers on either end of a path give you really valuable information - the larger the difference between the two, the small number of zombies are possible on the path, which might quickly dictate the rest of the positions as definitely ghosts or vampires.