Revisions for "Make this backtracking maze-generation algorithm iterative"

Make this backtracing maze-generation algorithm iterative

The following gist is a working implementation of a back-tracing maze algorithm:

 python maze.py
*****************************************
*         *               *             *
***** *** * ***** ******* * *********** *
*     * * * *     * *     *   *       * *
* ***** * * * ***** * ***** * ******* * *
*   *     * * *       *   * * *     *   *
* * *** *** * * ******* * * * * *** * ***
* *   * *   * *     *   * * *   *   *   *
* *** *** *** ***** * *** * ***** *******
* * *   * *   *   * *   * *   * *       *
* * *** * * * * * * *** * *** * ******* *
*   * * * * * * * *   * *     *     * * *
*** * * * * *** * *** * ******* *** * * *
* * * *   *   * *   * * *   *     * * * *
* * * ******* * *** * * * * ***** * * * *
* * *     *   * * * * *   *       *   * *
* * * ***** *** * * * *************** * *
*     *     *   * * *         *       * *
* ***** *** * *** * ********* ******* * *
* *     *   *   * *   *     *       * * *
* * ***** ***** * *** *** * ******* *** *
* * *     * *   * * *   * *     * *   * *
* * ***** * * *** * * * *** *** * *** * *
* * *   *   *   * * * *   *   *     *   *
*** * * * ***** * * ***** * * ********* *
*   * * * *     * *       * *       *   *
* * * * *** ***** ********* ******* * ***
* * * *     *       *     * *     *   * *
* *** ******* *** * * *** * *** * ***** *
*   *       * *   * * * *       * *     *
*** ******* * * *** * * ********* * * ***
*     * *   * * * * *   *   *   * * *   *
* *** * * ***** * * ***** * *** * ***** *
*   *   * *     * *       *   *   *     *
* * *** * * ***** *********** * *** *** *
* *   * *   *     *         * *   * *   *
* *** ******* ***** *** ***** *** * * ***
*   *     *         * *   *   * *   *   *
*** ***** * ********* *** * *** ******* *
*       *               *   *           *
*****************************************

Unfortunately, this algorithm breaks for large maze sizes (e.g., 100 x 100, 200 x 200) because the maximum recursion depth is reached:

File "/System/Library/Frameworks/Python.framework/Versions/2.7/lib/python2.7/random.py", line 288, in shuffle
    for i in reversed(xrange(1, len(x))):
RuntimeError: maximum recursion depth exceeded while calling a Python object

This bounty is to modify this algorithm to that it is iterative and thus capable of creating a 100 x 100 and 200 x 200 maze without the above error.

Make this backtracing maze-generation algorithm iterative
The following gist is a working implementation of a back-tracing maze algorithm: ❯ : https://gist.github.com/suchow/d446254351717ec57223af648bdc7696 ❯ python maze.py ***************************************** * * * * ***** *** * ***** ******* * *********** * * * * * * * * * * * * * ***** * * * ***** * ***** * ******* * * * * * * * * * * * * * * * *** *** * * ******* * * * * *** * *** * * * * * * * * * * * * * * *** *** *** ***** * *** * ***** ******* * * * * * * * * * * * * * * * *** * * * * * * *** * *** * ******* * * * * * * * * * * * * * * * * *** * * * * *** * *** * ******* *** * * * * * * * * * * * * * * * * * * * * * ******* * *** * * * * ***** * * * * * * * * * * * * * * * * * * * * ***** *** * * * *************** * * * * * * * * * * * * ***** *** * *** * ********* ******* * * * * * * * * * * * * * * * ***** ***** * *** *** * ******* *** * * * * * * * * * * * * * * * * * ***** * * *** * * * *** *** * *** * * * * * * * * * * * * * * * *** * * * ***** * * ***** * * ********* * * * * * * * * * * * * * * * * *** ***** ********* ******* * *** * * * * * * * * * * * * *** ******* *** * * *** * *** * ***** * * * * * * * * * * * * *** ******* * * *** * * ********* * * *** * * * * * * * * * * * * * * * *** * * ***** * * ***** * *** * ***** * * * * * * * * * * * * * *** * * ***** *********** * *** *** * * * * * * * * * * * * * *** ******* ***** *** ***** *** * * *** * * * * * * * * * * *** ***** * ********* *** * *** ******* * * * * * * ***************************************** Unfortunately, this algorithm breaks for large maze sizes (e.g., 100 x 100, 200 x 200) because the maximum recursion depth is reached: File "/System/Library/Frameworks/Python.framework/Versions/2.7/lib/python2.7/random.py", line 288, in shuffle for i in reversed(xrange(1, len(x))): RuntimeError: maximum recursion depth exceeded while calling a Python object This bounty is to modify this algorithm to that it is iterative and thus capable of creating a 100 x 100 and 200 x 200 maze without the above error.
Make this backtracking maze-generation algorithm iterative
The following gist is a working implementation of a back-tracing maze algorithm: https://gist.github.com/suchow/d446254351717ec57223af648bdc7696 ❯ python maze.py ***************************************** * * * * ***** *** * ***** ******* * *********** * * * * * * * * * * * * * ***** * * * ***** * ***** * ******* * * * * * * * * * * * * * * * *** *** * * ******* * * * * *** * *** * * * * * * * * * * * * * * *** *** *** ***** * *** * ***** ******* * * * * * * * * * * * * * * * *** * * * * * * *** * *** * ******* * * * * * * * * * * * * * * * * *** * * * * *** * *** * ******* *** * * * * * * * * * * * * * * * * * * * * * ******* * *** * * * * ***** * * * * * * * * * * * * * * * * * * * * ***** *** * * * *************** * * * * * * * * * * * * ***** *** * *** * ********* ******* * * * * * * * * * * * * * * * ***** ***** * *** *** * ******* *** * * * * * * * * * * * * * * * * * ***** * * *** * * * *** *** * *** * * * * * * * * * * * * * * * *** * * * ***** * * ***** * * ********* * * * * * * * * * * * * * * * * *** ***** ********* ******* * *** * * * * * * * * * * * * *** ******* *** * * *** * *** * ***** * * * * * * * * * * * * *** ******* * * *** * * ********* * * *** * * * * * * * * * * * * * * * *** * * ***** * * ***** * *** * ***** * * * * * * * * * * * * * *** * * ***** *********** * *** *** * * * * * * * * * * * * * *** ******* ***** *** ***** *** * * *** * * * * * * * * * * *** ***** * ********* *** * *** ******* * * * * * * ***************************************** Unfortunately, this algorithm breaks for large maze sizes (e.g., 100 x 100, 200 x 200) because the maximum recursion depth is reached: File "/System/Library/Frameworks/Python.framework/Versions/2.7/lib/python2.7/random.py", line 288, in shuffle for i in reversed(xrange(1, len(x))): RuntimeError: maximum recursion depth exceeded while calling a Python object This bounty is to modify this algorithm to that it is iterative and thus capable of creating a 100 x 100 and 200 x 200 maze without the above error.
Back to question