You're in a space of twisty little mazes, all alike

[mrcactu5]

this is known as a uniform spanning tree https://en.wikipedia.org/wiki/Spanning_tree

these can be sampled using Wilson's algorithm for Loop-Erased Random Walks https://en.wikipedia.org/wiki/Loop-erased_random_walk#The_un...

Here is a nice visualization of Wilson's algorithm using d3.js by Michael Bostock (NY Times) http://bl.ocks.org/mbostock/11357811

[9ac345a5509a]

The number of such mazes is also on OEIS under A007341: http://oeis.org/A007341

[jerf]

It seems like it would be way easier to think about it the opposite way... pick a space, start enumerating the possible connections it can have to its neighbors recursively, with a simple algorithm that won't pick already picked neighbors, and then read the bit string off the result. That's easily done by starting with all 1s, and then setting to 0 the bit corresponding to the choice you just made.

Either direction is of course the same in theory, of course.

More excitingly than that, you may be able to contribute to OEIS now, if you can work yourself out a few more terms: https://oeis.org/search?q=1%2C1%2C28%2C12600&sort=&language=...

[jdjdps]

I like the epilogue. I too wish I could go back to my younger self and describe this understanding. I would try to explain to myself that each pattern can be seen as an object in and of itself. That an algorithm is a way to move between these objects in a specific way that marries with a particular human goal. I would try to explain that each step of an algorithmic process combined can be seen independently of time as a pattern in and of itself and as such is itself an object. A process is a noun, a thing just as much as a chair or a lightbulb. I would say that in order to find an algorithm to solve a goal, all one needs to do is imagine the shape formed by this goal and construct that shape from the shapes that are readily available to you. Be them finger movements on an abacus or bitwise operations in a computer memory. And then I would explain that the universe can be seen in this way. The entire thing as a single object out there in phase space. I would tell myself that I suspected that all possible shapes exist, that the shape of your life exists only as much as the shape of a thing that you imagine while dreaming. This was the understanding I have been searching for since my early teens. It is such a joy to have found it, I like to think my younger self would have cherished it as much. But I may have discarded them as the ramnlings of an old fool.

[asdftemp]

https://en.wikipedia.org/wiki/Kirchhoff%27s_theorem ?

[kmill]

Implementation: https://gist.github.com/kmill/f4f47913d036fce687bc

Though it counts reflections as distinct.

[ginko]

It surprised me that he even mentioned the concept of a spanning tree, yet didn't use it for more than a coarse upper bound.

[VieElm]

Now watch this question pop up on technical interviews everywhere for days because people read about it here.

[drabiega]

That'd be great for those of us who read it and a going to interviews.

[comrh]

Interesting post, something people often ignore is talking about the failures that got them to the solution but this is usually the real interesting stuff!

[nobrains]

The answer from the post: http://strangelyconsistent.org/blog/images/all-the-4x4-mazes...