There's a clever bijection between mazes (spanning trees of an m-by-n grid graph) and domino tilings of a (2m-1)-by-(2n-1) rectangle with the bottom-left corner removed. And you can greedily build such domino tilings, one layer at a time, by 'playing Tetris with dominoes'. I imagine that if you take this algorithm and pass it through the bijection, you get Eller's algorithm. -- APG
Sent: Friday, April 12, 2019 at 4:16 PM From: "Mike Stay" <metaweta@gmail.com> To: math-fun <math-fun@mailman.xmission.com> Subject: Re: [math-fun] Draft of my April 17, 2019 essay
On Fri, Apr 12, 2019 at 9:14 AM Mike Stay <metaweta@gmail.com> wrote:
The kinds of maze you often see as busywork have a single entrance and a single exit on the exterior wall, and have a single path between any two points in the maze. There's an algorithm for generating such mazes of arbitrary height when only the width is known in advance.
Hmm, that didn't quite capture how cool Eller's algorithm is. You only need to store one row of the maze in memory at any time, forgetting everything that went before. As soon as the "stop" signal is received, you print out the final row and the exit. -- Mike Stay - metaweta@gmail.com http://math.ucr.edu/~mike https://reperiendi.wordpress.com
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun