Shortest universal maze exit string A maze on an N by N grid of square cells is defined by specifying whether each edge is a wall or not a wall. All outer edges are walls. One cell is defined as the start, and one cell is defined as the exit, and the exit is reachable from the start. The start and exit are never the same cell.

Note that neither the start nor the exit need to be on the outer border of the maze, so this is a valid maze:



A string of 'N', 'E', 'S' and 'W' indicates attempting to move North, East, South and West respectively. A move that is blocked by a wall is skipped without movement. A string exits a maze if applying that string from the start results in the exit being reached (regardless of whether the string continues after reaching the exit).

Inspired by this puzzling.SE question for which xnor provided a provable method of solving with a very long string, write code that can find a single string that exits any 3 by 3 maze.

Excluding invalid mazes (start and exit on the same cell, or exit not reachable from start) there are 138,172 valid mazes and the string must exit each of them.

Validity

The string must satisfy the following:


It is composed of only the characters 'N', 'E', 'S' and 'W'.
It exits any maze it is applied to, if started at the start.


Since the set of all possible mazes includes each possible maze with each possible valid starting point, this automatically means that the string will exit any maze from any valid starting point. That is, from any starting point from which the exit is reachable.

Winning

The winner is the answer that provides the shortest valid string and includes the code used to produce it. If more than one of the answers provide a string of this shortest length, the first to post that string length wins.

Example

Here is an example string 500 characters long, to give you something to beat:

SEENSSNESSWNNSNNNNWWNWENENNWEENSESSNENSESWENWWWWWENWNWWSESNSWENNWNWENWSSSNNNNNNESWNEWWWWWNNNSWESSEEWNENWENEENNEEESEENSSEENNWWWNWSWNSSENNNWESSESNWESWEENNWSNWWEEWWESNWEEEWWSSSESEEWWNSSEEEEESSENWWNNSWNENSESSNEESENEWSSNWNSEWEEEWEESWSNNNEWNNWNWSSWEESSSSNESESNENNWEESNWEWSWNSNWNNWENSNSWEWSWWNNWNSENESSNENEWNSSWNNEWSESWENEEENSWWSNNNNSSNENEWSNEEWNWENEEWEESEWEEWSSESSSWNWNNSWNWENWNENWNSWESNWSNSSENENNNWSSENSSSWWNENWWWEWSEWSNSSWNNSEWEWENSWENWSENEENSWEWSEWWSESSWWWNWSSEWSNWSNNWESNSNENNSNEWSNNESNNENWNWNNNEWWEWEE


Thanks to orlp for donating this.



Leaderboard



Equal scores are listed in order of posting of that score. This is not necessarily the order that the answers were posted since the score for a given answer may be updated over time.



Judge

Here is a Python 3 validator that takes a string of NESW as a command line argument or via STDIN.

For an invalid string, this will give you a visual example of a maze it fails for.
C++, 97 95 93 91 86 83 82 81 79 characters


  NNWSWNNSENESESWSSWNSEENWWNWSSEWWNENWEENWSWNWSSENENWNWNESENESESWNWSESEWWNENWNEES


My strategy is fairly simple - an evolution algorithm that can grow, shrink, swap elements of and mutate valid sequences. My evolution logic is now nearly the same as @Sp3000's, as his was an improvement over mine.

However, my implementation of the maze logic is rather nifty. This allows me to check if strings are valid at blistering speed. Try to figure it out by looking at the comment, do_move and the Maze constructor.

#include &lt;algorithm&gt;
#include &lt;bitset&gt;
#include &lt;cstdint&gt;
#include &lt;iostream&gt;
#include &lt;random&gt;
#include &lt;set&gt;
#include &lt;vector&gt;

/*
    Positions:

        8, 10, 12
        16, 18, 20
        24, 26, 28

    By defining as enum respectively N, W, E, S as 0, 1, 2, 3 we get:

        N: -8, E: 2, S: 8, W: -2
        0: -8, 1: -2, 2: 2, 3: 8

    To get the indices for the walls, average the numbers of the positions it
    would be blocking. This gives the following indices:

        9, 11, 12, 14, 16, 17, 19, 20, 22, 24, 25, 27

    We'll construct a wall mask with a 1 bit for every position that does not
    have a wall. Then if a 1 shifted by the average of the positions AND'd with
    the wall mask is zero, we have hit a wall.
*/

enum { N = -8, W = -2, E = 2, S = 8 };
static const int encoded_pos[] = {8, 10, 12, 16, 18, 20, 24, 26, 28};
static const int wall_idx[] = {9, 11, 12, 14, 16, 17, 19, 20, 22, 24, 25, 27};
static const int move_offsets[] = { N, W, E, S };

int do_move(uint32_t walls, int pos, int move) {
    int idx = pos + move / 2;
    return walls &amp; (1ull &lt;&lt; idx) ? pos + move : pos;
}

struct Maze {
    uint32_t walls;
    int start, end;

    Maze(uint32_t maze_id, int start, int end) {
        walls = 0;
        for (int i = 0; i &lt; 12; ++i) {
            if (maze_id &amp; (1 &lt;&lt; i)) walls |= 1 &lt;&lt; wall_idx[i];
        }
        this-&gt;start = encoded_pos[start];
        this-&gt;end = encoded_pos[end];
    }

    uint32_t reachable() {
        if (start == end) return false;

        uint32_t reached = 0;
        std::vector&lt;int&gt; fill; fill.reserve(8); fill.push_back(start);
        while (fill.size()) {
            int pos = fill.back(); fill.pop_back();
            if (reached &amp; (1 &lt;&lt; pos)) continue;
            reached |= 1 &lt;&lt; pos;
            for (int m : move_offsets) fill.push_back(do_move(walls, pos, m));
        }

        return reached;
    }

    bool interesting() {
        uint32_t reached = reachable();
        if (!(reached &amp; (1 &lt;&lt; end))) return false;
        if (std::bitset&lt;32&gt;(reached).count() &lt;= 4) return false;

        int max_deg = 0;
        uint32_t ends = 0;
        for (int p = 0; p &lt; 9; ++p) {
            int pos = encoded_pos[p];
            if (reached &amp; (1 &lt;&lt; pos)) {
                int deg = 0;
                for (int m : move_offsets) {
                    if (pos != do_move(walls, pos, m)) ++deg;
                }
                if (deg == 1) ends |= 1 &lt;&lt; pos;
                max_deg = std::max(deg, max_deg);
            }
        }

        if (max_deg &lt;= 2 &amp;&amp; ends != ((1u &lt;&lt; start) | (1u &lt;&lt; end))) return false;

        return true;
    }
};

std::vector&lt;Maze&gt; gen_valid_mazes() {
    std::vector&lt;Maze&gt; mazes;
    for (int maze_id = 0; maze_id &lt; (1 &lt;&lt; 12); maze_id++) {
        for (int points = 0; points &lt; 9*9; ++points) {
            Maze maze(maze_id, points % 9, points / 9);
            if (!maze.interesting()) continue;
            mazes.push_back(maze);
        }
    }

    return mazes;
}

bool is_solution(const std::vector&lt;int&gt;&amp; moves, Maze maze) {
    int pos = maze.start;
    for (auto move : moves) {
        pos = do_move(maze.walls, pos, move);
        if (pos == maze.end) return true;
    }

    return false;
}

std::vector&lt;int&gt; str_to_moves(std::string str) {
    std::vector&lt;int&gt; moves;
    for (auto c : str) {
        switch (c) {
        case 'N': moves.push_back(N); break;
        case 'E': moves.push_back(E); break;
        case 'S': moves.push_back(S); break;
        case 'W': moves.push_back(W); break;
        }
    }

    return moves;
}

std::string moves_to_str(const std::vector&lt;int&gt;&amp; moves) {
    std::string result;
    for (auto move : moves) {
             if (move == N) result += "N";
        else if (move == E) result += "E";
        else if (move == S) result += "S";
        else if (move == W) result += "W";
    }
    return result;
}

bool solves_all(const std::vector&lt;int&gt;&amp; moves, std::vector&lt;Maze&gt;&amp; mazes) {
    for (size_t i = 0; i &lt; mazes.size(); ++i) {
        if (!is_solution(moves, mazes[i])) {
            // Bring failing maze closer to begin.
            std::swap(mazes[i], mazes[i / 2]);
            return false;
        }
    }
    return true;
}

template&lt;class Gen&gt;
int randint(int lo, int hi, Gen&amp; gen) {
    return std::uniform_int_distribution&lt;int&gt;(lo, hi)(gen);
}

template&lt;class Gen&gt;
int randmove(Gen&amp; gen) { return move_offsets[randint(0, 3, gen)]; }

constexpr double mutation_p = 0.35; // Chance to mutate.
constexpr double grow_p = 0.1; // Chance to grow.
constexpr double swap_p = 0.2; // Chance to swap.

int main(int argc, char** argv) {
    std::random_device rnd;
    std::mt19937 rng(rnd());
    std::uniform_real_distribution&lt;double&gt; real;
    std::exponential_distribution&lt;double&gt; exp_big(0.5);
    std::exponential_distribution&lt;double&gt; exp_small(2);

    std::vector&lt;Maze&gt; mazes = gen_valid_mazes();

    std::vector&lt;int&gt; moves;
    while (!solves_all(moves, mazes)) {
        moves.clear();
        for (int m = 0; m &lt; 500; m++) moves.push_back(randmove(rng));
    }

    size_t best_seen = moves.size();
    std::set&lt;std::vector&lt;int&gt;&gt; printed;
    while (true) {
        std::vector&lt;int&gt; new_moves(moves);
        double p = real(rng);

        if (p &lt; grow_p &amp;&amp; moves.size() &lt; best_seen + 10) {
            int idx = randint(0, new_moves.size() - 1, rng);
            new_moves.insert(new_moves.begin() + idx, randmove(rng));
        } else if (p &lt; swap_p) {
            int num_swap = std::min&lt;int&gt;(1 + exp_big(rng), new_moves.size()/2);
            for (int i = 0; i &lt; num_swap; ++i) {
                int a = randint(0, new_moves.size() - 1, rng);
                int b = randint(0, new_moves.size() - 1, rng);
                std::swap(new_moves[a], new_moves[b]);
            }
        } else if (p &lt; mutation_p) {
            int num_mut = std::min&lt;int&gt;(1 + exp_big(rng), new_moves.size());
            for (int i = 0; i &lt; num_mut; ++i) {
                int idx = randint(0, new_moves.size() - 1, rng);
                new_moves[idx] = randmove(rng);
            }
        } else {
            int num_shrink = std::min&lt;int&gt;(1 + exp_small(rng), new_moves.size());
            for (int i = 0; i &lt; num_shrink; ++i) {
                int idx = randint(0, new_moves.size() - 1, rng);
                new_moves.erase(new_moves.begin() + idx);
            }
        }

        if (solves_all(new_moves, mazes)) {
            moves = new_moves;

            if (moves.size() &lt;= best_seen &amp;&amp; !printed.count(moves)) {
                std::cout &lt;&lt; moves.size() &lt;&lt; " " &lt;&lt; moves_to_str(moves) &lt;&lt; "\n";
                if (moves.size() &lt; best_seen) {
                    printed.clear(); best_seen = moves.size();
                }
                printed.insert(moves);
            }
        }
    }

    return 0;
}