How many walls do you need for a square maze?

By | December 3, 2011

At the Japanese contest, Peter said there is a closed form solution for the maximum number of walls a legal micromouse maze can have.

His suggestion was to draw out mazes in increasing size and the pattern will emerge. Also, the rules say every post, except the center post, will have at least one wall attached.

The number of walls for an N x N maze with at least one wall is:

4*N + (N-1)^2

The first term is for the outer perimeter and the second one is for at least one wall attached.

You need additional walls if you want spares or want to block off areas. I don’t have a good rule of thumb and am guessing 10% overage is probably not a bad idea.

8 thoughts on “How many walls do you need for a square maze?

  1. Peter Harrison

    For a general rectangular maze, of width X and height Y, I believe the solution is this:

    For the perimeter, you need 2*(X+Y) walls.
    There are P = (X-1)(Y-1) internal posts and (X+1)(Y+1) posts in total.
    The smallest number of walls you can have is W = int((P+1)/2).
    The largest number of walls you can use for an open maze is W = P.

    By an open maze, I mean one where all the cells are have a route to every other cell.

    So, for a 16×16 contest maze, you would need 289 posts, 64 walls for the perimeter and between 113 and 225 internal walls to create an open maze.

    Any advance on that?

  2. Patrick Reybaud

    Hi Peter,
    We can’t find maze kit on matrix multimedia or active robots. Do you have any idea for finding maze wall and post compatible?

    Thanks

  3. Peter Harrison

    I am sorry. I only know of places in the far East. You would have to commit to ordering several hundred for a good price. If you are looking for a smaller number, you could try RT-Corp:

    http://www.rt-shop.jp/index.php?main_page=index&cPath=1002_1023_1025

    But they are very expensive.

    It will be easier in the end to make your own from 12mm plywood and 12mm hardwood for the posts.

    Please post here if you do find anywhere else.

  4. Patrick Reybaud

    Thanks Peter,
    I’m still searching. I have already bought matrix multimedia walls and I would like to find the same maze for have full compatibility. I will post if I find anything…

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.