out of 2^441, one — Flashbulb

Of all of the ways to toggle the blocks on a 21x21 binary grid, this is one of the many that has the property that you can walk from the top-left to the bottom right with no fewer than 42 steps. There's nothing special about this example, it's just one guy in a big space. But.. some of those little features in there, islands, peninsulas, isthmuses, straits, inland lakes, disconnected continents, this single non-descript sample of full of micro-patterns we might want to require or forbid when we go out to design our own little world map. Do you think you could invent a single function that estimated how much you'd like a map before you saw it? Not with much confidence, no. Do you think you could order off of a menu which features you'd like to see next and specify which symmetries you'd like on the side, just for the next sample? More likely.

Comments (3):

This blog is nice and amazing. I love your post! It's also nice to see someone who does a lot of research and has a great knack for ting, which is pretty rare from bloggers these days. Thanks! neck lift

2012-01-09 02:53:06 · Shagor2012

I have a correction for you: the total number of possibilities for the board is 2^882. You have 441 positions, but 4 possibilities for each position, so 4^441 = 2^882.

2012-10-12 05:33:14 · SandManMattSH

Have a look at this explanation of the program that generated it: eis-blog.ucsc.edu/2011/10/map-generation-speedrun/ There really only are two options (solid or not) for each tile in the 21x21 grid. The coloring in the picture above is a derived property of those 2^441 choices. Solid tiles are colored green, lavender, or red if they are reachable in 42 steps, reachable beyond that, or unreachable respectively. The tile is white if it isn't solid. So, while there might be 2^882 ways to four-color a 21x21 grid, it turns out that exactly 2^441 of those are incompatible with the reachability-based coloring rules I described, giving 2^441.

2012-12-02 14:12:42 · Adam Smith